Submission #650272

#	Time	Username	Problem	Language	Result	Execution time	Memory
650272		ono_de206	Knapsack (NOI18_knapsack)	C++14	0 / 100	1 ms	212 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=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];
			}
		}
	}
	cout<<dp[st][s]<<'\n';
	return 0;
}

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