Submission #998690

#	Time	Username	Problem	Language	Result	Execution time	Memory
998690		vjudge1	Knapsack (NOI18_knapsack)	C++17	100 / 100	202 ms	14012 KiB

knapsack

#include<bits/stdc++.h>
using namespace std;
long long N, S;
pair<int, pair<int, int> > a[100010];
vector<pair<int, int> > edge[20010];
vector<pair<int, int> > b;
int dp[20010];
int cnt[20010];
bool cmp(pair<int, int> x, pair<int, int> y){
	return x.second>y.second;
}
signed main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin>>S>>N;
	for(int i=1; i<=N; i++) cin>>a[i].second.first>>a[i].second.second>>a[i].first;
	for(int i=1; i<=N; i++) edge[a[i].second.second].push_back(make_pair(a[i].second.first, a[i].first));
	for(int i=1; i<=S; i++){
		for(auto v:edge[i]){
			for(int j=0; j<=12; j++){
				if((1<<j)<=v.second){
					v.second-=(1<<j);
					if((long long)i*(1<<j)>S) break;
					b.push_back(make_pair(i*(1<<j), v.first*(1<<j)));
				}
			}
			if(v.second){
				if((long long)i*v.second<=S) b.push_back(make_pair(i*v.second, v.first*v.second));
			}
		}
	}
	sort(b.begin(), b.end());
	for(int i=1; i<=S; i++) dp[i]=-2e9;
	sort(b.begin(), b.end(), cmp);
	for(auto v:b){
		cnt[v.first]++;
		if(cnt[v.first]>S/v.first+1) continue;
		for(int i=S; i>=0; i--){
			if(i+v.first<=S){
				dp[i+v.first]=max(dp[i+v.first], dp[i]+v.second);
			}
		}
	}
	int total=-2e9;
	for(int i=0; i<=S; i++) total=max(total, dp[i]);
	cout<<total;
}

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