Submission #1224874

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224874		builder_op	Knapsack (NOI18_knapsack)	C++20	73 / 100	1095 ms	2016 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;

constexpr int MAX_S = 2000;          // given in the statement
static int dp[MAX_S + 1];            // zero-initialised by the loader

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int S, N;
    if (!(cin >> S >> N)) return 0;

    vector<int> V(N), W(N);
    vector<long long> K(N);          // the count can be up to 1e9, keep as 64-bit

    for (int i = 0; i < N; ++i) {
        cin >> V[i] >> W[i] >> K[i];
        if (W[i] != 0) K[i] = min<long long>(K[i], S / W[i]); // never need more
    }

    /* ---- main loop ---- */
    for (int idx = 0; idx < N; ++idx) {
        int v = V[idx], w = W[idx];
        long long k = K[idx];

        for (long long p = 1; k > 0; p <<= 1) {
            int take = static_cast<int>(min<long long>(p, k));
            int wt   = w * take;          // ≤ 2 000 × 2 048 = 4 096 000 < 2^31
            int val  = v * take;          // ≤ 1 024 × 1 000 000 = 1 024 000 000

            /* 0/1 knapsack update */
            for (int s = S; s >= wt; --s)
                dp[s] = max(dp[s], dp[s - wt] + val);

            k -= take;
        }
    }

    cout << dp[S] << '\n';
    return 0;
}

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