Submission #1350294

#	Time	Username	Problem	Language	Result	Execution time	Memory
1350294		vjudge1	Knapsack (NOI18_knapsack)	C++20	100 / 100	680 ms	460 KiB

knapsack

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define pi pair

vector<ll> dp(3000,0);

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    ll s,n;
    cin>>s>>n;


    for(int i=1;i<=n;i++)
    {
        ll u,v,k;
        cin>>u>>v>>k;

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

            ll w = cnt * v;
            ll val = cnt*u;

            for(int j=s;j>=w;j--)
            {
                dp[j] = max(dp[j] , dp[j-w] + val);
            }
        }
    }

    cout<<dp[s];

}

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