Submission #670807

#	Time	Username	Problem	Language	Result	Execution time	Memory
670807		hqminhuwu	Knapsack (NOI18_knapsack)	C++14	73 / 100	1086 ms	2736 KiB

knapsack

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pii pair<long long, long long>
#define pb push_back
#define st first
#define nd second
using namespace std;
const int N = 100005;
const int inf = 1000000000;
ll maxx (ll a, ll b)
{
    if (a>b)
        return a;
    return b;
}
int n,s,v[N],g[N] ,k[N],dp[N];
int main()
{
    cin >> s >> n;
    for (int i=1;i<=n;i++)
        cin >> v[i] >> g[i] >> k[i],k[i]=min(k[i],s/g[i]+1);
    fill(dp+1,dp+s+2,-1);
    dp[0]=0;
    for (int i=1;i<=n;i++)
        for (int j=1;k[i]>0;j++)
        {
            ll t=min(k[i],j);
            k[i]-=j;
            ll f=t*g[i];
            for (int l=s;l>=f;l--)
            if (dp[l-f]>-1)
                dp[l]=maxx(dp[l],dp[l-f]+v[i]*t);
        }
    for (int i=1;i<=s;i++)
    {
        dp[i]=maxx(dp[i],dp[i-1]);
    }
    cout << dp[s];
    return 0;
}

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