Submission #650274

#	Time	Username	Problem	Language	Result	Execution time	Memory
650274		ono_de206	Knapsack (NOI18_knapsack)	C++14	29 / 100	3 ms	1876 KiB

knapsack

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

#define int long long

signed main(){
//	freopen("feast.in","r",stdin);
//	freopen("feast.out","w",stdout);
	int s,n;
	cin>>s>>n;
	vector<int> v(n),w(n),k(n);
	for(int i=0; i<n; i++) cin>>v[i]>>w[i]>>k[i];
	vector<vector<int>> dp(n+1,vector<int>(s+1,0));
	int lol[s+1];
	int st=1;
	for(int i=0; i<n; i++){
		st^=1;
		memset(lol,0,sizeof(lol));
		for(int j=1; j<=s; j++) dp[st][j]=dp[st^1][j];
		for(int j=w[i]; j<=s; j++){
			if(dp[st][j-w[i]]+v[i]>dp[st][j] && lol[j-w[i]]<k[i]){
				lol[j]=lol[j-w[i]]+1;
				dp[st][j]=dp[st][j-w[i]]+v[i];
			}
			if(dp[st^1][j-w[i]]+v[i]>dp[st][j]){
				lol[j]=1;
				dp[st][j]=dp[st^1][j-w[i]]+v[i];
			}
		}
	}
	int ans=0;
	for(int i=1; i<=s; i++) ans=max(ans,dp[st][i]);
	cout<<ans<<'\n';
	return 0;
}

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