Submission #805717

#	Time	Username	Problem	Language	Result	Execution time	Memory
805717		fnuprince	Knapsack (NOI18_knapsack)	C++17	73 / 100	163 ms	262144 KiB

knapsack

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

int main() {
	int s, n; cin >> s >> n;
	vector<array<int,3>> obj(n);
	for (int i = 0; i < n; i++) cin >> obj[i][0] >> obj[i][1] >> obj[i][2];
	vector<vector<int>> dp(s+1,vector<int>(n+1));
	for (int i = 0; i < n+1; i++) dp[0][i] = 0;
	for (int i = 0; i < s+1; i++) {
		for (int j = 0; j < n; j++) {
			if (i-obj[j][1] >= 0) {
				if (dp[i-obj[j][1]][j+1] < obj[j][2]) {
					if (dp[i][0] < dp[i-obj[j][1]][0]+obj[j][0]) {
						dp[i] = dp[i-obj[j][1]];
						dp[i][0] += obj[j][0];
						dp[i][j+1]++;
					}
					else if (dp[i][0] == dp[i-obj[j][1]][0]+obj[j][0] && dp[i-obj[j][1]][j+1]+1<dp[i][j+1]) {
						dp[i] = dp[i-obj[j][1]];
						dp[i][0] += obj[j][0];
						dp[i][j+1]++;
					}
				}
			}
		}
	}
	int ans = 0;
	for (int i = 0; i < s+1; i++) ans = max(ans,dp[i][0]);
	cout << ans << endl;
}

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