Submission #856556

#	Time	Username	Problem	Language	Result	Execution time	Memory
856556		bad_ian	Knapsack (NOI18_knapsack)	C++17	17 / 100	2 ms	1968 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++){
            if(s >= ws[i]){
                dp[s][i] = max(dp[s][i], dp[s-ws[i]][i-1] + vs[i]) ;
            }
            dp[s][i] = max(dp[s][i], dp[s][i-1]);
        }
    }
    
    cout << dp[S][N];
    
    return 0;
}

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