제출 #1271740

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1271740		pvb.tunglam	Knapsack (NOI18_knapsack)	C++20	100 / 100	37 ms	2884 KiB

knapsack

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int S, N;
    if (!(cin >> S >> N)) return 0;
    // buckets by weight: for weight w, store vector of pairs (value, count)
    vector<vector<pair<int, long long>>> bucket(S + 1);
    
    for (int i = 0; i < N; ++i) {
        int V, W; long long K;
        cin >> V >> W >> K; // Vi Wi Ki
        if (W > S) continue; // theo đề W <= S nhưng an toàn
        bucket[W].push_back({V, K});
    }
    
    // build list of unit-items after truncation by t_w = floor(S / w)
    struct Item { int w; int v; };
    vector<Item> items;
    items.reserve(S * 12); // ước lượng (S log S)
    
    for (int w = 1; w <= S; ++w) {
        if (bucket[w].empty()) continue;
        // sort types of this weight by value descending
        auto &vec = bucket[w];
        sort(vec.begin(), vec.end(), [](const auto &a, const auto &b){
            return a.first > b.first;
        });
        int need = S / w; // at most this many copies of weight w can be used
        for (auto &p : vec) {
            if (need <= 0) break;
            int val = p.first;
            long long cnt = p.second;
            long long take = min<long long>(cnt, need);
            // push `take` unit items (value = val, weight = w)
            for (long long t = 0; t < take; ++t) items.push_back({w, val});
            need -= (int)take;
        }
    }
    
    // 0/1 knapsack DP on items
    vector<ll> dp(S + 1, 0);
    for (auto &it : items) {
        int w = it.w, v = it.v;
        for (int j = S; j >= w; --j) {
            dp[j] = max(dp[j], dp[j - 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