Submission #1254491

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254491		shakilinnovate	Knapsack (NOI18_knapsack)	C++20	73 / 100	1095 ms	412 KiB

knapsack

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

int main()
{
    ll S,N;     cin>>S>>N;

    vector<ll>dp(S+1,0);

    for(int i=0; i<N ; i++)
    {
        ll v,w,k;   cin>>v>>w>>k;

        for(ll cnt=1;k>0;cnt<<=1)
        {
            ll take=min(cnt,k);
            k-=take;

            ll tlt_v=v*take;
            ll tlt_w=w*take;

            for(ll j=S;j>=tlt_w;j--)
            {
                dp[j]=max(dp[j],dp[j-tlt_w]+tlt_v);
            }
        }
    }

    cout<<*max_element(dp.begin(),dp.end())<<endl;
}

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