Submission #1261637

#TimeUsernameProblemLanguageResultExecution timeMemory
1261637avighnaFestival (IOI25_festival)C++20
5 / 100
1010 ms2162688 KiB
#include <bits/stdc++.h> struct item { int64_t i, p, t; }; std::vector<int> max_coupons(int A, std::vector<int> P, std::vector<int> T) { const int n = P.size(); std::vector<item> a(n); for (int i = 0; i < n; ++i) { a[i] = {i, P[i], T[i]}; } std::sort(a.begin(), a.end(), [&](item i, item j) { if (i.t == j.t and i.t == 1) { return i.p < j.p; } return (j.p + i.p * i.t) * j.t < (i.p + j.p * j.t) * i.t; }); int _n = n; for (int i = 0; i < n; ++i) { if (a[i].t == 1) { _n = i; break; } } if (_n == 0) { std::vector<int> ans; int64_t cur = A; for (auto &i : a) { if (cur - i.p < 0) { break; } cur = (cur - i.p) * i.t; ans.push_back(i.i); } return ans; } std::vector<int64_t> psum(n); psum[_n] = a[_n].p; for (int i = _n + 1; i < n; ++i) { psum[i] = psum[i - 1] + a[i].p; } const int64_t inf = 1e15; std::vector dp(_n, std::vector<int64_t>(_n + 1)); for (int i = 0; i < _n; ++i) { for (int j = 0; j <= _n; ++j) { if (j == 0) { dp[i][j] = A; continue; } if (j > i + 1) { dp[i][j] = -inf; continue; } if (i == 0) { dp[i][j] = A - a[i].p >= 0 ? (A - a[i].p) * a[i].t : -inf; continue; } dp[i][j] = dp[i - 1][j]; if (dp[i - 1][j - 1] - a[i].p >= 0) { dp[i][j] = std::max(dp[i][j], (dp[i - 1][j - 1] - a[i].p) * a[i].t); } } } int max_ans = 0, corr_j = 0; for (int j = 0; j <= _n; ++j) { if (dp[_n - 1][j] < 0) { continue; } int got = j + std::upper_bound(psum.begin(), psum.end(), dp[_n - 1][j]) - psum.begin() - _n; if (got > max_ans) { max_ans = got; corr_j = j; } } std::vector<int> ans; int i = _n - 1, j = corr_j; while (j > 0) { if (i != 0 and dp[i - 1][j - 1] - a[i].p >= 0 and dp[i - 1][j - 1] - a[i].p > dp[i - 1][j]) { j--; ans.push_back(a[i].i); } else if (i == 0) { if (j != 0) { ans.push_back(a[i].i); j--; } } i--; } std::reverse(ans.begin(), ans.end()); for (int size = max_ans - ans.size(), i = 0; i < size; ++i) { ans.push_back(a[_n + i].i); } return ans; }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...