Submission #718464

#	Time	Username	Problem	Language	Result	Execution time	Memory
718464		Sig0001	Knapsack (NOI18_knapsack)	C++17	100 / 100	58 ms	1672 KiB

knapsack

#include <bits/stdc++.h>

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	/**
	 * @brief Input
	 * s: Maximum Weight 1 <= s <= 2000
	 * n: Number of Items 1 <= n <= 100000 (1e5)
	 *
	 * v_i : Value of Item 1 <= v_i <= 1e6
	 * w_i : Weight of Item 1 <= w_i <= s
	 * k_i : Number of Items 1 <= k_i <= 1e9
	 */

	int s, n; std::cin >> s >> n;
	std::vector<std::vector<std::array<int, 2>>> items_by_weight(s + 1);

	for (int i = 0, v, w, k; i < n; ++i) {
		std::cin >> v >> w >> k;
		items_by_weight[w].push_back({v, k});
	}

	for (auto &v : items_by_weight)
		std::sort(v.begin(), v.end(), std::greater<>());

	std::vector<int64_t> dp(s + 1, 0), dpOld;

	for (int w = 1; w <= s; ++w) {
		auto &vals = items_by_weight[w];
		if (vals.empty()) continue;

		dpOld = dp;
		int64_t profit = 0;
		int totW = 0;

		for (std::size_t i = 0; i < vals.size(); ) {
			auto &[v, k] = vals[i];
			if (k == 0) { ++i; continue; }

			profit += v;
			totW += w;
			--k;

			if (totW > s) break;

			for (int x = 0; x <= s; x++) {
				if (totW <= x)
					dp[x] = std::max(dp[x], dpOld[x - totW] + profit);
			}
		}
	}

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

	return 0;
}

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