Submission #1131259

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131259		nlkn	Knapsack (NOI18_knapsack)	C++20	100 / 100	93 ms	2808 KiB

knapsack

// Source: https://usaco.guide/general/io

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

int main() {
	
	int m,n; cin >> m >>n;
	map<int,vector<pair<int,int>>> map;
	for(int i=0; i<n; i++){
		int v,w,k;cin>>v>>w>>k;
		map[w].push_back(make_pair(v,k));
	}
	vector<int> prev(m+1);
	for(auto i:map){
		int w=i.first;
		vector<int> curr(m+1);
		for(int j=0; j<=m; j++)curr[j]=prev[j];
		vector<pair<int,int>> pie=i.second;
		sort(pie.begin(),pie.end(),greater<pair<int, int>>());
		for(int j=0; j<=m; j++){
			int k=0,p=pie[0].second-1,sum=pie[0].first,wait=w;
			while(wait+j<=m){
				
				curr[wait+j]=max(curr[wait+j],prev[j]+sum);
		
				if(!p){
//cout<<p<<" "<<k<<endl;			
					k++;
		//	cout<<p<<" "<<k<<endl;
					if(k>=pie.size())break;
					p=pie[k].second;	
				}
				sum+=pie[k].first;
				wait+=w;
				p--;

			}
		}
		prev=curr;
	}
	int ans=0;
	for(int j=0; j<=m; j++){
		ans=max(ans,prev[j]);
	}
	cout<<ans;
}

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