제출 #1183245

#제출 시각아이디문제언어결과실행 시간메모리
1183245Trn115Knapsack (NOI18_knapsack)C++17
100 / 100
89 ms8684 KiB
#include <bits/stdc++.h> #define int long long #define fi first #define se second #define all(v) v.begin(), v.end() using namespace std; using pii = pair<int, int>; int s, n; vector<vector<int>> val; vector<int> dp; signed main() { cin.tie(0)->sync_with_stdio(0); cin >> s >> n; val.resize(s + 1); while (n--) { int v, w, k; cin >> v >> w >> k; int x = 1; while (x <= k) { if (w * x <= s) val[w * x].push_back(v * x); k -= x; x <<= 1; } if (k && w * k <= s) val[w * k].push_back(v * k); } for (int i = 1; i <= s; ++i) { sort(all(val[i]), greater<int>()); int len = val[i].size(); val[i].insert(val[i].begin(), 0); for (int j = 1; j <= len; ++j) { val[i][j] += val[i][j - 1]; } } dp.assign(s + 1, 0); for (int i = 1; i <= s; ++i) { for (int j = s; j >= i; --j) { for (int k = 1; k < val[i].size(); ++k) { if (j >= i * k) { dp[j] = max(dp[j], dp[j - i * k] + val[i][k]); } else { break; } } } } cout << dp[s]; }
#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...