Submission #1282153

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282153		Faisal_Saqib	Knapsack (NOI18_knapsack)	C++17	73 / 100	1095 ms	17680 KiB

knapsack

#include <iostream>
using namespace std;
#define ll long long
// #define int ll
const int N=1e5+100;
const int S=2005;
const ll inf=1e18;
int w[N],v[N],k[N];
ll dp[S],ad[S];
int l[S],r[S];
ll vec[S][S];
int cur[S][S];
int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int s,n;
    cin>>s>>n;
    for(int i=0;i<n;i++)
    {
        cin>>v[i]>>w[i]>>k[i];
        k[i]=min(2000,k[i]);
    }
    for(int i=0;i<n;i++)
    {
        for(int idp=0;idp<=s;idp++)
        {
            if(idp<w[i])
            {
                l[idp]=r[idp]=0;
                ad[idp]=0;
            }
            int x=idp%w[i],j=idp/w[i];
            vec[x][j]=dp[idp];
            {
                ad[x]+=v[i];
                while(l[x]<r[x] and cur[x][l[x]]<j-k[i])
                    l[x]++;
                vec[x][j]-=ad[x];
                while(l[x]<r[x] and vec[x][cur[x][r[x]-1]]<=vec[x][j])
                    r[x]--;
                cur[x][r[x]]=j;
                r[x]++;
                if(l[x]<r[x])
                    dp[idp]=vec[x][cur[x][l[x]]]+ad[x];
            }
        }
    }
    ll mx=0;
    for(int i=0;i<=s;i++)mx=max(mx,dp[i]);
    cout<<mx;
}

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