제출 #1186363

#제출 시각아이디문제언어결과실행 시간메모리
1186363trunz111Knapsack (NOI18_knapsack)C++20
100 / 100
63 ms34376 KiB
#include <bits/stdc++.h> using namespace std; #define int long long int limit, n; map<int, vector<pair<int,int>>> mp; void Solve() { // dp[i][j] tong lon nhat tao dc tu i tap weight dau tien voi weight <= j vector<vector<int>> dp(mp.size()+5, vector<int>(limit+5, 0)); int i = 1, ans = 0; dp[0][0] = 0; for (map<int,vector<pair<int,int>>>::iterator it = mp.begin(); it != mp.end(); it++) { int w = it->first; vector<pair<int,int>> vk = it->second; sort(vk.begin(), vk.end(), greater<pair<int,int>>()); for (int m = 0; m <= limit; m++) { dp[i][m] = dp[i-1][m]; int copies = 0; int cnt_vk = 0; int cur_used = 0; int profit = 0; while ((copies+1) * w <= m && cnt_vk < vk.size()) { copies++; profit += vk[cnt_vk].first; dp[i][m] = max(dp[i][m], dp[i-1][m-copies*w] + profit); cur_used++; if (cur_used == vk[cnt_vk].second){ cnt_vk++; cur_used = 0; } } ans = max(ans, dp[i][m]); } i++; } cout << ans; } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> limit >> n; for (int i = 1; i <= n; i++) { int v, w, k; cin >> v >> w >> k; mp[w].push_back({v,k}); } 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...