Submission #1048827

#	Time	Username	Problem	Language	Result	Execution time	Memory
1048827		tamir1	Knapsack (NOI18_knapsack)	C++17	73 / 100	1064 ms	3920 KiB

knapsack

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,S,i,j,l,res,dp[2005],s[100001],w[100001],k[100001];
int main(){
	cin >> S >> n;
	for(i=1;i<=n;i++){
		cin >> s[i] >> w[i] >> k[i];
	}
	if(n==1){
		cout << min(k[1],S/w[1])*s[1];
		return 0;
	}
	for(i=1;i<=n;i++){
		for(l=S;l>=0;l--){
			for(j=1;j<=k[i];j++){
				if(l-w[i]*j<0) break;
				dp[l]=max(dp[l],dp[l-w[i]*j]+s[i]*j);
			}
		}
	}
	for(i=0;i<=S;i++) res=max(res,dp[i]);
	cout << res; 
}

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