Submission #1276480

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276480		mehrzad	Festival (IOI25_festival)	C++17	0 / 100	1006 ms	2162688 KiB

festival

#include "festival.h"
#include <bits/stdc++.h>
using namespace std;

struct Coupon {
    int idx;               // original index
    long long P;           // price
    int T;                 // type (multiplier)
    long long num;         // T * P
    int den;               // T - 1  (0 for T == 1, meaning infinite key)
};

static const __int128 INF = (__int128)4'000'000'000'000'000'000LL; // sufficiently large

vector<int> max_coupons(int A, vector<int> P, vector<int> T) {
    int N = (int)P.size();
    vector<Coupon> cur(N);
    for (int i = 0; i < N; ++i) {
        cur[i].idx = i;
        cur[i].P = P[i];
        cur[i].T = T[i];
        cur[i].num = (long long)T[i] * (long long)P[i];
        cur[i].den = T[i] - 1;               // 0 for T==1
    }

    // sort by increasing v = T*P/(T-1); treat T==1 as +infinity
    sort(cur.begin(), cur.end(), [](const Coupon& a, const Coupon& b) {
        if (a.den == 0 && b.den == 0) {
            // both type 1, order by price (cheapest first, any tie is fine)
            return a.P < b.P;
        }
        if (a.den == 0) return false;   // a is type 1 -> larger key
        if (b.den == 0) return true;    // b is type 1 -> larger key
        __int128 lhs = (__int128)a.num * b.den;
        __int128 rhs = (__int128)b.num * a.den;
        if (lhs != rhs) return lhs < rhs;
        // tie‑break by price
        return a.P < b.P;
    });

    // DP: dp[i][k] = maximal tokens after considering first i coupons and buying exactly k of them
    vector<vector<__int128>> dp(N + 1, vector<__int128>(N + 1, -1));
    vector<vector<char>> take(N + 1, vector<char>(N + 1, -1)); // 1 = taken, 0 = skipped
    dp[0][0] = A;

    for (int i = 0; i < N; ++i) {
        const Coupon& c = cur[i];
        for (int k = 0; k <= i; ++k) {
            if (dp[i][k] < 0) continue;
            // Skip this coupon
            if (dp[i][k] > dp[i + 1][k]) {
                dp[i + 1][k] = dp[i][k];
                take[i + 1][k] = 0;
            }
            // Take this coupon if affordable
            if (dp[i][k] >= (__int128)c.P) {
                __int128 newToken = (dp[i][k] - (__int128)c.P) * (__int128)c.T;
                if (newToken > INF) newToken = INF;
                if (newToken > dp[i + 1][k + 1]) {
                    dp[i + 1][k + 1] = newToken;
                    take[i + 1][k + 1] = 1;
                }
            }
        }
    }

    // Find the maximum number of coupons we can buy
    int bestK = 0;
    for (int k = 0; k <= N; ++k) {
        if (dp[N][k] >= 0) bestK = k;
    }

    // Reconstruct the sequence
    vector<int> revResult;
    int i = N, k = bestK;
    while (i > 0) {
        if (take[i][k] == 1) {
            revResult.push_back(cur[i - 1].idx);
            --k;
        }
        // if take[i][k] == 0 we simply skip this coupon
        --i;
    }
    reverse(revResult.begin(), revResult.end());
    return revResult;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 12
• Subtask 4: 0 / 15
• Subtask 5: 0 / 27
• Subtask 6: 0 / 16
• Subtask 7: 0 / 18