Submission #1134774

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134774		nikolashami	Knapsack (NOI18_knapsack)	C++20	100 / 100	84 ms	2120 KiB

knapsack

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

struct s{int v,w,k;}a[(int)1e5];
vector<array<int,2>>b;
vector<int>v[2001];
int f[2001];

bool cmp(const s&a,const s&b){
	return(a.v>b.v);
}

int main(){
	int m,n;
	cin>>m>>n;

 	for(int i=0;i<n;++i){
 		cin>>a[i].v>>a[i].w>>a[i].k;
 		a[i].k=min(a[i].k,m/a[i].w);
 	}

 	sort(a,a+n,cmp);
 	for(int i=0;i<n;++i){
 		while(a[i].k--&&v[a[i].w].size()<=(m/a[i].w))
 			v[a[i].w].push_back(a[i].v);
 	}

 	for(int w=1;w<=m;++w)
 		for(int x:v[w])
 			b.push_back({x,w});

 	n=b.size();
 	for(int i=0;i<n;++i){
 		for(int j=m;j>=b[i][1];--j)
 			f[j]=max(f[j],f[j-b[i][1]]+b[i][0]);
 	}

 	cout<<*max_element(f,f+m+1);
}

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