제출 #1262968

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1262968		khanghb2006	Knapsack (NOI18_knapsack)	C++20	0 / 100	0 ms	324 KiB

knapsack

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

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

    int N, S;
    if (!(cin >> N >> S)) return 0;
    vector<int> V(N), W(N), K(N);
    for (int i = 0; i < N; ++i) cin >> V[i] >> W[i] >> K[i];

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

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

        // Trường hợp đặc biệt: w == 0
        if (w == 0) {
            if (k > 0 && v > 0) {
                long long add = 1LL * v * k;
                for (int c = 0; c <= S; ++c)
                    if (dp[c] != NEG) dp[c] += add;
            }
            // nếu v <= 0 thì lấy 0 món là tốt nhất, bỏ qua
            continue;
        }

        vector<long long> dp_old = dp;               // tách bạch trước/sau
        vector<long long> ndp(S + 1, NEG);

        int R = min(w - 1, S);
        for (int r = 0; r <= R; ++r) {
            deque<pair<long long,int>> dq;           // (value = f[t]-t*v, index=t)
            // j: số bội của w trong lớp dư r (idx = r + j*w)
            for (int j = 0; r + 1LL*j*w <= S; ++j) {
                int idx = r + j*w;

                // thêm ứng viên t = j vào dequeue (f[j] - j*v)
                long long val = dp_old[idx] - 1LL*j*v;
                while (!dq.empty() && dq.back().first <= val) dq.pop_back();
                dq.emplace_back(val, j);

                // cửa sổ chỉ giữ t in [j-k .. j]
                while (!dq.empty() && dq.front().second < j - k) dq.pop_front();

                // g[j] = max_{t in [j-k..j]} f[t] + (j-t)*v
                ndp[idx] = dq.front().first + 1LL*j*v;
            }
        }

        dp.swap(ndp);
    }

    cout << *max_element(dp.begin(), dp.end()) << '\n';
    return 0;
}

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