Submission #1276483

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

festival

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

vector<int> max_coupons(int A, vector<int> P, vector<int> T) {
    struct Coupon {
        int idx;          // original index
        long long p;      // price
        int t;            // type (multiplier)
    };
    int N = (int)P.size();
    vector<Coupon> c(N);
    for (int i = 0; i < N; ++i) c[i] = {i, (long long)P[i], T[i]};

    /*  Order that minimises the needed initial tokens.
        For T>1 the key is  V = P * T / (T-1) .
        Coupons with T = 1 are placed at the end (they never increase tokens).   */
    auto cmp = [](const Coupon& a, const Coupon& b) {
        if (a.t == 1 && b.t == 1) return a.idx < b.idx; // any stable order
        if (a.t == 1) return false;                     // a after b
        if (b.t == 1) return true;                      // a before b
        // compare a.p * a.t * (b.t-1)  <  b.p * b.t * (a.t-1)
        long long left  = a.p * a.t * (b.t - 1LL);
        long long right = b.p * b.t * (a.t - 1LL);
        if (left != right) return left < right;
        // deterministic tie‑break
        if (a.t != b.t) return a.t < b.t;
        return a.p < b.p;
    };
    sort(c.begin(), c.end(), cmp);

    const long long INF = (1LL << 60);
    // dp[i][k] = minimal tokens needed before processing items i..N-1
    //            to buy exactly k coupons among them (respecting the order)
    vector<vector<long long>> dp(N + 1, vector<long long>(N + 1, INF));
    dp[N][0] = 0;
    for (int i = N - 1; i >= 0; --i) {
        dp[i][0] = 0;
        for (int k = 1; k <= N - i; ++k) {
            long long best = dp[i + 1][k];                      // skip current coupon
            long long prev = dp[i + 1][k - 1];                 // take it
            if (prev != INF) {
                long long cand = c[i].p + ( (prev + c[i].t - 1) / c[i].t );
                if (cand < best) best = cand;
            }
            dp[i][k] = best;
        }
    }

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

    // reconstruct one optimal sequence (forward order = the order in 'c')
    vector<int> answer;
    answer.reserve(bestK);
    int i = 0, k = bestK;
    while (i < N && k > 0) {
        if (dp[i][k] == dp[i + 1][k]) {
            ++i;                     // skip this coupon
        } else {
            answer.push_back(c[i].idx); // take it
            --k;
            ++i;
        }
    }
    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