제출 #1134764

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1134764		nikolashami	Knapsack (NOI18_knapsack)	C++20	73 / 100	1096 ms	13992 KiB

knapsack

#include<bits/stdc++.h>
using namespace std;
 
struct s{int w,v,k;}a[(int)1e5];
int f[2001];
 
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);
	}
 
	vector<s>v;
	for(int i=0;i<n;++i){
		int j=1;
		while(a[i].k){
			int sl=min(a[i].k,j);
			a[i].k-=sl;
			v.push_back({a[i].w*sl,a[i].v*sl,0});
			j<<=1;
		}
	}
 
	n=v.size();
	for(int i=0;i<n;++i){
		for(int j=m;j>=v[i].w;--j)
			f[j]=max(f[j],f[j-v[i].w]+v[i].v);
	}
 
	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: 0 / 27