Submission #571865

#TimeUsernameProblemLanguageResultExecution timeMemory
571865beabossKnapsack (NOI18_knapsack)C++14
73 / 100
514 ms262144 KiB
#include <bits/stdc++.h> using namespace std; int main() { int n, w; cin >> w >> n; vector<vector<int> > vals(n, vector<int>(3)); for (int i = 0; i < n; i++) cin >> vals[i][0] >> vals[i][1] >> vals[i][2]; vector<vector<int> > dp(n + 1, vector<int>(w + 1, 0)); for (int item = 0; item < n; item ++) { for (int we = w; we >= 0; we--) { int current = we; int used = 0; while (current <= w && used <= vals[item][2]) { dp[item + 1][current] = max(dp[item][we] + used*vals[item][0],dp[item + 1][current]); current += vals[item][1]; used++; } } } int ans = 0; for (auto val: dp[n]) ans = max(ans, val); cout << ans << 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...