Submission #659558

#	Time	Username	Problem	Language	Result	Execution time	Memory
659558		khshg	Knapsack (NOI18_knapsack)	C++14	100 / 100	51 ms	3716 KiB

knapsack

#include<bits/stdc++.h>

using namespace std;

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(w == 0 || k == 0) {
			return 1;
		}
		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][2];
	memset(dp, 0, sizeof(dp));
	int ans = 0;
	for(int i = 1; i <= s; ++i) {
		for(int j = 0; j <= s; ++j) {
			dp[j][1] = 0;
		}
		int k = 0, sum = 0;
		for(int j = i; j <= s && k < (int) items[i].size(); j += i) {
			sum += items[i][k][0];
			--items[i][k][1];
			if(!items[i][k][1]) {
				++k;
			}
			for(int u = j; u <= s; ++u) {
				dp[u][1] = max(dp[u][1], dp[u - j][0] + sum);
			}
		}
		for(int j = 0; j <= s; ++j) {
			dp[j][0] = max(dp[j][0], dp[j][1]);
		}
	}
	for(int i = 0; i <= s; ++i) {
		ans = max(ans, dp[i][0]);
	}
	cout << ans << '\n';
	return 0;
}

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