Submission #957372

#	Time	Username	Problem	Language	Result	Execution time	Memory
957372		Dipa	Knapsack (NOI18_knapsack)	C++14	100 / 100	115 ms	4220 KiB

knapsack

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MOD = 1e9 + 7;


int main(int argc, char const *argv[])
{
    int S, N; cin >> S >> N;

    map<int, vector<pair<int, int>>> m;



    vector<pair<int, int>> eff;
    for (int i  = 0; i < N; i++) {
        int v, w, k;
        cin >> v >> w >> k;

        m[w].push_back({v, k});
    }

    

    for (auto &[w, vec]: m) {
        sort(vec.begin(), vec.end());
    }




    for (auto &[w, vec]: m) {
        int limit = S/w;
        while (limit > 0 && vec.size() > 0) {
            --limit;
            eff.push_back({vec.back().first, w});
            --vec.back().second;

            if (vec.back().second == 0) vec.pop_back();
        }
    }



    ll dp[S + 1]{0};
    for (auto &[v, w]: eff) {
        for (int i = S; i >= 0; --i) {
            if (i - w < 0) continue;

            dp[i] = max(dp[i], dp[i - w] + v);
        }
    }

    ll ans = 0;
    for (int i = 0; i <= S; ++i) {
        ans = max(ans, dp[i]);
    }

    cout << ans << '\n';
    return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'int main(int, const char**)':
knapsack.cpp:28:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   28 |     for (auto &[w, vec]: m) {
      |                ^
knapsack.cpp:35:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   35 |     for (auto &[w, vec]: m) {
      |                ^
knapsack.cpp:49:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   49 |     for (auto &[v, w]: eff) {
      |                ^

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