Submission #916212

#	Time	Username	Problem	Language	Result	Execution time	Memory
916212		lamter	Knapsack (NOI18_knapsack)	C++17	73 / 100	1070 ms	1500 KiB

knapsack

#include <bits/stdc++.h>

const int M = 2000;

std::vector <std::pair <int, int>> items[M + 1];
int dp[M + 1];

int main(void) {
	std::ios_base::sync_with_stdio(0);
	std::cin.tie(nullptr);

	int S, n; std::cin >> S >> n;
	for (int i = 0; i < n; i += 1) {
		int v, w, k; std::cin >> v >> w >> k;
		items[w].emplace_back(v, std::min(k, S / w));
	}

	for (int w = 1; w <= S; w += 1) {
		std::sort(items[w].begin(), items[w].end(), std::greater <> ());
		for (auto [v, cnt] : items[w]) {
			int total = 0;
			for (int i = 1; i <= cnt and total <= S; i += 1) {
				for (int t = S; t >= w; t -= 1)
					dp[t] = std::max(dp[t], dp[t - w] + v);
				total += w;
			}
		}
	}

	std::cout << dp[S] << '\n';

	return 0^0;
}

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