Submission #1276475

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

festival

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

struct Coupon {
    int idx;          // original index
    long long P;      // price
    int T;            // multiplier
};

static long long ceilDiv(long long a, int b) {
    // a >= 0 , b >= 1
    return (a + b - 1) / b;
}

// ---------------------------------------------------------------
//  max_coupons : required function
// ---------------------------------------------------------------
vector<int> max_coupons(int A, vector<int> P, vector<int> T) {
    int N = (int)P.size();
    vector<Coupon> all(N);
    for (int i = 0; i < N; ++i) {
        all[i] = {i, (long long)P[i], T[i]};
    }

    /* ---------- sort by increasing R = P*T/(T-1) ----------
       T = 1  →   R = +∞   (they are placed after all T>1)   */
    auto cmp = [](const Coupon& a, const Coupon& b) -> bool {
        bool a_one = (a.T == 1);
        bool b_one = (b.T == 1);
        if (a_one && b_one) return a.idx < b.idx;   // any stable order
        if (a_one) return false;                    // a after b
        if (b_one) return true;                     // a before b
        __int128 left  = (__int128)a.P * a.T * (b.T - 1);
        __int128 right = (__int128)b.P * b.T * (a.T - 1);
        if (left != right) return left < right;
        if (a.P != b.P) return a.P < b.P;           // tie‑break
        return a.idx < b.idx;
    };
    sort(all.begin(), all.end(), cmp);

    /* ---------- DP over the list, processed from large R to small R ----------
       reverse order → we always add the current coupon at the front */
    vector<Coupon> order = all;
    reverse(order.begin(), order.end());

    const long long INF = (1LL << 60);
    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;                     // empty set

    for (int i = 0; i < N; ++i) {
        // initialise row i+1
        for (int k = 0; k <= i + 1; ++k) {
            dp[i + 1][k] = INF;
            take[i + 1][k] = 0;
        }
        // skip the i‑th coupon
        for (int k = 0; k <= i; ++k) {
            if (dp[i][k] < dp[i + 1][k]) {
                dp[i + 1][k] = dp[i][k];
                take[i + 1][k] = 0;
            }
        }
        // take the i‑th coupon (it becomes the first one)
        const Coupon& c = order[i];
        for (int k = 0; k <= i; ++k) {
            if (dp[i][k] == INF) continue;
            long long cand = c.P + ceilDiv(dp[i][k], c.T);
            if (cand < dp[i + 1][k + 1]) {
                dp[i + 1][k + 1] = cand;
                take[i + 1][k + 1] = 1;
            }
        }
    }

    // largest feasible number of coupons
    int bestK = 0;
    for (int k = N; k >= 0; --k) {
        if (dp[N][k] <= (long long)A) {
            bestK = k;
            break;
        }
    }

    // reconstruct the purchase order (forward order)
    vector<int> answer;
    int i = N, k = bestK;
    while (i > 0) {
        if (k > 0 && take[i][k]) {
            answer.push_back(order[i - 1].idx);   // original index
            --k;
            --i;
        } else {
            --i;                                   // coupon was skipped
        }
    }
    // the `answer` vector already contains the coupons in the order they
    // have to be bought.
    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