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;
      |                          ^