Submission #669833

#TimeUsernameProblemLanguageResultExecution timeMemory
669833rv4102Knapsack (NOI18_knapsack)C++17
100 / 100
127 ms3708 KiB
#include <iostream> #include <vector> #include <algorithm> using namespace std; int main(){ int capacity, n; cin >> capacity >> n; // vector<int> price(n), weight(n), copies(n); // for(int i=0; i<n; i++){ // cin >> price[i] >> weight[i] >> copies[i]; // } // vector<int> dp(capacity+1, 0); // for(int i=0; i<n; i++){ // int max_copies = capacity / weight[i]; // for(int j=1; j<=min(max_copies, copies[i]); j++){ // for(int wt=capacity; wt>=0; wt--){ // if(wt >= weight[i]) // dp[wt] = max(dp[wt], dp[wt-weight[i]] + price[i]); // else // break; // } // } // } // cout << dp[capacity] << endl; vector<vector<pair<int, int>>> item_grp_by_wt(capacity+1); for(int i=0; i<n; i++){ int price, weight, copies; cin >> price >> weight >> copies; item_grp_by_wt[weight].push_back({price, copies}); } // evaluate by taking each item group and sorting it on the basis of their prices. vector<int> dp(capacity+1, 0); for(int i=1; i<=capacity; i++){ // descending order sort sort(item_grp_by_wt[i].rbegin(), item_grp_by_wt[i].rend()); int item_cnt = 0; // for each item in the weight group for(auto& p: item_grp_by_wt[i]){ int price = p.first; int copies = p.second; for(int j=1; j<=copies; j++){ // we evaluate each copy of a particular item here // if the count exceeds capacity then go to another item class if(item_cnt * i > capacity) break; // update dp array for(int wt = capacity; wt>=i; wt--){ dp[wt] = max(dp[wt], dp[wt-i] + price); } item_cnt++; } } } cout << dp[capacity] << 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...