Submission #1317821

#	Time	Username	Problem	Language	Result	Execution time	Memory
1317821		Aratab	Knapsack (NOI18_knapsack)	C++20	0 / 100	1095 ms	332 KiB

knapsack

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

typedef long long ll;

const ll INF = (ll)(1e18) + 13;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int s, n;
    cin >> s >> n;
    int a[n][3];
    for (int i=0; i<n; i++) {
        for (int j=0; j<3; j++) {
            cin >> a[i][j];
        }
    }

    vector<ll> dp(s+5, -INF);
    dp[0] = 0;
    for (int i=s; i>=0; i--) {
        int x = 0;
        ll v = 0;
        queue<int> q;
        for (int j=0; j<n; j++) {
            int k = a[j][2];
            while (k--) {
                // deduct if exceeded
                while (x + a[j][1] > i) {
                    if (q.empty()) {
                        break;
                    }
                    int l = q.front(); q.pop();
                    x -= a[l][1];
                    v -= a[l][0];
                }

                if (x + a[j][1] > i) {
                    break;
                }
                x += a[j][1];
                v += a[j][0];
                q.push(j);

                if (dp[i-x] > -INF) {
                    // cerr << i << ' ' << x << ' ' << v << '\n';
                    dp[i] = max(dp[i], dp[i-x] + v);
                }
           }
        }
    }

    ll ans = 0;
    for (int i=0; i<=s; i++) {
        ans = max(ans, dp[i]);
    }

    cout << ans << '\n';
}

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