Submission #1131886

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131886		ngtlong	Knapsack (NOI18_knapsack)	C++20	49 / 100	5 ms	328 KiB

knapsack

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

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

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

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

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

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

            for (int currentWeight = mod; currentWeight <= maxWeight; currentWeight += weight) {
                int index = currentWeight / weight;
                int 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];
}

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

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

    int maxWeight, n;
    cin >> maxWeight >> n;

    for (int 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: 0 / 24
• Subtask 5: 0 / 27