Submission #856565

#	Time	Username	Problem	Language	Result	Execution time	Memory
856565		bad_ian	Knapsack (NOI18_knapsack)	C++17	73 / 100	246 ms	262144 KiB

knapsack

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

int main()
{
    ll S, N;
    
    cin >> S >> N;
    
    vector<ll> vs(N + 1, 0);
    vector<ll> ws(N + 1, 0);
    vector<ll> ks(N + 1, 0);
    
    for(int i = 1; i <= N; i++){
        ll V;
        ll W;
        ll K;
        cin >> V >> W >> K;
        vs[i] = V;
        ws[i] = W;
        ks[i] = K;
    }
    
    vector<vector<ll>> dp(S + 1, vector<ll>(N + 1, 0));
    
    for(int s = 1; s <= S; s++){
        for(int i = 1; i <= N; i++){
            for(int k = 1; k <= ks[i]; k++){
                if(s >= (k * ws[i])){
                    dp[s][i] = max(dp[s][i], dp[s-(ws[i]*k)][i-1] + (vs[i]*k)) ;
                }else{
                    break;
                }
            }
            dp[s][i] = max(dp[s][i], dp[s][i-1]);
        }
    }
    
    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