Submission #1322762

#	Time	Username	Problem	Language	Result	Execution time	Memory
1322762		hamstpan	Knapsack (NOI18_knapsack)	C++20	100 / 100	104 ms	33032 KiB

knapsack

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int pref[2010][2010], dp[2010][2010];
int main() {
	int n, s;
	cin >> s >> n;
	vector<vector<pair<int, int>>> a(s + 1);
	for (int i = 0; i < n; ++i) {
		int v, w, k;
		cin >> v >> w >> k;
		a[w].push_back({ v, k });
	}
	for (int i = 1; i <= s; ++i) sort(a[i].rbegin(), a[i].rend());
	for (int i = 1; i <= s; ++i) {
		if (a[i].empty()) continue;
		int ctr = 1, term = 0, sz = a[i].size(), rem = 1;
		while (ctr <= s && term < sz) {
			pref[i][ctr] = pref[i][ctr - 1] + a[i][term].first;
			++ctr;
			++rem;
			if (rem > a[i][term].second) {
				rem = 1;
				++term;
			}
		}
	}
	for (int i = 1; i <= s; ++i) {
		//consider putting objects of weight i
		for (int j = 1; j <= s; ++j) dp[i][j] = dp[i - 1][j];
		for (int j = 1; j <= s; ++j) {
			for (int k = 1; i * k <= j; ++k) dp[i][j] = max(dp[i][j], dp[i - 1][j - i * k] + pref[i][k]);
		}
	}
	cout << dp[s][s];
}

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