Submission #1289519

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289519		kubinsgk8	Knapsack (NOI18_knapsack)	C++20	49 / 100	1093 ms	1864 KiB

knapsack

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

long long dp[102][2001];

long long value[101], w[101], cop[101];

long long n, s;


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

    cin>>s>>n;

    for(int i=1; i<=n; i++)
    {
      cin>>value[i]>>w[i]>>cop[i];
    }

    if(n==1)
    {
        cout<<min(s/w[1], cop[1])*value[1];
        return 0;
    }
    for(int i=1; i<=n; i++)
    {
        for(int sum=1; sum<=s; sum++)
        {
            dp[i][sum]=dp[i-1][sum];

            for(int k=1; k<=cop[i]; k++)
            {
                if(k*w[i]<=sum)
                    dp[i][sum]=max(dp[i][sum], dp[i-1][sum-w[i]*k]+value[i]*k);
            }
        }
    }

    cout<<dp[n][s];

    return 0;
}

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