Submission #891720

#TimeUsernameProblemLanguageResultExecution timeMemory
891720a5a7Knapsack (NOI18_knapsack)C++14
73 / 100
1069 ms1416 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; int main(){ int s, n; cin >> s >> n; vector<int> val(s+1, -1); val[0] = 0; for (int i = 0; i < n; i++){ int v, w, k; cin >> v >> w >> k; k = min(k, s/w); for (int j = s; j > -1; j--){ for (int x = 1; x * w <= j && x <= k; x++){ if (val[j-x*w] == -1) continue; val[j] = max(val[j-x*w]+x*v, val[j]); } } } cout << (*max_element(val.begin(), val.end())) << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...