Submission #650289

#	Time	Username	Problem	Language	Result	Execution time	Memory
650289		ono_de206	Knapsack (NOI18_knapsack)	C++14	100 / 100	126 ms	4904 KiB

knapsack

#include<bits/stdc++.h>
using namespace std;

#define int long long

const int mxn=1e5+10;
const int mxm=2010;

vector<pair<int,int>> lol[mxm];

int dp[2][mxm];

signed main(){
//	freopen("feast.in","r",stdin);
//	freopen("feast.out","w",stdout);
	int s,n;
	cin>>s>>n;
	for(int i=0; i<n; i++){
		int v,w,k;
		cin>>v>>w>>k;
		lol[w].push_back({v,k});
	}
	int st=1;
	for(int i=1; i<=s; i++){
		if(lol[i].empty()) continue;
		st^=1;
		sort(lol[i].rbegin(),lol[i].rend());
		for(int j=1; j<=s; j++) dp[st][j]=dp[st^1][j];
		for(int j=1; j<=s; j++){
			int idx=0;
			int now=1;
			int hhe=0;
			int cur=0;
			while(now*i<=j && hhe<lol[i].size()){
				cur+=lol[i][hhe].first;
				if(dp[st^1][j-(now*i)]+cur>dp[st][j]){
					dp[st][j]=dp[st^1][j-(now*i)]+cur;
				}
				now++;
				idx++;
				if(idx==lol[i][hhe].second){
					hhe++;
					idx=0;
				}
			}
		}
	}
	int ans=0;
	for(int i=1; i<=s; i++) ans=max(ans,dp[st][i]);
	cout<<ans<<'\n';
	return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:34:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |    while(now*i<=j && hhe<lol[i].size()){
      |                      ~~~^~~~~~~~~~~~~~

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