제출 #1224875

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1224875		builder_op	Knapsack (NOI18_knapsack)	C++20	100 / 100	35 ms	2888 KiB

knapsack

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

// ---------- constants ----------
constexpr int MAX_S = 2000;            // 1 ≤ S ≤ 2000

// ---------- helpers ----------
struct ItemType {
    int v;             // value  (≤ 1 000 000)
    int w;             // weight (1 … S)
    long long k;       // copies (≤ 1e9)
};

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

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

    /* ---- 1. read & bucket by weight ---- */
    vector<vector<pair<int,long long>>> bucket(S + 1);     // bucket[w] = list of (value, copies)

    for (int i = 0; i < N; ++i) {
        ItemType it;
        cin >> it.v >> it.w >> it.k;
        if (it.w > S) continue;                            // too heavy, ignore
        long long cap = S / it.w;                          // we never need more than this many copies
        if (cap == 0) continue;
        if (it.k > cap) it.k = cap;
        bucket[it.w].push_back({it.v, it.k});
    }

    /* ---- 2. keep only the best S/w copies for each weight ---- */
    struct Copy { int v, w; };                             // one concrete copy
    vector<Copy> copies;
    copies.reserve(15200);                                 // upper bound

    for (int w = 1; w <= S; ++w) {
        if (bucket[w].empty()) continue;
        int lim = S / w;                                   // maximum copies of weight w we can ever carry

        auto &vec = bucket[w];
        sort(vec.begin(), vec.end(),                      // sort by value descending
             [](auto &a, auto &b) { return a.first > b.first; });

        int taken = 0;
        for (auto [v, k] : vec) {
            if (taken == lim) break;
            int cnt = static_cast<int>(min<long long>(k, lim - taken));
            taken += cnt;
            while (cnt--) copies.push_back({v, w});       // push each copy individually
        }
    }

    /* ---- 3. 0/1 knapsack with at most 15 200 items ---- */
    static int dp[MAX_S + 1];                              // zero-initialised

    for (const auto &cp : copies) {
        int w = cp.w, v = cp.v;
        for (int s = S; s >= w; --s)
            dp[s] = max(dp[s], dp[s - w] + v);
    }

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

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