Submission #1276482

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276482		mehrzad	Festival (IOI25_festival)	C++17	0 / 100	1018 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)
    bool inf;                // true for T == 1 (key = +infinity)
    __int128 num;            // P * T   (valid only if !inf)
    __int128 den;            // T-1    (valid only if !inf)
};

static bool cmpCoupon(const Coupon& a, const Coupon& b) {
    if (a.inf != b.inf)            // finite keys come first
        return !a.inf && b.inf;
    if (a.inf)                     // both infinite – any order, keep by idx
        return a.idx < b.idx;
    // compare a.num / a.den  <  b.num / b.den
    return a.num * b.den < b.num * a.den;
}

std::vector<int> max_coupons(int A, std::vector<int> P,
    std::vector<int> T) {

    int N = (int)P.size();
    vector<Coupon> coupons(N);
    for (int i = 0; i < N; ++i) {
        coupons[i].idx = i;
        coupons[i].p   = P[i];
        coupons[i].t   = T[i];
        coupons[i].inf = (T[i] == 1);
        if (!coupons[i].inf) {
            coupons[i].num = (__int128)P[i] * (__int128)T[i];
            coupons[i].den = (__int128)(T[i] - 1);
        }
    }

    // sort by increasing key = P*T/(T-1); T==1 -> +inf
    sort(coupons.begin(), coupons.end(), cmpCoupon);

    // reverse order: we will add coupons in front of the already built suffix
    vector<int> orderDesc(N);            // original indices in descending key order
    for (int i = 0; i < N; ++i) {
        orderDesc[i] = coupons[N - 1 - i].idx;   // biggest key first
    }

    const long long INF = (1LL << 60);   // large enough ( > sum of all prices )
    vector<vector<long long>> dp(N + 1, vector<long long>(N + 1, INF));
    vector<vector<char>> take(N + 1, vector<char>(N + 1, 0));

    dp[0][0] = 0;
    for (int i = 1; i <= N; ++i) {
        int idx = orderDesc[i - 1];
        long long Pi = P[idx];
        int Ti = T[idx];
        for (int k = 0; k <= i; ++k) {
            // option 1: skip this coupon
            long long best = dp[i - 1][k];
            char used = 0;
            // option 2: take it
            if (k > 0 && dp[i - 1][k - 1] != INF) {
                long long prev = dp[i - 1][k - 1];
                long long cand = Pi + (prev + Ti - 1) / Ti;   // ceil(prev / Ti)
                if (cand < best) {
                    best = cand;
                    used = 1;
                }
            }
            dp[i][k] = best;
            take[i][k] = used;
        }
    }

    int bestK = 0;
    for (int k = N; k >= 0; --k) {
        if (dp[N][k] <= A) {
            bestK = k;
            break;
        }
    }

    // reconstruct the answer
    vector<int> answer;
    int i = N, k = bestK;
    while (i > 0) {
        if (take[i][k]) {
            answer.push_back(orderDesc[i - 1]);   // this coupon is used
            --k;
        }
        --i;
    }
    // 'answer' is already in forward chronological order (lowest key first)
    return answer;
}

• 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