Submission #1335419

#	Time	Username	Problem	Language	Result	Execution time	Memory
1335419		atombulul	Knapsack (NOI18_knapsack)	C++17	73 / 100	1095 ms	472 KiB

knapsack

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

#define ll long long
const int SMAX = 2005;

ll dp[SMAX], olddp[SMAX];

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

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

    while(N--){
        ll v,w,k;
        cin >> v >> w >> k;

        if(w > S) continue;

        memcpy(olddp, dp, sizeof(dp));

        for(int r=0;r<w;r++){
            deque<int> dq;

            for(int t=0, j=r; j<=S; t++, j+=w){

                ll val = olddp[j] - t*v;

                while(!dq.empty() &&
                     olddp[r + dq.back()*w] - dq.back()*v <= val)
                    dq.pop_back();

                dq.push_back(t);

                while(!dq.empty() && dq.front() < t-k)
                    dq.pop_front();

                int best = dq.front();
                dp[j] = olddp[r + best*w] + (t-best)*v;
            }
        }
    }

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

    cout<<ans<<"\n";
}

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