Submission #1091675

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091675		artem_svl	Knapsack (NOI18_knapsack)	C++17	100 / 100	37 ms	3932 KiB

knapsack

#include <iostream>
#include <vector>
#include <set>
#include <string>
#include <algorithm>
#include <utility>
#include <unordered_map>
#include <cassert>
#include <queue>

typedef long long ll;

using namespace std;

struct Item {
    int value;
    int amount;

    bool operator<(const Item& other) const {
        return value > other.value;
    }
};

struct ShopItem {
    int weight;
    int value;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    int test = 1;
    // cin >> test;
    int s, n;
    while(test--) {
        cin >> s >> n;
        vector<int> cnt(s+1);
        for(int i = 1; i <= s; ++i) {
            cnt[i] = (s / i) + 1;
        }
        vector<vector<Item> > weights(s+1);
        int v, w, k;
        for(int _ = 0; _ < n; ++_) {
            cin >> v >> w >> k;
            weights[w].push_back({v, k});
        }
        vector<ShopItem> shopping_cart;
        for(int ww = 0; ww <= s; ++ww) {
            sort(weights[ww].begin(), weights[ww].end());
            int cur = 0;
            int i = 0;
            while(cur < cnt[ww] && i < weights[ww].size()) {
                int to_add = min(cnt[ww] - cur, weights[ww][i].amount);
                for(int _ = 0; _ < to_add; ++_) {
                    shopping_cart.push_back({ww, weights[ww][i].value});
                }
                cur += to_add;
                i++;
            }
        }
        vector<int> mvv(s+1);
        for(int i = 0; i < shopping_cart.size(); ++i) {
            int w_ = shopping_cart[i].weight;
            int v_ = shopping_cart[i].value;
            // cout << w_ << ' ' << v_ << '\n';
            for(int j = s; j >= w_; j--) {
                mvv[j] = max(mvv[j], mvv[j-w_] + v_);
            }
        }
        cout << mvv[s] << '\n';
    }
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:54:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Item>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |             while(cur < cnt[ww] && i < weights[ww].size()) {
      |                                    ~~^~~~~~~~~~~~~~~~~~~~
knapsack.cpp:64:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<ShopItem>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |         for(int i = 0; i < shopping_cart.size(); ++i) {
      |                        ~~^~~~~~~~~~~~~~~~~~~~~~

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