Submission #1129225

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129225		jackofall718	Knapsack (NOI18_knapsack)	C++20	73 / 100	693 ms	327680 KiB

knapsack

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

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

    long long S, N;
    cin >> S >> N;

    // weight -> vector of values
    unordered_map<long long, vector<long long>> groups;
    groups.reserve(N);
    groups.max_load_factor(0.7f);

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

        // We cannot take more than floor(S / W) copies of this item anyway
        long long limit = S / W; 
        // So among K copies, we only need to keep min(K, limit) of them.
        long long take = min(K, limit);
        
        // Push those 'take' copies of value V into groups[W].
        // (Because subtask constraints allow S up to 2000, this is safe enough.)
        for(int c = 0; c < take; c++){
            groups[W].push_back(V);
        }
    }

    // Now, for each weight group, sort values in descending order and truncate
    // to at most floor(S / W) items (in case multiple lines gave the same weight).
    vector<long long> finalWeights, finalValues;
    finalWeights.reserve(S * 30); // just a small over-reservation
    finalValues.reserve(S * 30);

    for(auto &kv : groups) {
        long long w = kv.first;
        auto &vals = kv.second;

        sort(vals.begin(), vals.end(), greater<long long>());

        // cap again at floor(S / w) in case multiple input lines had the same weight
        long long limit = S / w;
        if((long long)vals.size() > limit) {
            vals.resize(limit);
        }

        // store in final arrays
        for(long long v : vals) {
            finalWeights.push_back(w);
            finalValues.push_back(v);
        }
    }

    // Now do a standard 0-1 knapsack on (finalWeights, finalValues)
    vector<long long> dp(S + 1, 0);

    for(int i = 0; i < (int)finalWeights.size(); i++) {
        long long w = finalWeights[i], val = finalValues[i];
        for(long long cap = S; cap >= w; cap--) {
            dp[cap] = max(dp[cap], dp[cap - w] + val);
        }
    }

    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