Submission #950436

#	Time	Username	Problem	Language	Result	Execution time	Memory
950436		PM1	Knapsack (NOI18_knapsack)	C++17	100 / 100	73 ms	6748 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mxn=1e5+5,mxs=2e3+5;
int n,s,vv[mxn],w[mxn],k[mxn];
vector<int>v[mxn],gg;
bool cmp(int x,int y){
	return (vv[x]!=vv[y])?vv[x]<vv[y]:x<y;
}
ll dp[2][mxs];
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>s>>n;
	for(int i=1;i<=n;i++){
		cin>>vv[i]>>w[i]>>k[i];
		v[w[i]].push_back(i);
	}
	for(int i=1;i<mxs;i++)
		sort(v[i].begin(),v[i].end(),cmp);
	for(int i=1;i<mxs;i++){
		int sum=s/i;
		while(sum && v[i].size()){
			int x=v[i].back();
			gg.push_back(x);
			k[x]--;
			if(!k[x])v[i].pop_back();
			sum--;

		}
	}
	for(int i=0;i<gg.size();i++){
		int y=i&1;
		for(int j=1;j<=s;j++){
			dp[y][j]=dp[y^1][j];
			if(j>=w[gg[i]])dp[y][j]=max(dp[y][j],dp[y^1][j-w[gg[i]]]+vv[gg[i]]);
		}
	}
	ll ans=0;
	for(int i=0;i<mxs;i++){
		ans=max({ans,dp[0][i],dp[1][i]});
	}
	cout<<ans;
	return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:33:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |  for(int i=0;i<gg.size();i++){
      |              ~^~~~~~~~~~

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