제출 #1197236

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1197236		tin_le	Knapsack (NOI18_knapsack)	C++20	37 / 100	5 ms	8520 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
static const ll INF = (1LL<<60);

// Maximum S is 2000, so each residue class queue needs at most ceil(2001/1)=2001 slots
// but in general ceil(S/1)=S+1 is enough.
static int qbuf[2001][2005];
static int ql[2001], qr[2001];
static int seen[2001], timer = 1;

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

    int S, N;
    cin >> S >> N;

    vector<ll> dp(S+1, -INF), next_dp;
    dp[0] = 0;

    for(int it=0; it<N; it++){
        ll v,w,k;
        cin >> v >> w >> k;
        timer++;  // mark all residue‐classes fresh
        next_dp = dp;

        // For each residue r = 0..w-1 we will maintain a sliding-window maximum
        // in qbuf[r] as a circular buffer [ql[r], qr[r]).
        for(int r=0; r<w; r++){
            seen[r] = timer;   // mark as initialized
            ql[r] = qr[r] = 0;
        }

        // We unroll get_score(i,j)=dp[j]+((i-j)/w)*v as
        //  dp[j] + ((i - j)/w)*v  =  dp[j] + ((i-r)/w - (j-r)/w)*v
        // with i%w = j%w = r => (i-j)/w = (i-r)/w - (j-r)/w.  But simplest is:
        //   let t = (i-r)/w, then score = dp[j] + t*v  where j = r + q*w.
        // We just inline the original formula and rely on compiler to optimize.

        for(int i=0; i<=S; i++){
            int r = i % w;
            // lazy init check
            if(seen[r] != timer){
                seen[r] = timer;
                ql[r] = qr[r] = 0;
            }
            // pop front if out of window [i-k*w .. i]
            int limit = i - int(k*w);
            while(ql[r] < qr[r] && qbuf[r][ql[r]] < limit) 
                ql[r]++;

            // compute current candidate index i
            // now push i into back, maintaining monotonicity by score
            // strictly inline get_score
            auto score_i = dp[i];
            // pop back while new score >= back's score
            while(ql[r] < qr[r]){
                int j = qbuf[r][qr[r]-1];
                // (i-j)/w * v = ((i-j)/w)*v
                ll score_j = dp[j] + ll((i - j)/w)*v;
                ll s_i = dp[i] + ll((i - i)/w)*v; // = dp[i]
                if(s_i >= score_j) qr[r]--;
                else break;
            }
            qbuf[r][qr[r]++] = i;

            // now front holds index j maximizing dp[j] + ((i-j)/w)*v
            int j_best = qbuf[r][ql[r]];
            ll best_score = dp[j_best] + ll((i - j_best)/w)*v;
            next_dp[i] = max(next_dp[i], best_score);
        }

        dp.swap(next_dp);
    }

    ll ans = 0;
    for(ll x: dp) if(x>ans) ans = x;
    cout << ans << "\n";
    return 0;
}

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