Submission #1255920

#TimeUsernameProblemLanguageResultExecution timeMemory
1255920goutomKnapsack (NOI18_knapsack)C++20
100 / 100
35 ms2884 KiB
#include <bits/stdc++.h> using namespace std; struct Item { long long value; int weight; long long qty; }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int capacity, numItems; cin >> capacity >> numItems; vector<priority_queue<pair<long long, long long>>> grouped(capacity + 1); for (int i = 0; i < numItems; i++) { Item item; cin >> item.value >> item.weight >> item.qty; grouped[item.weight].push(make_pair(item.value, item.qty)); } vector<long long> dp(capacity + 1, 0); for (int w = 1; w <= capacity; w++) { long long maxCanTake = capacity / w; while (!grouped[w].empty() && maxCanTake > 0) { pair<long long, long long> topItem = grouped[w].top(); grouped[w].pop(); long long value = topItem.first; long long qty = topItem.second; if (qty > maxCanTake) qty = maxCanTake; maxCanTake -= qty; for (int i = 0; i < qty; i++) { for (int c = capacity; c >= w; c--) { dp[c] = max(dp[c], dp[c - w] + value); } } } } long long answer = 0; for (int c = 1; c <= capacity; c++) { answer = max(answer, dp[c]); } cout << answer << "\n"; 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...