Submission #858582

#	Time	Username	Problem	Language	Result	Execution time	Memory
858582		rob123bob	Knapsack (NOI18_knapsack)	C++17	73 / 100	1033 ms	10164 KiB

knapsack

#include <iostream>
#include <vector>

int main()
{
    int32_t count_of_unique_items, max_weight;
    std::cin >> max_weight >> count_of_unique_items;

    std::vector<int32_t> weights;
    std::vector<int32_t> prices;

    for (int32_t idx = 0; idx < count_of_unique_items; ++idx)
    {
        int32_t weight, price, count;
        std::cin >> price >> weight >> count;
        if (weight > max_weight)
        {
            continue;
        }
        count = std::min(count, max_weight / weight);

        // "Factorising" count to bits
        for (int32_t cur_bit = 1; cur_bit <= count; cur_bit *= 2)
        {
            weights.push_back(weight * cur_bit);
            prices.push_back(price * cur_bit);
            count -= cur_bit;
        }

        // Remained bits
        if (count > 0)
        {
            weights.push_back(weight * count);
            prices.push_back(price * count);
        }
    }

    size_t count_of_items_new = weights.size();
    // We just need an answer, so we dont need to store all data

    std::vector<std::vector<int64_t>> dp(2,
                                         std::vector<int64_t>(max_weight + 1, 0));

    for (size_t j = 1; j <= count_of_items_new; ++j)
    {
        for (int32_t weight = 1; weight <= max_weight; ++weight)
        {
            if (weights[j - 1] <= weight)
            {
                dp[1][weight] = std::max(dp[0][weight],
                                         dp[0][weight - weights[j - 1]] + prices[j - 1]);
            }
            else
            {
                dp[1][weight] = dp[0][weight];
            }
        }

        for (int32_t weight = 0; weight <= max_weight; ++weight)
        {
            dp[0][weight] = dp[1][weight];
        }
    }

    int64_t mmax = 0;
    for (int32_t idx = max_weight; idx >= 0; --idx)
    {
        mmax = std::max(mmax, dp[1][idx]);
    }

    std::cout << mmax << std::endl;
    return 0;

    // If we want to print taken elements
    // std::vector<std::vector<int64_t>> dp(count_of_items_new + 1,
    //                                      std::vector<int64_t>(max_weight + 1, 0));

    // for (size_t j = 1; j <= count_of_items_new; ++j)
    // {
    //     for (int32_t weight = 1; weight <= max_weight; ++weight)
    //     {
    //         if (weights[j - 1] <= weight)
    //         {
    //             dp[j][weight] = std::max(dp[j - 1][weight],
    //                                      dp[j - 1][weight - weights[j - 1]] + prices[j - 1]);
    //         }
    //         else
    //         {
    //             dp[j][weight] = dp[j - 1][weight];
    //         }
    //     }
    // }

    // for (int32_t idx = max_weight; idx >= 0; --idx)
    // {
    //     if (dp[count_of_items_new][idx])
    //     {
    //         std::cout << dp[count_of_items_new][idx] << std::endl;
    //         return 0;
    //     }
    // }

    // std::cout << 0 << std::endl;
    // return 0;
}

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