Submission #1224875

#TimeUsernameProblemLanguageResultExecution timeMemory
1224875builder_opKnapsack (NOI18_knapsack)C++20
100 / 100
35 ms2888 KiB
#include <bits/stdc++.h> using namespace std; // ---------- constants ---------- constexpr int MAX_S = 2000; // 1 ≤ S ≤ 2000 // ---------- helpers ---------- struct ItemType { int v; // value (≤ 1 000 000) int w; // weight (1 … S) long long k; // copies (≤ 1e9) }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int S, N; if (!(cin >> S >> N)) return 0; /* ---- 1. read & bucket by weight ---- */ vector<vector<pair<int,long long>>> bucket(S + 1); // bucket[w] = list of (value, copies) for (int i = 0; i < N; ++i) { ItemType it; cin >> it.v >> it.w >> it.k; if (it.w > S) continue; // too heavy, ignore long long cap = S / it.w; // we never need more than this many copies if (cap == 0) continue; if (it.k > cap) it.k = cap; bucket[it.w].push_back({it.v, it.k}); } /* ---- 2. keep only the best S/w copies for each weight ---- */ struct Copy { int v, w; }; // one concrete copy vector<Copy> copies; copies.reserve(15200); // upper bound for (int w = 1; w <= S; ++w) { if (bucket[w].empty()) continue; int lim = S / w; // maximum copies of weight w we can ever carry auto &vec = bucket[w]; sort(vec.begin(), vec.end(), // sort by value descending [](auto &a, auto &b) { return a.first > b.first; }); int taken = 0; for (auto [v, k] : vec) { if (taken == lim) break; int cnt = static_cast<int>(min<long long>(k, lim - taken)); taken += cnt; while (cnt--) copies.push_back({v, w}); // push each copy individually } } /* ---- 3. 0/1 knapsack with at most 15 200 items ---- */ static int dp[MAX_S + 1]; // zero-initialised for (const auto &cp : copies) { int w = cp.w, v = cp.v; for (int s = S; s >= w; --s) dp[s] = max(dp[s], dp[s - 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...