Submission #1262977

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

knapsack

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll NEG = (ll)-4e18;

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 Ý: nếu đề của bạn cho thứ tự khác (ví dụ W V K) thì đổi dòng đọc tương ứng.
    for (int i = 0; i < N; ++i) cin >> V[i] >> W[i] >> K[i];

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

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

        if (w == 0) {
            // nếu w==0 và v>0 thì tốt nhất lấy hết; nếu v<=0 thì không lấy
            if (v > 0 && k > 0) {
                ll add = v * k;
                for (int c = 0; c <= S; ++c)
                    if (dp[c] != NEG) dp[c] += add;
            }
            continue;
        }

        // không cần xét k > S/w (không thể bỏ quá S/w món cân nặng w trong 0..S)
        if (k > 0) k = min(k, (ll)(S / w));

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

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

                // chỉ push nếu trạng thái trước đó reachable
                if (dp_old[idx] != NEG) {
                    ll val = dp_old[idx] - 1LL * j * v;
                    while (!dq.empty() && dq.back().first <= val) dq.pop_back();
                    dq.emplace_back(val, j);
                }

                // pop nếu ngoài cửa sổ j - k
                while (!dq.empty() && dq.front().second < j - (int)k) dq.pop_front();

                if (!dq.empty()) {
                    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) if (dp[c] != NEG) ans = max(ans, dp[c]);
    if (ans == NEG) ans = 0; // chọn không lấy gì -> 0
    cout << ans << '\n';
    return 0;
}

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