Submission #718453

#	Time	Username	Problem	Language	Result	Execution time	Memory
718453		Sig0001	Knapsack (NOI18_knapsack)	C++17	0 / 100	6 ms	12244 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::array<int, 3>> items(n);  // [value, weight, num_items]
	for (auto& [v, w, k] : items)
		std::cin >> v >> w >> k;

	std::vector<std::vector<int>> items_by_weight(s + 1);

	/**
	 * Since the maximum weight is 2000, the number of items that can fit
	 * is at most floor(2000 / w_i) <= 2000
	 */
	for (auto &[v, w, k] : items) {
		// We can use at most floor(2000 / w) items
		k = std::min(k, 2000 / w - static_cast<int>(items_by_weight[w].size()));
		for (int i = 0; i < k; i++)
			items_by_weight[w].push_back(v);
	}

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

	/**
	 * dp[i][x]: Maximum value with i-item types and x-weight
	 */

	std::vector<std::vector<int64_t>> dp(items_by_weight.size(),
		std::vector<int64_t>(s + 1, 0));

	int64_t ans = 0;

	for (int i = 0; i < n; i++) {
		for (int x = 1; x <= s; x++) {
			dp[i + 1][x] = dp[i][x];
			int64_t sumByW = 0;
			for (int j = 0; j < items_by_weight[i].size(); j++) {
				// Here, we are fitting j + 1 items of weight i
				sumByW += items_by_weight[i][j];
				if (x < (j + 1) * i)
					break;
				dp[i + 1][x] = std::max(dp[i + 1][x],
					dp[i][x - (j + 1) * i] + sumByW);
				ans = std::max(ans, dp[i + 1][x]);
			}
		}
	}

	std::cout << ans << '\n';

	return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:51:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |    for (int j = 0; j < items_by_weight[i].size(); j++) {
      |                    ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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