Submission #1276478

#TimeUsernameProblemLanguageResultExecution timeMemory
1276478mehrzadFestival (IOI25_festival)C++17
Compilation error
0 ms0 KiB
#include <bits/stdc++.h> using namespace std; using int64 = long long; using i128 = __int128_t; struct Coupon { int idx; // original index int64 P; // price int T; // type i128 num; // P * T (for v = num / (T-1) ) int64 den; // T-1 bool inf; // true for T == 1 (v = +∞) }; static i128 INF = ( (i128)1 << 60 ); // sufficiently large (≈10^18) static i128 ceil_div(i128 a, int64 b) { return (a + b - 1) / b; } vector<int> max_coupons(int A, vector<int> P, vector<int> T) { int N = (int)P.size(); vector<Coupon> coupons; coupons.reserve(N); for (int i = 0; i < N; ++i) { Coupon c; c.idx = i; c.P = P[i]; c.T = T[i]; if (c.T == 1) { c.inf = true; c.num = 0; c.den = 1; } else { c.inf = false; c.num = (i128)c.P * (i128)c.T; // numerator of v c.den = c.T - 1; } coupons.push_back(c); } // sort by decreasing v (inf first) auto cmp = [](const Coupon& a, const Coupon& b) { if (a.inf != b.inf) return a.inf > b.inf; // inf (T==1) is larger // compare a.num / a.den > b.num / b.den ? // i.e. a.num * b.den > b.num * a.den i128 left = a.num * (i128)b.den; i128 right = b.num * (i128)a.den; if (left != right) return left > right; return a.idx < b.idx; // tie‑break – deterministic }; sort(coupons.begin(), coupons.end(), cmp); // DP[i][k] = minimal needed tokens before first i coupons, // using exactly k of them. vector<vector<i128>> dp(N + 1, vector<i128>(N + 1, INF)); vector<vector<char>> take(N + 1, vector<char>(N + 1, -1)); vector<vector<int>> prevK(N + 1, vector<int>(N + 1, -1)); dp[0][0] = 0; // nothing needed before empty prefix for (int i = 0; i < N; ++i) { const Coupon& c = coupons[i]; for (int k = 0; k <= i; ++k) { i128 cur = dp[i][k]; if (cur == INF) continue; /* skip c */ if (cur < dp[i + 1][k]) { dp[i + 1][k] = cur; take[i + 1][k] = 0; prevK[i + 1][k] = k; } /* take c (it becomes the last bought coupon) */ i128 need = (i128)c.P + ceil_div(cur, c.T); if (need < dp[i + 1][k + 1]) { dp[i + 1][k + 1] = need; take[i + 1][k + 1] = 1; prevK[i + 1][k + 1] = k; } } } int bestK = 0; for (int k = N; k >= 0; --k) { if (dp[N][k] <= (i128)A) { bestK = k; break; } } // reconstruction vector<int> answer; int i = N, k = bestK;

Compilation message (stderr)

festival.cpp: In function 'std::vector<int> max_coupons(int, std::vector<int>, std::vector<int>)':
festival.cpp:93:26: error: expected '}' at end of input
   93 |     int i = N, k = bestK;
      |                          ^
festival.cpp:22:62: note: to match this '{'
   22 | vector<int> max_coupons(int A, vector<int> P, vector<int> T) {
      |                                                              ^
festival.cpp:93:26: warning: no return statement in function returning non-void [-Wreturn-type]
   93 |     int i = N, k = bestK;
      |                          ^