Submission #858582

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
858582	2023-10-08T23:07:55 Z	rob123bob	Knapsack (NOI18_knapsack)	C++17	73 / 100	1000 ms	10164 KB

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.0 / 12.0

#	Verdict	Memory	Grader output
1	Correct	348 KB	Output is correct
2	Correct	436 KB	Output is correct
3	Correct	348 KB	Output is correct
4	Correct	348 KB	Output is correct

Subtask #2
17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	1 ms	436 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	1 ms	344 KB	Output is correct
9	Correct	1 ms	344 KB	Output is correct
10	Correct	1 ms	348 KB	Output is correct

Subtask #3
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	1 ms	436 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	1 ms	344 KB	Output is correct
9	Correct	1 ms	344 KB	Output is correct
10	Correct	1 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	2 ms	348 KB	Output is correct
13	Correct	1 ms	436 KB	Output is correct
14	Correct	1 ms	348 KB	Output is correct
15	Correct	1 ms	348 KB	Output is correct
16	Correct	1 ms	344 KB	Output is correct
17	Correct	1 ms	432 KB	Output is correct
18	Correct	1 ms	348 KB	Output is correct
19	Correct	1 ms	436 KB	Output is correct
20	Correct	1 ms	348 KB	Output is correct

Subtask #4
24.0 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	436 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1 ms	436 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	1 ms	348 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	1 ms	344 KB	Output is correct
13	Correct	1 ms	344 KB	Output is correct
14	Correct	1 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	2 ms	348 KB	Output is correct
17	Correct	1 ms	436 KB	Output is correct
18	Correct	1 ms	348 KB	Output is correct
19	Correct	1 ms	348 KB	Output is correct
20	Correct	1 ms	344 KB	Output is correct
21	Correct	1 ms	432 KB	Output is correct
22	Correct	1 ms	348 KB	Output is correct
23	Correct	1 ms	436 KB	Output is correct
24	Correct	1 ms	348 KB	Output is correct
25	Correct	0 ms	348 KB	Output is correct
26	Correct	3 ms	348 KB	Output is correct
27	Correct	1 ms	348 KB	Output is correct
28	Correct	1 ms	348 KB	Output is correct
29	Correct	1 ms	348 KB	Output is correct
30	Correct	1 ms	352 KB	Output is correct
31	Correct	1 ms	352 KB	Output is correct
32	Correct	1 ms	352 KB	Output is correct
33	Correct	1 ms	352 KB	Output is correct
34	Correct	1 ms	356 KB	Output is correct

Subtask #5
0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	436 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1 ms	436 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	1 ms	348 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	1 ms	344 KB	Output is correct
13	Correct	1 ms	344 KB	Output is correct
14	Correct	1 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	2 ms	348 KB	Output is correct
17	Correct	1 ms	436 KB	Output is correct
18	Correct	1 ms	348 KB	Output is correct
19	Correct	1 ms	348 KB	Output is correct
20	Correct	1 ms	344 KB	Output is correct
21	Correct	1 ms	432 KB	Output is correct
22	Correct	1 ms	348 KB	Output is correct
23	Correct	1 ms	436 KB	Output is correct
24	Correct	1 ms	348 KB	Output is correct
25	Correct	0 ms	348 KB	Output is correct
26	Correct	3 ms	348 KB	Output is correct
27	Correct	1 ms	348 KB	Output is correct
28	Correct	1 ms	348 KB	Output is correct
29	Correct	1 ms	348 KB	Output is correct
30	Correct	1 ms	352 KB	Output is correct
31	Correct	1 ms	352 KB	Output is correct
32	Correct	1 ms	352 KB	Output is correct
33	Correct	1 ms	352 KB	Output is correct
34	Correct	1 ms	356 KB	Output is correct
35	Correct	44 ms	2260 KB	Output is correct
36	Execution timed out	1033 ms	10164 KB	Time limit exceeded
37	Halted	0 ms	0 KB	-

Submission #858582

Compilation message

Subtask #1 12.0 / 12.0

Subtask #2 17.0 / 17.0

Subtask #3 20.0 / 20.0

Subtask #4 24.0 / 24.0

Subtask #5 0 / 27.0

Subtask #1
12.0 / 12.0

Subtask #2
17.0 / 17.0

Subtask #3
20.0 / 20.0

Subtask #4
24.0 / 24.0

Subtask #5
0 / 27.0