Submission #734905

#	Time	Username	Problem	Language	Result	Execution time	Memory
734905		vjudge1	Knapsack (NOI18_knapsack)	C++17	100 / 100	51 ms	3684 KiB

knapsack

#include <bits/stdc++.h>

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

	int s, n; std::cin >> s >> n;

	/**
	 * When we get a new item, put the value, num_items in
	 * the vector of items with the same weight.
	 */

	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});
	}

	/**
	 * Sort the items of the same weight in descending order of value.
	 */
	for (auto &v : items_by_weight) {
		std::sort(v.begin(), v.end(), std::greater<>());
	}

	/**
	 * dp[x] = Maximum Profit with Weight x after using items of weight 1 to w
	 * dpOld[x] stores the corresponding values before using items of weight w
	 */
	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;  // If there are no items of weight w, skip

		dpOld = dp;  // Store the values of dp before using items of weight w
		int64_t profit = 0;  // Profit of the items of weight w
		int totW = 0;  // Total Weight of the items of weight w

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

			profit += v;  // Add the value of the item
			totW += w;  // Weight of the items of weight w increases by w
			--k;  // Current item can not be used again

			if (totW > s) break;  // If the total weight exceeds s, stop

			for (int x = totW; x <= s; 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