Submission #889303

#	Time	Username	Problem	Language	Result	Execution time	Memory
889303		dsyz	Knapsack (NOI18_knapsack)	C++17	100 / 100	100 ms	12672 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (1000005)
int main() {
	ios_base::sync_with_stdio(false);cin.tie(0);
	ll S,N;
	cin>>S>>N;
	ll V[N], W[N], K[N];
	for(ll i = 0;i < N;i++){
		cin>>V[i]>>W[i]>>K[i];
		K[i] = min(K[i],S);
	}
	vector<ll> weight[S + 1];
	for(ll i = 0;i < N;i++){
		ll k = K[i];
		ll pwrof2 = 1;
		while(k >= pwrof2){
			if(pwrof2 * W[i] > S) break;
			weight[pwrof2 * W[i]].push_back(pwrof2 * V[i]);
			k -= pwrof2;
			pwrof2 *= 2;
		}
		if(k >= 1){
			if(k * W[i] > S) continue;
			weight[k * W[i]].push_back(k * V[i]);
			k = 0;
		}
	}
	for(ll i = 0;i <= S;i++){
		sort(weight[i].begin(),weight[i].end(),greater<ll>());
	}
	vector<pair<ll,ll> > items;
	for(ll w = 1;w <= S;w++){
		ll needed = S / w; 
		//we only need to consider the top (S / w) elements sorted by decreasing value
		for(ll i = 0;i < min(ll(weight[w].size()),needed);i++){
			items.push_back({weight[w][i],w});
		}
	}	
	N = items.size();
	ll dp[S + 1];
	memset(dp,0,sizeof(dp));
	for(ll i = 0;i < N;i++){
		ll v = items[i].first;
		ll w = items[i].second;
		for(ll j = S - w;j >= 0;j--){
			dp[j + w] = max(dp[j + w],dp[j] + v);
		}
	}
	ll maximum = 0;
	for(ll i = 0;i <= S;i++){
		maximum = max(maximum,dp[i]);
	}
	cout<<maximum<<'\n';
}

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