Submission #433296

#	Time	Username	Problem	Language	Result	Execution time	Memory
433296		Autron	Knapsack (NOI18_knapsack)	C++14	100 / 100	127 ms	4824 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;

#define int long long

int32_t main(){
	int s, n;
	cin>>s>>n;
	vector<vector<pair<int, int>>> val(s+1, vector<pair<int, int>>(0));
	vector<int> dp(s+1, -1e18);
	for(int i=1;i<=n;++i){
		int a, b, c;
		cin>>a>>b>>c;
		val[b].push_back({a, c});
	}
	for(int i=1;i<=s;++i) sort(val[i].rbegin(), val[i].rend());
	dp[0]=0;
	for(int i=1;i<=s;++i){
		int x=0;
		for(auto it:val[i]){
			for(int j=1;j<=it.second;++j){
				x+=i;
				for(int k=s;k>=x;--k) dp[k]=max(dp[k], dp[k-i]+it.first);
				if(x>s) break;
			}
			if(x>s) break;
		}
	}
	int sol=0;
	for(int i=0;i<=s;++i) sol=max(sol, dp[i]);
	cout<<sol<<"\n";
}

• Subtask 1: 12 / 12
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 24 / 24
• Subtask 5: 27 / 27