제출 #1127445

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1127445		heisenberg	Knapsack (NOI18_knapsack)	C++20	0 / 100	1098 ms	49700 KiB

knapsack

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

void run_case() {
    int S , N ;
    cin >> S >> N ;
    vector<long long> weights , values ;
    for(int i = 0 ; i < N ; ++i) {
        long long w , v , k ;
        cin >> w >> v >> k ;
        while(k--) {
            weights.push_back(w) ;
            values.push_back(v) ;
        }
    }
    N = weights.size() ;
    vector<long long> dp(S + 1,0) ;
    for(int i = N - 1 ; i >= 0 ; --i) {
        for(int capacity = S ; capacity >= 0 ; --capacity) {
            dp[capacity] = dp[capacity] ;
            if(capacity >= weights[i])
                dp[capacity] = max(dp[capacity - weights[i]] + values[i],dp[capacity]) ;
        }
    }
    cout << dp[S] <<' ' ;
}

signed main() {
    run_case() ;
    return 0 ;
}

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