Submission #659551

#	Time	Username	Problem	Language	Result	Execution time	Memory
659551		khshg	Knapsack (NOI18_knapsack)	C++14	12 / 100	27 ms	31700 KiB

knapsack

#include<bits/stdc++.h>

using namespace std;

#define int long long

int32_t main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int s, n;
	cin >> s >> n;
	vector<array<int, 2>> items[s + 1];
	for(int i = 0; i < n; ++i) {
		int v, w, k;
		cin >> v >> w >> k;
		if(k > 0)
			items[w].push_back({v, k});
	}
	for(int i = 1; i <= s; ++i) {
		sort(begin(items[i]), end(items[i]));
		reverse(begin(items[i]), end(items[i]));
	}
	int dp[s + 1][s + 1];
	for(int i = 0; i <= s; ++i) {
		for(int j = 0; j <= s; ++j) {
			dp[i][j] = -1e18;
		}
	}
	int ans = 0;
	dp[0][0] = 0;
	for(int i = 1; i <= s; ++i) {
		for(int j = 0; j <= s; ++j) {
			dp[i][j] = dp[i - 1][j];
		}
		int k = 0, sum = 0;
		for(int j = i; j <= s; j += i) {
			if(k == (int) items[i].size()) {
				break;
			}
			sum += items[i][k][0];
			--items[i][k][1];
			if(!items[i][k][1]) {
				++k;
			}
			for(int u = j; u <= s; ++u) {
				if(dp[i - 1][u - j] != (long long)-1e18) {
					dp[i][u] = max(dp[i][j], dp[i - 1][u - j] + sum);
				}
			}
		}
	}
	for(int i = 0; i <= s; ++i) {
		for(int j = 0; j <= s; ++j) {
			ans = max(ans, dp[i][j]);
		}
	}
	cout << ans << '\n';
	return 0;
}

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