Submission #1145700

#TimeUsernameProblemLanguageResultExecution timeMemory
1145700poltanosKnapsack (NOI18_knapsack)C++20
100 / 100
66 ms34376 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const int inf = 1e18; // Try to accurately compute the time complexity // Also remember 1/1 + 1/2 + 1/3 + ... + 1/n = log(n) [approx] void solve(){ int limit, type_num; cin >> limit >> type_num; map<int, vector<pair<int, int>>> by_weight; for(int t = 0; t < type_num; t++){ int val, wt, amt; cin >> val >> wt >> amt; if(wt <= limit && amt > 0) by_weight[wt].push_back({val, amt}); } /* * best[i][j] contains the most value we can * get using j weight and the first i weight types */ vector<vector<int>> best(by_weight.size() + 1, vector<int> (limit + 1, -inf)); best[0][0] = 0; int at = 1; for(auto &[wt, items] : by_weight){ sort(items.begin(), items.end(), greater<pair<int, int>>()); for(int i = 0; i <= limit; i++){ best[at][i] = best[at - 1][i]; int copies = 0, type_at = 0, curr_used = 0, profit = 0; while((copies + 1)*wt <= i && type_at < items.size()){ copies++; profit += items[type_at].first; if(best[at - 1][i - copies*wt] != -inf){ best[at][i] = max(best[at][i], best[at - 1][i - copies*wt] + profit); } curr_used++; if(curr_used == items[type_at].second){ curr_used = 0; type_at++; } } } at++; } cout << *max_element(best.back().begin(), best.back().end()) << endl; } signed main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int t = 1; while(t--) solve(); 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...