Submission #1254823

#TimeUsernameProblemLanguageResultExecution timeMemory
1254823orny_nabilaKnapsack (NOI18_knapsack)C++20
73 / 100
360 ms327680 KiB
#include <bits/stdc++.h> #define int long long using namespace std; int32_t main() { ios::sync_with_stdio(false); cin.tie(NULL); int S, N; cin >> S >> N; map<int, vector<int>> weight_groups; for (int i = 0; i < N; ++i) { int v, w, k; cin >> v >> w >> k; int limit = min(k, S / w); for (int j = 0; j < limit; ++j) { weight_groups[w].push_back(v); } } vector<pair<int, int>> final_items; for (auto& [w, vals] : weight_groups) { int limit = S / w; if ((int)vals.size() > limit) { nth_element(vals.begin(), vals.begin() + limit, vals.end(), greater<>()); vals.resize(limit); } for (int v : vals) { final_items.emplace_back(w, v); } } vector<int> dp(S + 1, 0); for (auto& [w, v] : final_items) { for (int j = S; j >= w; --j) { dp[j] = max(dp[j], dp[j - w] + v); } } cout << dp[S] << '\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...