Submission #916195

#	Time	Username	Problem	Language	Result	Execution time	Memory
916195		lamter	Knapsack (NOI18_knapsack)	C++17	73 / 100	1079 ms	2516 KiB

knapsack

#include <bits/stdc++.h>

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

	int S, n; std::cin >> S >> n;
	std::vector <std::vector <std::pair <int, int>>> items(S + 1);
	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));
	}

	std::vector <long long int> dp(S + 1);
	for (auto& it : items) {
		std::sort(it.begin(), it.end());
		std::reverse(it.begin(), it.end());
	}

	for (int w = 1; w <= S; w += 1) {
		for (const 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.back() << '\n';

	return 0^0;
}

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