Submission #1275200

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275200		prax27	Knapsack (NOI18_knapsack)	C++20	73 / 100	1091 ms	25356 KiB

knapsack

// Compile with: g++ -std=c++20 -O2 -pipe -march=native -o knap knap.cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int S; int N;
    if (!(cin >> S >> N)) return 0;
    
    struct Item { int w; ll v; };
    vector<Item> items;
    items.reserve(N * 4); // heuristic
    
    for (int i = 0; i < N; ++i) {
        ll V; int W; long long K;
        cin >> V >> W >> K;
        if (W > S) {
            // if single item's weight > capacity, none of its copies fit
            continue;
        }
        // Cap maximum usable copies by capacity: at most S / W copies can ever be taken
        long long usable = min(K, (long long)(S / W));
        long long take = 1;
        while (usable > 0) {
            long long cur = min(take, usable);
            int newW = int(cur * W);
            ll newV = V * cur;
            // newW <= S by construction because cur <= usable <= S/W
            items.push_back({ newW, newV });
            usable -= cur;
            take <<= 1;
        }
    }
    
    // 0/1 knapsack on constructed items
    vector<ll> dp(S + 1, 0);
    for (const auto &it : items) {
        int w = it.w;
        ll v = it.v;
        for (int cap = S; cap >= w; --cap) {
            ll cand = dp[cap - w] + v;
            if (cand > dp[cap]) dp[cap] = cand;
        }
    }
    
    // answer is max value for capacity <= S (dp[S] already holds max for S)
    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