Submission #815275

#	Time	Username	Problem	Language	Result	Execution time	Memory
815275		Acanikolic	Knapsack (NOI18_knapsack)	C++14	100 / 100	65 ms	5948 KiB

knapsack

#include <bits/stdc++.h>
		 		
#define int long long 
		 
#define pb push_back 
		
#define F first
		 
#define S second
		 
using namespace std;
		 
const int N = 3e5+10;
		 
const int mod = 1e9+7;
		 
const int inf = 1e18;	
								
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
	
	int s,n;
	cin >> s >> n;
	vector<int>v(n+1),w(n+1),k(n+1);
	vector<pair<int,int>>g[s+1];
	for(int i=1;i<=n;i++) {
		cin >> v[i] >> w[i] >> k[i];
		g[w[i]].pb({v[i],k[i]});
	}
	for(int i=1;i<=s;i++) {
		sort(g[i].begin(),g[i].end());
		reverse(g[i].begin(),g[i].end());
	}
	vector<pair<int,int>>V;
	for(int i=1;i<=s;i++) {
		int mx = s/i;
		for(auto X:g[i]) {
			if(mx < 0) break;
			for(int j=1;j<=X.S;j++) {
				V.pb({X.F,i});
				mx -= 1;
				if(mx == -1) break;
			}
		}
	}
	vector<int>dp(s+1);
	for(auto X:V) {
		vector<int>new_dp = dp;
		for(int i=1;i<=s;i++) if(i >= X.S) new_dp[i] = max(new_dp[i],dp[i-X.S]+X.F);
		swap(dp,new_dp);
	}
	cout << dp[s];
    return 0; 
}

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