Submission #1329776

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

knapsack

#include <bits/stdc++.h>
using namespace std;
#define ll long long
signed 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 u=1; u<=k; u++)
            {
                if(j+u*y>w)break;
                if(dp[j+u*y]<dp[j]+u*v)dp[j+u*y]=max(dp[j+u*y], dp[j]+u*v);
                else break;
            }
        }
    }
    ll u=0; for(ll i=0; i<=w; i++)u=max(dp[i], u); cout<<u<<endl;
}

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