Submission #1084200

#	Time	Username	Problem	Language	Result	Execution time	Memory
1084200		JohnnyVenturas	Knapsack (NOI18_knapsack)	C++17	100 / 100	85 ms	5464 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;

struct item {
    int weight, price, count;
};

int main() {
    int s, n;

    vector<vector<item>> hash_map(s + 1);
    cin >> s >> n;

    vector<item> items(n);

    for (int i = 0; i < n; ++i) {
        cin >> items[i].price >> items[i].weight >> items[i].count;
        hash_map[items[i].weight].push_back(items[i]);
    }

    for (auto &group : hash_map) {
        sort(group.begin(), group.end(), [](item &a, item &b) {
            if (a.price == b.price) {
                return a.count > b.count;
            }

            return a.price > b.price;
        });
    }
	
	vector<int> dp(s + 1, 0);

    for (int w = 0; w <= s; ++w) {
        for (int x = s; x >= 0; --x) {
            int count = 0, cur_count = 0, pos = 0, price_gain = 0;

            while (pos < hash_map[w].size()) {
                if (x - (count + 1) * w < 0)
                    break;

                if (cur_count == hash_map[w][pos].count) {
                    ++pos;
                    cur_count = 0;
                    continue;
                }

                price_gain += hash_map[w][pos].price;
                ++cur_count;
                ++count;

                dp[x] = max(dp[x], dp[x - count * w] + price_gain);
            }
        }
    }

    cout << dp[s] << "\n";
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:37:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<item>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |             while (pos < hash_map[w].size()) {
      |                    ~~~~^~~~~~~~~~~~~~~~~~~~
knapsack.cpp:11:37: warning: 's' is used uninitialized in this function [-Wuninitialized]
   11 |     vector<vector<item>> hash_map(s + 1);
      |                                   ~~^~~

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