Submission #1339651

#	Time	Username	Problem	Language	Result	Execution time	Memory
1339651		ghunglt	Knapsack (NOI18_knapsack)	C++20	73 / 100	1095 ms	472 KiB

knapsack

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

#define name "king2."
#define ll long long
#define vi vector<int>

const int N=1e7+5, mod=998244353, S=2005;
int n, s;
ll dp1[S], dp2[S];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    //freopen(name "in","r",stdin);
    //freopen(name "out","w",stdout);

    cin>>s>>n;
    for (int i=1;i<=n;i++){
        int v,w,c;
        cin>>v>>w>>c;

        if (w>s) continue;
        swap(dp1,dp2);
        
        for (int r=0;r<w;r++){
            deque<int> dq;

            for (int k=0;r+k*w<=s;k++){
                int j=r+k*w;

                ll val=dp1[j]-1ll*k*v;

                while (!dq.empty()) {
                    int last = dq.back();
                    int pos = r + last * w;
                    if (dp1[pos] - (ll)last * v <= val)
                        dq.pop_back();
                    else break;
                }
                
                dq.push_back(k);

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

                int best=dq.front();
                int pos=r+best*w;

                dp2[j]=dp1[pos]+1ll*(k-best)*v;
            }
        }
    }

    cout<<dp2[s];
    
    return 0;
}

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