Submission #1275201

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275201		prax27	Knapsack (NOI18_knapsack)	C++20	73 / 100	1004 ms	584 KiB

knapsack

// Compile: g++ -std=c++20 -O2 -march=native -pipe -o knap knap.cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

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

    int S, N;
    if (!(cin >> S >> N)) return 0;

    // dp[w] = best value for weight exactly w (we'll maintain for 0..S)
    vector<ll> dp(S + 1, 0), prev(S + 1);

    for (int i = 0; i < N; ++i) {
        ll V; int W; long long K;
        cin >> V >> W >> K;
        if (W > S) continue;                   // no copy fits
        // cap K to at most S / W, since more copies are useless
        K = min(K, (long long)(S / W));
        // copy current dp to prev (we read from prev, write into dp)
        prev = dp;

        // process residues r = 0..W-1
        for (int r = 0; r < W; ++r) {
            // we process positions: pos = r + m*W for m = 0,1,2,... while pos <= S
            deque<int> dq; // store positions (pos indices), but we only need to compute f(m)=prev[pos]-m*V
            int max_m = (S - r) / W; // last m such that r + m*W <= S

            for (int m = 0; m <= max_m; ++m) {
                int pos = r + m * W;
                // f(m) = prev[pos] - m*V
                ll f_m = prev[pos] - (ll)m * V;

                // maintain decreasing deque by f
                while (!dq.empty()) {
                    int back_pos = dq.back();
                    int back_m = (back_pos - r) / W;
                    ll f_back = prev[back_pos] - (ll)back_m * V;
                    if (f_back <= f_m) dq.pop_back();
                    else break;
                }
                dq.push_back(pos);

                // ensure the front is within window of size K: current m - front_m <= K
                while (!dq.empty()) {
                    int front_pos = dq.front();
                    int front_m = (front_pos - r) / W;
                    if ((long long)m - (long long)front_m > K) dq.pop_front();
                    else break;
                }

                // best candidate is at dq.front()
                if (!dq.empty()) {
                    int best_pos = dq.front();
                    int best_m = (best_pos - r) / W;
                    // dp[pos] = max(prev[pos], prev[best_pos] + (m - best_m) * V)
                    ll cand = prev[best_pos] + (ll)(m - best_m) * V;
                    if (cand > dp[pos]) dp[pos] = cand;
                    // else dp[pos] keeps previous value (which is prev[pos] copied earlier)
                }
            } // end for m
        } // end for r
    } // end for each item

    // the dp array stores best value for exact weight w; answer is maximum for weight <= S
    ll ans = 0;
    for (int w = 0; w <= S; ++w) ans = max(ans, dp[w]);
    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