Submission #734126

#	Time	Username	Problem	Language	Result	Execution time	Memory
734126		swapbeast	Knapsack (NOI18_knapsack)	C++14	73 / 100	1077 ms	18540 KiB

knapsack

//https://oj.uz/problem/view/NOI18_knapsack

#include<bits/stdc++.h>

using namespace std;
#define pb push_back
#define ll long long
#define MAXN 2001
ll dp[2][MAXN];
int main()
{
    int n,S;cin>>S>>n;
    int V[n],W[n],K[n];
    for(int i=0;i<n;i++)cin>>V[i]>>W[i]>>K[i];
    vector<ll>w,v;
    // log2 trick
    for(int i=0;i<n;i++)
    {
        int j=0;
        K[i]=min(K[i],S/W[i]);
        while(K[i])
        {
            if(K[i]>=(1<<j))
            {
                w.pb(1ll*W[i]*(1<<j));
                v.pb(1ll*V[i]*(1<<j));
                K[i]-=(1<<j);
            }else
            {
                w.pb(1ll*W[i]*K[i]);
                v.pb(1ll*V[i]*K[i]);
                K[i]=0;
            }
            j++;
        }
    }
    memset(dp,0,sizeof(dp));
    int m = w.size();
    for(int i=0;i<m;i++)
    {
        for(int j=0;j<=S;j++)
        {
            if(j+w[i]<=S)
                dp[(i+1)%2][j+w[i]]=max(dp[(i+1)%2][j+w[i]],v[i]+dp[i%2][j]);
            dp[(i+1)%2][j]=max(dp[(i+1)%2][j],dp[i%2][j]);
        }
    }

    cout<<dp[m%2][S];


}

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