Submission #1131891

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131891		ngtlong	Knapsack (NOI18_knapsack)	C++20	73 / 100	1096 ms	2836 KiB

knapsack

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

// Constants
const ll MAX_N = 1e5 + 5; // Maximum number of items

// Function to calculate the maximum value
ll knapsack(ll n, ll maxWeight, ll weights[], ll values[], ll quantities[]) {
    vector<ll> dp(maxWeight + 1, 0); // DP array for max value with given weight

    for (ll i = 1; i <= n; i++) {
        ll weight = weights[i];
        ll value = values[i];
        ll quantity = quantities[i];

        if (weight > maxWeight) continue; // Skip items heavier than the capacity

        // Modular optimization to handle bounded knapsack
        for (ll mod = 0; mod < weight; mod++) {
            deque<pair<ll, ll>> dq; // Stores pairs of (value, weight)

            for (ll currentWeight = mod; currentWeight <= maxWeight; currentWeight += weight) {
                ll index = currentWeight / weight;
                ll currentValue = dp[currentWeight] - index * value;

                // Maintain deque: Remove elements that are not optimal
                while (!dq.empty() && dq.back().first <= currentValue)
                    dq.pop_back();

                dq.emplace_back(currentValue, currentWeight);

                // Remove elements that exceed the quantity constraint
                if (!dq.empty() && dq.front().second < currentWeight - quantity * weight)
                    dq.pop_front();

                // Update DP with the maximum value
                dp[currentWeight] = dq.front().first + index * value;
            }
        }
    }

    return dp[maxWeight];
}

ll weights[MAX_N], values[MAX_N], quantities[MAX_N];

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

    ll maxWeight, n;
    cin >> maxWeight >> n;

    for (ll i = 1; i <= n; i++) {
        cin >> values[i] >> weights[i] >> quantities[i];
    }

    cout << knapsack(n, maxWeight, weights, values, quantities) << "\n";

    return 0;
}

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