Submission #1304983

#	Time	Username	Problem	Language	Result	Execution time	Memory
1304983		2120minhdt	Knapsack (NOI18_knapsack)	C++20	73 / 100	1096 ms	616 KiB

knapsack

#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>

using namespace std;

typedef long long ll;

void solve() {
    int S, N;
    if (!(cin >> S >> N)) return;

    vector<ll> dp(S + 1, 0);
    vector<ll> next_dp(S + 1, 0);

    for (int i = 0; i < N; ++i) {
        int v, w;
        ll k;
        cin >> v >> w >> k;
        
        // Khối lượng tối đa thực tế có thể lấy
        k = min(k, (ll)S / w);

        // Duyệt qua từng số dư r từ 0 đến w-1
        for (int r = 0; r < w; ++r) {
            deque<int> dq;
            for (int q = 0; q * w + r <= S; ++q) {
                int j = q * w + r;
                
                // 1. Tính giá trị f(q) để đưa vào queue
                ll val = dp[j] - (ll)q * v;
                
                // 2. Duy trì hàng đợi đơn điệu giảm dần
                while (!dq.empty() && dp[dq.back() * w + r] - (ll)dq.back() * v <= val) {
                    dq.pop_back();
                }
                dq.push_back(q);
                
                // 3. Loại bỏ phần tử quá hạn (ngoài cửa sổ kích thước k)
                if (dq.front() < q - k) {
                    dq.pop_front();
                }
                
                // 4. Cập nhật giá trị mới từ phần tử tốt nhất ở đầu hàng đợi
                next_dp[j] = dp[dq.front() * w + r] + (ll)(q - dq.front()) * v;
            }
        }
        dp = next_dp; // Chuyển sang đồ vật tiếp theo
    }

    ll ans = 0;
    for (int i = 0; i <= S; ++i) ans = max(ans, dp[i]);
    cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    solve();
    return 0;
}

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