Submission #1248161

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248161		mohamedaziz	Knapsack (NOI18_knapsack)	C++20	100 / 100	50 ms	1880 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, T;
    cin >> S >> T;

    // Read all item types and group by weight:
    // by_weight[w] = vector of (value, count) for items of weight w
    map<int, vector<pair<int,int>>> by_weight;
    for (int t = 0; t < T; t++) {
        int v, w, cnt;
        cin >> v >> w >> cnt;
        if (w <= S && cnt > 0) {
            by_weight[w].emplace_back(v, cnt);
        }
    }

    // Prepare grouped & truncated lists:
    // Each entry in `groups` is (weight w, vector of best values)
    vector<pair<int, vector<int>>> groups;
    for (auto &kv : by_weight) {
        int w = kv.first;
        auto &items = kv.second;

        // Sort by descending value
        sort(items.begin(), items.end(),
             [](auto &a, auto &b){ return a.first > b.first; });

        // We only need up to floor(S / w) copies
        int cap = S / w;
        vector<int> bestVals;
        bestVals.reserve(cap);

        // Take counts from the highest-value items first
        for (auto &vc : items) {
            int v = vc.first;
            int c = vc.second;
            int take = min(c, cap - (int)bestVals.size());
            for (int i = 0; i < take; i++) {
                bestVals.push_back(v);
            }
            if ((int)bestVals.size() == cap) break;
        }

        if (!bestVals.empty()) {
            groups.emplace_back(w, move(bestVals));
        }
    }

    // DP arrays: dp_prev[s] = best value for weight exactly s using processed groups
    const ll NEG_INF = LLONG_MIN / 4;
    vector<ll> dp_prev(S+1, NEG_INF), dp_curr(S+1, NEG_INF);
    dp_prev[0] = 0;

    // Process each group
    for (auto &grp : groups) {
        int w = grp.first;
        auto &vals = grp.second;
        int m = vals.size();

        // Build prefix sums of the values: P[k] = sum of first k vals
        vector<ll> P(m+1, 0);
        for (int i = 0; i < m; i++) {
            P[i+1] = P[i] + vals[i];
        }

        // Reset dp_curr
        fill(dp_curr.begin(), dp_curr.end(), NEG_INF);

        // For each possible total weight s:
        for (int s = 0; s <= S; s++) {
            // Option 1: take 0 items from this group
            dp_curr[s] = dp_prev[s];

            // Option 2: take k items (1 ≤ k ≤ min(m, s/w))
            int maxK = min(m, s / w);
            for (int k = 1; k <= maxK; k++) {
                ll prev = dp_prev[s - k*w];
                if (prev != NEG_INF) {
                    dp_curr[s] = max(dp_curr[s], prev + P[k]);
                }
            }
        }

        // Move to next group
        dp_prev.swap(dp_curr);
    }

    // The answer is the maximum value for any weight ≤ S
    ll answer = *max_element(dp_prev.begin(), dp_prev.end());
    cout << answer << "\n";

    return 0;
}

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