# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1127444 | heisenberg | Knapsack (NOI18_knapsack) | C++20 | 0 ms | 0 KiB |
#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[W] <<' ' ;
}
signed main() {
run_case() ;
return 0 ;
}