Submission #1359227

#	Time	Username	Problem	Language	Result	Execution time	Memory
1359227		atif2077	Knapsack (NOI18_knapsack)	C++20	100 / 100	678 ms	452 KiB

knapsack

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

signed main() 
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    ll S, N;
    cin >> S >> N;

    vector<ll> dp(S + 1, 0);

    for (ll i = 0; i < N; i++)
    {
        ll V, W, K;
        cin >> V >> W >> K;

        ll cnt = 1;
        while (K > 0)
        {
            ll take = min(cnt, K);

            ll weight = W * take;
            ll value  = V * take;

            for (ll s = S; s >= weight; s--)
            {
                dp[s] = max(dp[s], dp[s - weight] + value);
            }

            K -= take;
            cnt <<= 1;
        }
    }

    cout << dp[S];
    return 0;
}

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