Submission #1096603

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096603		dchang0524	Knapsack (NOI18_knapsack)	C++17	0 / 100	1 ms	604 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 ((int)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--;
        }
    }

    vector<vector<ll>> choices(S+1, vector<ll>());
    for (int i = 1; i<S+1; i++) {
        while (items[i].size()>0) {
            auto it = --items[i].end();
            choices[i].push_back(*it);
            items[i].erase(*it);
        }
    }

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

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

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