Submission #1247920

#TimeUsernameProblemLanguageResultExecution timeMemory
1247920RomanLeshchukKnapsack (NOI18_knapsack)C++20
100 / 100
71 ms1864 KiB
#include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int s, n; cin >> s >> n; vector<vector<pair<int, int>>> vals(s + 1); for (int i = 0; i < n; ++i) { int v, w, k; cin >> v >> w >> k; vals[w].push_back({ v, k }); } vector<pair<int, int>> items{}; for (int w = 1; w <= s; ++w) { sort(vals[w].begin(), vals[w].end()); int maxCnt = s / w; while (!vals[w].empty() && maxCnt) { int addCnt = min(maxCnt, vals[w].back().second); maxCnt -= addCnt; items.insert(items.end(), addCnt, { vals[w].back().first, w }); vals[w].pop_back(); } } vector<int> dp(s + 1); for (pair<int, int> item : items) { for (int w = s; w >= item.second; --w) { dp[w] = max(dp[w], dp[w - item.second] + item.first); } } cout << *max_element(dp.begin(), dp.end()) << '\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...