제출 #1101208

#제출 시각아이디문제언어결과실행 시간메모리
1101208Plot_TwistKnapsack (NOI18_knapsack)C++17
100 / 100
119 ms35144 KiB
#include<bits/stdc++.h> using namespace std; #define int long long bool comp(pair<int,int>&p1,pair<int,int>&p2) { if(p1.first==p2.first) return p1.second > p2.second; else return p1.first > p2.first; } signed main () { int n,limit; cin>>limit>>n; // ------Grouping by weight---------- map<int,vector<pair<int,int>>>mp; for(int i = 0; i < n; i++) { int val, wt, am; cin>>val>>wt>>am; if(wt<=limit && am>0)mp[wt].push_back({val,am}); } // ---------------------------------- // ------Initializing DP ------------ int wtcnt = mp.size(); int dp[wtcnt+1][limit+1]; for(int i = 0; i<= wtcnt; i++) for(int j = 0; j<=limit;j++) dp[i][j] = INT32_MIN; // ---------------------------------- int level = 1; dp[0][0] = 0; for(auto &[wt,arr] : mp) { sort(arr.begin(),arr.end(),comp); int sz= arr.size(); for(int i = 0; i<=limit; i++) { dp[level][i] = dp[level-1][i]; // NOT TAKE int idx = 0; int value = 0; int amount_taken = 0; int curr_item_used = 0; while((amount_taken+1)*wt <= i && idx < sz) { amount_taken++; value+= arr[idx].first; if(dp[level-1][i-amount_taken*wt]!= INT32_MIN) { dp[level][i] = max(dp[level][i], value + dp[level-1][i-amount_taken*wt]); } curr_item_used++; if(curr_item_used==arr[idx].second) { idx++; curr_item_used=0; } } } level++; } int ans = -1; for(int i = 0; i<= limit; i++) ans = max(ans, dp[wtcnt][i]); 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...