Submission #1255779

#TimeUsernameProblemLanguageResultExecution timeMemory
1255779eradaxFestival (IOI25_festival)C++20
22 / 100
1040 ms2162688 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; for (int i = 0; i < n; i++) { coup.push_back({p[i], t[i], i}); } 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(n + 1, -1)); // max tickets, bought j out of the first i tickets dp[0][0] = a; for (int i = 1; i < n + 1; i++) { dp[i][0] = a; for (int j = 1; j < n + 1; 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 = n; 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()); 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...