Submission #884171

#	Time	Username	Problem	Language	Result	Execution time	Memory
884171		AleXutzZu	Knapsack (NOI18_knapsack)	C++17	100 / 100	103 ms	3756 KiB

knapsack

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

int main() {
    std::map<int, std::vector<std::pair<int, int>>> groups;

    int s, n;
    std::cin >> s >> n;
    for (int i = 1; i <= n; ++i) {
        int v, w, k;
        std::cin >> v >> w >> k;

        groups[w].emplace_back(v, k);
    }


    std::vector<long long> dp[2];
    dp[0].resize(s + 1, 0);
    dp[1].resize(s + 1, 0);

    int row = 0;

    for (auto &[weight, objects]: groups) {
        std::sort(objects.begin(), objects.end(), std::greater<>());

        for (int i = 0; i <= s; ++i) {
            dp[row][i] = dp[1 - row][i];

            int count = 0;
            int ptr = 0;
            int used = 0;
            long long profit = 0;

            while ((count + 1) * weight <= i && ptr < objects.size()) {
                count++;
                profit += objects[ptr].first;

                dp[row][i] = std::max(dp[row][i], dp[1 - row][i - count * weight] + profit);

                used++;
                if (used == objects[ptr].second) {
                    used = 0;
                    ptr++;
                }
            }
        }
        row = 1 - row;
    }

    row = 1 - row;

    std::cout << *std::max_element(dp[row].begin(), dp[row].end());
    return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:36:53: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |             while ((count + 1) * weight <= i && ptr < objects.size()) {
      |                                                 ~~~~^~~~~~~~~~~~~~~~

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