Submission #1131893

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131893		ngtlong	Knapsack (NOI18_knapsack)	C++20	73 / 100	1093 ms	2832 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAX_N = 1e5 + 5;

ll knapsack(ll n, ll maxWeight, ll weights[], ll values[], ll quantities[]) {
    vector<ll> dp(maxWeight + 1, 0);

    for (ll i = 1; i <= n; i++) {
        if (weights[i] > maxWeight) continue;
        for (ll mod = 0; mod < weights[i]; mod++) {
            deque<pair<ll, ll>> dq;
            for (ll w = mod; w <= maxWeight; w += weights[i]) {
                ll idx = w / weights[i];
                ll currVal = dp[w] - idx * values[i];
                while (!dq.empty() && dq.back().first <= currVal) dq.pop_back();
                dq.emplace_back(currVal, w);
                if (!dq.empty() && dq.front().second < w - quantities[i] * weights[i]) dq.pop_front();
                dp[w] = dq.front().first + idx * values[i];
            }
        }
    }

    return dp[maxWeight];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    ll n, maxWeight, weights[MAX_N], values[MAX_N], quantities[MAX_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