Submission #1096638

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096638		dchang0524	Knapsack (NOI18_knapsack)	C++17	49 / 100	5 ms	764 KiB

knapsack

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;


int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int S, N;
    cin >> S >> N;
    vector<ll> dp(S+1);
    unordered_map<int ,multiset<ll>> items; //<weight, multiset of values>
    for (int i = 0; i<N; i++) {
        ll V, W, K;
        cin >> V >> W >> K;

        int maxQ = S/W;
        while (items[W].size() < maxQ && K>0) {
            items[W].insert(V);
            K--;
        }
        while (items[W].size() == maxQ && K>0 && V > *items[W].begin()) {
            items[W].erase(*items[W].begin());
            items[W].insert(V);
            K--;
        }
    }


    // Converting multiset to a vector
    vector<vector<ll>> choices(S + 1);
    for (int i = 1; i <= S; i++) {
        if (items.find(i) != items.end()) {
            choices[i].assign(items[i].rbegin(), items[i].rend());
        }
    }


    for (int i = 1; i<S+1; i++) {
        vector<ll> values = choices[i];
        for (int k = 0; k<values.size(); k++) {
            for (int x = S; x>=0; x--) {
                if (x-i >= 0) {
                    dp[x] = max(dp[x], dp[x-i] + values[k]);
                }
            }
        }
    }

    ll ans = 0;
    for (int x = 1; x<S+1; x++) {
        ans = max(ans, dp[x]);
    }
    cout << ans << "\n";
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:19:32: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   19 |         while (items[W].size() < maxQ && K>0) {
      |                ~~~~~~~~~~~~~~~~^~~~~~
knapsack.cpp:23:32: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   23 |         while (items[W].size() == maxQ && K>0 && V > *items[W].begin()) {
      |                ~~~~~~~~~~~~~~~~^~~~~~~
knapsack.cpp:42:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |         for (int k = 0; k<values.size(); k++) {
      |                         ~^~~~~~~~~~~~~~

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