Submission #1264967

#TimeUsernameProblemLanguageResultExecution timeMemory
1264967canhnam357Knapsack (NOI18_knapsack)C++20
100 / 100
37 ms1608 KiB
#include <bits/stdc++.h> using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int s, n; cin >> s >> n; vector<vector<pair<int, int>>> a(s + 1); for (int i = 0; i < n; i++) { int v, w, k; cin >> v >> w >> k; a[w].emplace_back(v, k); } vector<int> dp(s + 1); for (int i = 1; i <= s; i++) { sort(a[i].rbegin(), a[i].rend()); int j = 0; for (int k = 1; k <= s / i; k++) { if (j == a[i].size()) break; if (a[i][j].second == 0) { j++; k--; continue; } a[i][j].second--; int v = a[i][j].first; for (int _ = s; _ >= i; _--) { dp[_] = max(dp[_], dp[_ - i] + v); } } } cout << *max_element(dp.begin(), dp.end()); return 0; }
#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...