Submission #1167866

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167866		jmuzhen	Knapsack (NOI18_knapsack)	C++20	73 / 100	1095 ms	16792 KiB

knapsack

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

#define int long long

signed main() {
    int S, N;
    cin >> S >> N;

    vector<pair<int, int>> items; // (weight, value)

    for (int i = 0; i < N; i++) {
        int V, W, K;
        cin >> V >> W >> K;

        // use binary representation to break down K copies
        // into powers of 2 (+ remainder) to represent all possible quantities
        for (int p = 1; K > 0; p *= 2) {
            int take = min(p, K);
            items.push_back({take * W, take * V});
            K -= take;
        }
    }

    // run 0-1 knapsack
    vector<int> dp(S + 1, 0); // dp[i] = max value with max capacity i

    for (auto [w, val] : items) {
        if (w <= S) {
            for (int j = S; j >= w; j--) { // j = capacity
                dp[j] = max(dp[j], dp[j - w] + val);
            }
        }
    }

    cout << dp[S] << endl;
}

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