Submission #976014

#	Time	Username	Problem	Language	Result	Execution time	Memory
976014		vjudge1	Knapsack (NOI18_knapsack)	C++17	12 / 100	3 ms	3420 KiB

knapsack

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
using namespace std;

signed main (){
	int s,n; cin >> s >> n;
	pair<int,int> dp[n+1][s+1];
	int w[n+1],h[n+1],k[n+1];
	memset(dp,0,sizeof dp);
	for(int i =1;i<=n;i++){
		cin >> h[i] >> w[i] >> k[i];
	}
	
	for(int i = 1;i<=n;i++){
		for(int j = 1;j<=s;j++){
			int tmp = 0,con = 0;
			if(j - w[i] >= 0){
				tmp = dp[i][j-w[i]].fi + h[i];
				con = dp[i][j-w[i]].se + 1;
			}
			
			
			dp[i][j].fi = max(dp[i][j-1].fi,dp[i-1][j].fi);
			if(dp[i][j].fi == dp[i][j-1].fi) dp[i][j].se = dp[i][j-1].se;
			else dp[i][j].se = 0;
			if(con <= k[i]){
				if(max(dp[i][j].fi,tmp) == tmp){
					dp[i][j].fi = tmp;
					dp[i][j].se = con;
				} 
			} else{
				dp[i][j].fi += dp[i-1][j - k[i]*w[i]].fi - dp[i-1][j - k[i]*w[i] - 1].fi;
			}
			
//			cout << dp[i][j].fi << " ";
		}
//		cout << endl;
	}
	cout << dp[n][s].fi << endl;
	
	return 0;
}

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