Submission #975883

#	Time	Username	Problem	Language	Result	Execution time	Memory
975883		vjudge1	Knapsack (NOI18_knapsack)	C++17	12 / 100	1 ms	348 KiB

knapsack

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

using ll = long long;

ll s, n;
vector<ll> v, w, k;
vector<vector<ll>> dp, add;

signed main() {
	cin >> s >> n;

	v.resize(n);
	w.resize(n);
	k.resize(n);
	dp.assign(n, vector<ll>(s + 1, 0LL));
	add.assign(n, vector<ll>(s + 1, 0LL));

	for (int i = 0; i < n; i++) {
		cin >> v[i] >> w[i] >> k[i];
	}

	for (int i = 0; i <= s; i++) {
		dp[0][i] = min(i / w[0], k[0]) * v[0]; 
	}

	for (int i = 1; i < n; i++) {
		for (int j = 0; j <= s; j++) {
			dp[i][j] = dp[i-1][j];
			if (j > w[i] && k[i] >= add[i][j-w[i]]+1 && dp[i][j-w[i]] + v[i] > dp[i][j]) {
				dp[i][j] = dp[i][j-w[i]] + v[i];
				add[i][j] = add[i][j-w[i]] + 1;
			}
		}
	}

	// for (int i = 0; i< n; i++) {
	// 	for (int j = 0; j <= s; j++) {
	// 		cout << dp[i][j] << ' ';
	// 	}
	// 	cout << '\n';
	// }

	ll ans = 0;

	for (int i = 0; i <= s; i++) {
		ans = max(ans, dp[n-1][i]);
	}

	cout << ans << '\n';
}

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