제출 #1262988

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1262988		khanghb2006	Knapsack (NOI18_knapsack)	C++20	73 / 100	1095 ms	2872 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;
    cin >> S >> N;

    vector<ll> V(N), W(N), K(N);
    // Đọc theo định dạng bạn xác nhận: v w k
    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 xét quá nhiều món hơn khả năng chứa
        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 = 0;
    for (int c = 0; c <= S; ++c) if (dp[c] != NEG) ans = max(ans, dp[c]);
    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