Submission #1223248

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223248		eduardmm	Knapsack (NOI18_knapsack)	C++20	73 / 100	1096 ms	2632 KiB

knapsack

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

int main(){

    cin.tie(0)->sync_with_stdio(0);

    int n, s;
    cin >> s >> n;

    vector<ll> v(n), w(n), k(n);
    for (int i = 0; i < n; ++i){
        cin >> v[i] >> w[i] >> k[i];
    }

    vector<ll> dp(s + 1, -1);
    dp[0] = 0;
    for (int i = 0; i < n; ++i){
        vector<ll> index(w[i], 3000);
        vector<deque<ll>> best(w[i]);
        for (int j = s; j >= 0; --j){
            int ind = j % w[i];
            if (index[ind] == 3000) index[ind] = j;
            while (index[ind] >= 0 && (j - index[ind])/w[i] <= k[i]){
                int z = index[ind];
                ll val = dp[z] + ((s - z)/w[i])*v[i];
                index[ind] -= w[i];
                while (dp[z] >= 0 && !best[ind].empty() && best[ind].back() < val){
                    best[ind].pop_back();
                }
                if (dp[z] >= 0) best[ind].push_back(val);
            }
            ll mult = ((s - j)/w[i])*v[i];
            ll u = dp[j] + mult;
            if (!best[ind].empty() && best[ind].front() == u) best[ind].pop_front();
            if (!best[ind].empty()){
                ll v = best[ind].front() - mult;
                dp[j] = max(dp[j], v);
            }
        }
    }

    ll ans = 0;
    for (int i = 0; i <= s; ++i) ans = max(ans, dp[i]);
    cout << ans << '\n';

    return 0;
}

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