Submission #998683

#	Time	Username	Problem	Language	Result	Execution time	Memory
998683		vjudge1	Knapsack (NOI18_knapsack)	C++17	73 / 100	1010 ms	22336 KiB

knapsack

#include<bits/stdc++.h>
#define int long long
using namespace std;
int N, S;
pair<int, pair<int, int> > a[100010];
vector<pair<int, int> > edge[20010];
vector<pair<int, int> > b;
int dp[20010];
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<=13; j++){
				if((1<<j)<=v.second){
					v.second-=(1<<j);
					b.push_back(make_pair(i*(1<<j), v.first*(1<<j)));
				}
			}
			if(v.second) 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]=-1e18;
	for(auto v:b){
		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=-1e18;
	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: 0 / 27