Submission #1219970

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219970		brito.joao	Knapsack (NOI18_knapsack)	C++20	37 / 100	1 ms	328 KiB

knapsack

#include <iostream>
#include <vector>
#include <algorithm>

int knapsack(int S, const std::vector<std::tuple<int, int, int>>& items) {
    std::vector<int> dp(S + 1, 0);

    for (const auto& [value, weight, count] : items) {
        int k = count;
        int mul = 1;

        while (k > 0) {
            int take = std::min(mul, k);
            int total_value = take * value;
            int total_weight = take * weight;

            for (int j = S; j >= total_weight; --j) {
                dp[j] = std::max(dp[j], dp[j - total_weight] + total_value);
            }

            k -= take;
            mul <<= 1; // multiply by 2
        }
    }

    return *std::max_element(dp.begin(), dp.end());
}

int main() {
    int S, N;
    std::cin >> S >> N;

    std::vector<std::tuple<int, int, int>> items(N);
    for (int i = 0; i < N; ++i) {
        int v, w, k;
        std::cin >> v >> w >> k;
        items[i] = {v, w, k};
    }

    std::cout << knapsack(S, items) << '\n';
    return 0;
}

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