Submission #851953

#	Time	Username	Problem	Language	Result	Execution time	Memory
851953		vancoding_way	Knapsack (NOI18_knapsack)	C++17	73 / 100	225 ms	262144 KiB

knapsack

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

/*
15 5
4 12 1
2 1 1
10 4 1
1 1 1
2 2 1

15

=================

20 3
5000 15 1
100 1 3
50 1 4

5400

The housewife take one of item 1, three of item 2 and two of item 3 for a total weight of
15 × 1 + 1 × 3 + 1 × 2 = 20 and a total value of 5000 × 1 + 100 × 3 + 50 × 2 = 5400.
*/
int main()
{
    ll S, N;
    cin >> S >> N;
    vector<ll> V(N+1, 0);
    vector<ll> W(N+1, 0);
    vector<ll> K(N+1, 0);
    
    for (int i = 1; i <= N; i++) {
        ll v,w,k;
        cin >> v >> w >> k;
        V[i] = v;
        W[i] = w;
        K[i] = k;
    }
    
    vector<vector<ll>> dp(S+1, vector<ll>(N+1, 0));
    
    for(ll s = 1; s <= S; s++) {
        for(ll n = 1; n <= N; n++) {
            dp[s][n] = dp[s][n-1];
            for(ll k = 1; k <= K[n]; k++) {
                if (W[n] * k <= s) {
                    if ((dp[s-W[n]*k][n-1] + V[n]*k) > dp[s][n]) {
                        dp[s][n] = dp[s-W[n]*k][n-1] + V[n]*k;
                    }
                } else {
                    break;
                }
            }
        }
    }
    
    /*
    for(int i = 0; i <= S; i++) {
        cout << "s = " << i << ":";
        for(ll j = 0; j <= N; j++) {
            cout << dp[i][j] << " ";
        }
        cout << endl;
    }
    */
    cout << dp[S][N];
    
    return 0;
    
}

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