Submission #975870

#	Time	Username	Problem	Language	Result	Execution time	Memory
975870		vjudge1	Knapsack (NOI18_knapsack)	C++17	73 / 100	169 ms	262144 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;

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

	v.resize(n);
	w.resize(n);
	k.resize(n);
	dp.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]) dp[i][j] = max(dp[i][j], dp[i][j-w[i]] + v[i]);
			for (ll l = 1; j >= l * w[i] && l <= k[i]; l++) {
				dp[i][j] = max(dp[i][j], dp[i-1][j-l*w[i]] + l * v[i]);
			}
		}
	}

	// 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: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 24 / 24
• Subtask 5: 0 / 27