Submission #908746

#	Time	Username	Problem	Language	Result	Execution time	Memory
908746		eysbutno	Knapsack (NOI18_knapsack)	C++11	100 / 100	84 ms	7504 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define all(x) begin(x), end(x)
#define pb push_back
#define ins insert
#define f first 
#define s second 

template<class T> bool smin(T& a, T b) {
    return b < a ? a = b, 1 : 0;
}
template<class T> bool smax(T& a, T b) {
    return b > a ? a = b, 1 : 0;
}
ll dp[2001], cnt[2001];
map<int, int> wt[2001];
int main() {
    cin.tie(0) -> sync_with_stdio(0);
    int s, n; cin >> s >> n;
    for (int i = 0; i < n; i++) {
        int v, w, k; cin >> v >> w >> k;
        wt[w][v] += k, cnt[w] += k;
    }
    for (int i = 1; i <= s; i++) {
        while (cnt[i] > s / i) {
            int dx = cnt[i] - (s / i);
            auto [k, v] = *begin(wt[i]);
            if (dx >= v) {
                cnt[i] -= v;
                wt[i].erase(k);
            } else {
                wt[i][k] -= dx;
                cnt[i] = 0;
            }
        }
    }
    for (int i = 1; i <= s; i++) {
        // only S/i items in this sack
        for (int j = s; j >= 0; j--) {
            // recalculate dp[j]
            ll cnt = 0, sum = 0;
            auto it = end(wt[i]);
            while (it != begin(wt[i])) {
                it = prev(it);
                auto [k, v] = *it;
                bool done = false;
                for (int l = 0; l < v; l++) {
                    ++cnt, sum += k;
                    if (j - i * cnt < 0) {
                        done = true; break;
                    }
                    smax(dp[j], sum + dp[j - i * cnt]);
                }
                if (done) break;
            }
        }
    }
    cout << dp[s] << '\n';
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:29:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   29 |             auto [k, v] = *begin(wt[i]);
      |                  ^
knapsack.cpp:47:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   47 |                 auto [k, v] = *it;
      |                      ^

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