제출 #1255796

#제출 시각아이디문제언어결과실행 시간메모리
1255796eradaxFestival (IOI25_festival)C++20
0 / 100
117 ms64516 KiB
#include "festival.h" #include <bits/stdc++.h> using namespace std; #ifndef EVAL #define dbg(expr) cerr << "[" << __FUNCTION__ << ", " << __LINE__ << "] " << #expr << ": " << expr << endl #else #define dbg(expr) #endif using ll = long long; using vl = vector<ll>; using vvl = vector<vl>; using vi = vector<int>; using vvi = vector<vi>; using a3 = array<ll, 3>; using v3 = vector<a3>; #define sz(c) ((int)c.size()) vi max_coupons(int _a, vi p, vi t) { int n = sz(p); assert(n == sz(t)); ll a = _a; v3 coup; v3 ones; for (int i = 0; i < n; i++) { coup.push_back({p[i], t[i], i}); if (t[i] == 1) ones.push_back({p[i], t[i], i}); } sort(ones.begin(), ones.end(), [](auto lhs, auto rhs) { auto [x, y, lind] = lhs; auto [z, w, rind] = rhs; if (y == 1 && w == 1) return x < z; return x * y * (w - 1) < z * w * (y - 1); }); sort(coup.begin(), coup.end(), [](auto lhs, auto rhs) { auto [x, y, lind] = lhs; auto [z, w, rind] = rhs; if (y == 1 && w == 1) return x < z; return x * y * (w - 1) < z * w * (y - 1); }); for (auto [x, y, i] : coup) { dbg(x); dbg(y); dbg(i); } vvl dp(n + 1, vl(__bit_width(n) + 10, -1)); // max tickets, bought j out of the first i tickets dp[0][0] = a; for (int i = 1; i < sz(dp); i++) { dp[i][0] = a; for (int j = 1; j < sz(dp[0]); j++) { dp[i][j] = max(dp[i - 1][j], max(min((dp[i - 1][j - 1] - coup[i - 1][0]) * coup[i - 1][1], (ll)1e15), (ll)-1)); } } int i = n; int j = sz(dp[0]) - 1; while (j >= 0 && dp[i][j] < 0) j--; dbg(i); dbg(j); vi ret; for (; i > 0 && j > 0; i--) { dbg(dp[i][j]); dbg(dp[i - 1][j]); dbg(dp[i - 1][j - 1]); int nj = j - (max(min((dp[i - 1][j - 1] - coup[i - 1][0]) * coup[i - 1][1], (ll)1e15), (ll)-1) == dp[i][j]); dbg(i); dbg(j); if (nj != j) ret.push_back(coup[i - 1][2]); j = nj; } reverse(ret.begin(), ret.end()); for (auto i : ret) a = max(min((a - coup[i - 1][0]) * coup[i - 1][1], (ll)1e15), (ll)-1); for (auto [x, w, i] : ones) { if (a < x) continue; a -= x; ret.push_back(i); } return ret; }
#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...