Submission #1185439

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185439		GoBananas69	Knapsack (NOI18_knapsack)	C++20	0 / 100	1 ms	328 KiB

knapsack

#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
using namespace std;
typedef long long ll;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int s, n;
    cin >> s >> n;
    vector<ll> dp(s + 1, 0); // dp[j]: best value for capacity j

    // Process each item one by one.
    for (int i = 0; i < n; ++i) {
        int price, weight, count;
        cin >> price >> weight >> count;
        
        // If the item weight is larger than our knapSack capacity, skip.
        if (weight > s) continue;
        
        // We cannot use more than s/weight copies
        count = min(count, s / weight);

        // Process each residue modulo weight.
        // For every r (0 <= r < weight), j takes the form j = r + k * weight.
        for (int r = 0; r < weight; r++) {
            deque<int> dq;
            // k is the number of items used (0-indexed) along this residue.
            // j = r + k*weight must be within [0, s].
            for (int k = 0; r + k * weight <= s; k++) {
                int j = r + k * weight;
                
                // Value we want to optimize: 
                // f(k) = dp[j] - k * price.
                ll cur = dp[j] - (ll)k * price;
                
                // Remove indices from the front that are out of the allowed range (k - previous_index > count)
                while (!dq.empty() && dq.front() < k - count)
                    dq.pop_front();
                
                // Maintain the deque in decreasing order of dp[r + (index)*weight] - index*price.
                while (!dq.empty() && (dp[r + dq.back() * weight] - (ll)dq.back() * price) <= cur)
                    dq.pop_back();
                
                dq.push_back(k);
                
                // Update dp[j] using the best candidate from the deque.
                // Let t = dq.front(). Then for j = r + k*weight, we get:
                // dp[j] = dp[r + t*weight] + (k - t) * price.
                dp[j] = dp[r + dq.front() * weight] + (ll)(k - dq.front()) * price;
            }
        }
    }
    
    cout << dp[s] << "\n";
    return 0;
}

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