Submission #805719

#	Time	Username	Problem	Language	Result	Execution time	Memory
805719		fnuprince	Knapsack (NOI18_knapsack)	C++17	0 / 100	90 ms	262144 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
int obj[100000][3] ;
//int dp[2001][100001];
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<array<int,100001>> dp(s+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: 0 / 12
• Subtask 2: 0 / 17
• Subtask 3: 0 / 20
• Subtask 4: 0 / 24
• Subtask 5: 0 / 27