Submission #1262973

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262973		khanghb2006	Knapsack (NOI18_knapsack)	C++20	0 / 100	0 ms	324 KiB

knapsack

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

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

    int N;
    int S;
    if (!(cin >> N >> S)) return 0;

    vector<ll> V(N), W(N), K(N);
    // LƯU Ý: thứ tự đọc V W K theo file đề; nếu đề của bạn khác (W V K) đổi lại ở đây.
    for (int i = 0; i < N; ++i) cin >> V[i] >> W[i] >> K[i];

    const ll NEG = (ll)-4e18;
    vector<ll> dp(S + 1, NEG);
    dp[0] = 0;

    for (int i = 0; i < N; ++i) {
        ll w = W[i], v = V[i], k = K[i];

        // trường hợp w == 0: nếu v > 0 thì lấy hết k; nếu v <= 0 thì bỏ (không lấy)
        if (w == 0) {
            if (v > 0 && k > 0) {
                ll add = v * k;
                for (int c = 0; c <= S; ++c)
                    if (dp[c] != NEG) dp[c] += add;
            }
            continue;
        }

        vector<ll> dp_old = dp;
        vector<ll> ndp(S + 1, NEG);

        int R = (int)min((ll)w - 1, (ll)S);
        for (int r = 0; r <= R; ++r) {
            deque<pair<ll,int>> dq; // pair: (value = dp_old[idx] - j*v, j)
            for (int j = 0;; ++j) {
                int idx = r + j * (int)w;
                if (idx > S) break;

                ll base = dp_old[idx];
                ll val = (base == NEG) ? (NEG) : (base - 1LL * j * v);

                // maintain deque decreasing by .first
                while (!dq.empty() && dq.back().first <= val) dq.pop_back();
                dq.emplace_back(val, j);

                // pop front if out of window > k
                while (!dq.empty() && dq.front().second < j - (int)k) dq.pop_front();

                if (!dq.empty()) {
                    // ndp[idx] = max_{t in [j-k..j]} dp_old[r + t*w] + (j-t)*v
                    ndp[idx] = dq.front().first + 1LL * j * v;
                } else {
                    ndp[idx] = NEG;
                }
            }
        }

        dp.swap(ndp);
    }

    ll ans = NEG;
    for (int c = 0; c <= S; ++c) ans = max(ans, dp[c]);
    cout << (ans == NEG ? 0 : ans) << '\n';
    return 0;
}

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