Submission #1329501

#	Time	Username	Problem	Language	Result	Execution time	Memory
1329501		scalifrastico_098	Knapsack (NOI18_knapsack)	C++20	100 / 100	307 ms	444 KiB

knapsack

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

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