제출 #1188006

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1188006		mehmetkagan	Knapsack (NOI18_knapsack)	C++20	73 / 100	1094 ms	488 KiB

knapsack

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

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int S, N;
    cin >> S >> N;
    vector<int> dp(S+1, 0);

    for (int i = 0; i < N; i++) {
        int V, W, K;
        cin >> V >> W >> K;

        // If effectively unbounded, do classic unbounded knapsack in O(S)
        if ((ll)W * K >= S) {
            for (int j = W; j <= S; j++) {
                dp[j] = max(dp[j], dp[j - W] + V);
            }
            continue;
        }

        // Otherwise do bounded knapsack with monotonic‐queue optimization
        // Process each residue class r = 0,1,...,W-1
        for (int r = 0; r < W; r++) {
            deque<pair<int,int>> dq;
            // We look at positions j = r + m*W (m=0,1,2,...) up to S
            for (int m = 0, j = r; j <= S; m++, j += W) {
                // f(m) = dp_prev[j] - m*V
                int fm = dp[j] - m * V;

                // push new m into deque, maintaining decreasing fm
                while (!dq.empty() && dq.back().second <= fm)
                    dq.pop_back();
                dq.emplace_back(m, fm);

                // pop front if outside window of size K+1
                while (!dq.empty() && dq.front().first < m - K)
                    dq.pop_front();

                // best is dq.front()
                dp[j] = dq.front().second + m * V;
            }
        }
    }

    // Answer is the maximum over all weights ≤ S
    cout << *max_element(dp.begin(), dp.end()) << "\n";
    return 0;
}

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