Submission #1198197

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198197		almaharbas4	Knapsack (NOI18_knapsack)	C++20	12 / 100	1 ms	328 KiB

knapsack

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
    int n,k;
    cin>>k>>n;
    vector<int> val(n),w(n),cap(n);
    for(int i=0;i<n;i++)
    {
        cin>>val[i]>>w[i]>>cap[i];
    }
    vector<vector<ll>> dp(n+1,vector<ll>(k+1,-1));
    dp[0][0]=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=k;j++)
        {
            for(int a=1;a<=cap[i-1]&&j-a*w[i-1]>=0;a++)
            {
            if(dp[i-1][j-a*w[i-1]]!=-1)
            dp[i][j]=max(dp[i][j],dp[i-1][j-a*w[i-1]]+a*val[i-1]);
            else 
            dp[i][j]=max(dp[i][j],(ll)a*val[i-1]);
            }
        }
    }
    cout<<dp[n][k]<<endl;
    return 0;
}

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