Submission #888915

#	Time	Username	Problem	Language	Result	Execution time	Memory
888915		Perl32	Knapsack (NOI18_knapsack)	C++14	100 / 100	47 ms	3752 KiB

knapsack

//I wrote this code 4 u <3
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

const int INF = (int) 1e9 + 1e3;

const int maxN = 2024;
ll dp[maxN];
vector<pair<int, int>> srt[maxN];

signed main(int32_t argc, char *argv[]) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int W, n;
    cin >> W >> n;
    dp[0] = 0;
    for (int i = 0; i < n; ++i) {
        int s, w, k;
        cin >> s >> w >> k;
        if (w <= W) {
            srt[w].emplace_back(s, k);
        }
    }
    for (auto &x : srt) {
        sort(x.rbegin(), x.rend());
    }
    memset(dp, 0ll, sizeof dp);
    for (int i = 1; i <= W; ++i) {
        int id = 0, cur = 0;
        while (id < (int) srt[i].size() && cur <= W) {
            auto [v, k] = srt[i][id];
            for (int j = W; j >= i; --j) {
                dp[j] = max(dp[j], dp[j - i] + v);
            }
            if (!(--srt[i][id].second)) {
                id++;
            }
            cur += i;
        }
    }
    ll mx = 0;
    for (int i = 0; i <= W; ++i) {
        mx = max(mx, dp[i]);
    }
    cout << mx;
}
/*

 */

Compilation message (stderr)

knapsack.cpp: In function 'int main(int32_t, char**)':
knapsack.cpp:40:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   40 |             auto [v, k] = srt[i][id];
      |                  ^

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