Submission #1134772

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134772		nikolashami	Knapsack (NOI18_knapsack)	C++20	73 / 100	1093 ms	1352 KiB

knapsack

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

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,sse2")

int a[(int)1e5][3],f[2001];

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

 	for(int i=0;i<n;++i){
 		cin>>a[i][1]>>a[i][0]>>a[i][2];
 		a[i][2]=min(a[i][2],m/a[i][0]);
 	}

	for(int i=0,j;i<n;++i){
		j=1;
		while(a[i][2]){
			int s=min(a[i][2],j);
			a[i][2]-=s;
			for(int k=m;k>=a[i][0]*s;--k)
				f[k]=max(f[k],f[k-a[i][0]*s]+a[i][1]*s);
			j*=2;
		}
	}

	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