Submission #1276469

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276469		mehrzad	Festival (IOI25_festival)	C++17	12 / 100	1059 ms	2162688 KiB

festival

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

using int64 = long long;
using i128 = __int128_t;

const int64 INF = (1LL << 60);          // big enough, far larger than any price sum

// multiply and subtract with saturation at INF
static inline int64 apply(int64 cur, int64 price, int mult) {
    if (cur == INF) return INF;
    if (cur < price) return -1;                 // cannot buy
    i128 val = (i128)(cur - price) * mult;
    if (val > INF) return INF;
    return (int64)val;
}

// --------------------------------------------------------------------

struct MulCoupon {
    int idx;        // original index
    int64 P;
    int T;
};

vector<int> max_coupons(int A, vector<int> P, vector<int> T) {
    int N = (int)P.size();

    /* -------- separate the two groups -------- */
    vector<MulCoupon> mul;               // T > 1
    vector<pair<int64,int>> cheap;       // price , index   (T == 1)

    for (int i = 0; i < N; ++i) {
        if (T[i] == 1) cheap.emplace_back((int64)P[i], i);
        else            mul.push_back({i, (int64)P[i], T[i]});
    }

    /* -------- sort multipliers by K = P*T/(T-1) -------- */
    auto cmpK = [](const MulCoupon& a, const MulCoupon& b) {
        // compare a.P * a.T / (a.T-1)  <  b.P * b.T / (b.T-1)
        i128 left  = (i128)a.P * a.T * (b.T - 1);
        i128 right = (i128)b.P * b.T * (a.T - 1);
        return left < right;
    };
    sort(mul.begin(), mul.end(), cmpK);

    int M = (int)mul.size();

    /* -------- DP over the sorted multipliers -------- */
    vector<vector<int64>> best(M + 1, vector<int64>(M + 1, -1));
    // predecessor: {previous k , taken?}
    vector<vector<pair<int,bool>>> pre(M + 1, vector<pair<int,bool>>(M + 1, {-1,false}));

    best[0][0] = (int64)A;

    for (int i = 0; i < M; ++i) {
        for (int k = 0; k <= i; ++k) {
            if (best[i][k] == -1) continue;

            // not take coupon i
            if (best[i][k] > best[i + 1][k]) {
                best[i + 1][k] = best[i][k];
                pre[i + 1][k] = {k, false};
            }

            // take coupon i, if affordable
            if (best[i][k] >= mul[i].P) {
                int64 nxt = apply(best[i][k], mul[i].P, mul[i].T);
                if (nxt > best[i + 1][k + 1]) {
                    best[i + 1][k + 1] = nxt;
                    pre[i + 1][k + 1] = {k, true};
                }
            }
        }
    }

    /* -------- cheap coupons: sort by price and prefix sums -------- */
    sort(cheap.begin(), cheap.end(),
         [](const pair<int64,int>& a, const pair<int64,int>& b){
            return a.first < b.first;
         });

    int C = (int)cheap.size();
    vector<int64> pref(C + 1, 0);
    for (int i = 1; i <= C; ++i) pref[i] = pref[i - 1] + cheap[i - 1].first;

    /* -------- choose the best number of multipliers -------- */
    int bestTotal = 0;
    int bestK = 0;           // how many multipliers are used
    int bestCheap = 0;       // how many cheap coupons are taken

    for (int k = 0; k <= M; ++k) {
        int64 tok = best[M][k];
        if (tok < 0) continue;          // unreachable

        // maximal cheap coupons we can afford
        int cheapCnt = 0;
        if (tok >= pref[C]) cheapCnt = C;
        else {
            // binary search on prefix sums
            int lo = 0, hi = C;
            while (lo < hi) {
                int mid = (lo + hi + 1) >> 1;
                if (pref[mid] <= tok) lo = mid;
                else hi = mid - 1;
            }
            cheapCnt = lo;
        }

        int total = k + cheapCnt;
        if (total > bestTotal) {
            bestTotal = total;
            bestK = k;
            bestCheap = cheapCnt;
        }
    }

    /* -------- reconstruct the chosen multipliers -------- */
    vector<int> answer;
    int i = M;
    int k = bestK;
    while (i > 0) {
        auto pr = pre[i][k];
        int prevK = pr.first;
        bool took = pr.second;
        if (took) {
            answer.push_back(mul[i - 1].idx);      // coupon i-1 was taken
        }
        k = prevK;
        --i;
    }
    reverse(answer.begin(), answer.end());   // correct chronological order

    /* -------- add the cheap coupons -------- */
    for (int idx = 0; idx < bestCheap; ++idx)
        answer.push_back(cheap[idx].second);

    return answer;        // possibly empty
}

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