Submission #1276463

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276463		mehrzad	Festival (IOI25_festival)	C++20	21 / 100	65 ms	20272 KiB

festival

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

struct Coupon {
    int price;      // P[i]
    int type;       // T[i]  (2,3,4)
    int idx;        // original index
    long long C;    // net loss at start, formula (5)
};

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

    /* -------------------------------------------------------------
       split coupons into high (T>1) and cheap (T==1), discard
       those with price > A (they can never be bought)
    ------------------------------------------------------------- */
    vector<Coupon> high;
    struct Cheap { int price; int idx; };
    vector<Cheap> cheap;

    for (int i = 0; i < N; ++i) {
        if (P[i] > A) continue;                 // never affordable
        if (T[i] == 1) {
            cheap.push_back({P[i], i});
        } else {
            long long C = 1LL * T[i] * P[i] - 1LL * (T[i] - 1) * A;
            high.push_back({P[i], T[i], i, C});
        }
    }

    /* --------------- cheap coupons : sort by price -------------- */
    sort(cheap.begin(), cheap.end(),
         [](const Cheap& a, const Cheap& b) {
             if (a.price != b.price) return a.price < b.price;
             return a.idx < b.idx;
         });

    vector<long long> cheapPref(cheap.size() + 1, 0);
    for (size_t i = 0; i < cheap.size(); ++i)
        cheapPref[i + 1] = cheapPref[i] + cheap[i].price;

    /* --------------- high coupons : sort by V ------------------- */
    sort(high.begin(), high.end(),
         [&](const Coupon& a, const Coupon& b) {
             long long left  = 1LL * a.price * a.type * (b.type - 1);
             long long right = 1LL * b.price * b.type * (a.type - 1);
             if (left != right) return left < right;                 // smaller V first
             if (a.C != b.C) return a.C < b.C;                       // tie‑break by net loss
             return a.idx < b.idx;
         });

    const int M = (int)high.size();
    const int K = min(M, 60);                     // safe upper bound (≈30)

    /* -------------------------------------------------------------
       DP: dp[i][c] – maximal remaining tokens after considering
                     first i high coupons and buying exactly c of them
       we keep only two rows for the values, but we store the
       whole decision table "taken" for back‑tracking
    ------------------------------------------------------------- */
    const long long NEG = -1;
    vector<long long> dpPrev(K + 1, NEG), dpCurr(K + 1, NEG);
    dpPrev[0] = A;

    // decision table: taken[i][c] == 1  iff coupon i (1‑based) is taken to obtain dp[i][c]
    vector<char> taken((M + 1) * (K + 1), 0);

    for (int i = 1; i <= M; ++i) {
        const Coupon& cp = high[i - 1];
        // copy the “skip” case
        for (int c = 0; c <= K; ++c) dpCurr[c] = dpPrev[c];

        // try to take the i‑th coupon
        for (int c = 1; c <= K; ++c) {
            if (dpPrev[c - 1] != NEG && dpPrev[c - 1] >= cp.price) {
                long long newX = (dpPrev[c - 1] - cp.price) * 1LL * cp.type;
                if (newX > dpCurr[c]) {
                    dpCurr[c] = newX;
                    taken[i * (K + 1) + c] = 1;
                }
            }
        }
        dpPrev.swap(dpCurr);
    }

    /* -------------------------------------------------------------
       choose the best number of high coupons (c) together with cheap ones
    ------------------------------------------------------------- */
    long long bestTotal = 0;
    int bestC = 0;
    long long bestTokens = A;          // tokens after the chosen high coupons

    for (int c = 0; c <= K; ++c) {
        long long tokens = dpPrev[c];
        if (tokens == NEG) continue;
        // maximal number of cheap coupons we can still afford
        int cheapCnt = (int)(upper_bound(cheapPref.begin(),
                                         cheapPref.end(),
                                         tokens) - cheapPref.begin()) - 1;
        long long total = (long long)c + cheapCnt;
        if (total > bestTotal) {
            bestTotal = total;
            bestC = c;
            bestTokens = tokens;
        }
    }

    /* -------------------------------------------------------------
       reconstruct the chosen high coupons
    ------------------------------------------------------------- */
    vector<int> chosenHigh;
    int c = bestC;
    for (int i = M; i >= 1 && c > 0; --i) {
        if (taken[i * (K + 1) + c]) {
            chosenHigh.push_back(high[i - 1].idx);
            --c;
        }
    }
    reverse(chosenHigh.begin(), chosenHigh.end());

    /* -------------------------------------------------------------
       add cheap coupons (the cheapest ones that still fit)
    ------------------------------------------------------------- */
    int cheapCnt = (int)(upper_bound(cheapPref.begin(),
                                     cheapPref.end(),
                                     bestTokens) - cheapPref.begin()) - 1;
    vector<int> answer;
    answer.reserve(chosenHigh.size() + cheapCnt);
    answer.insert(answer.end(), chosenHigh.begin(), chosenHigh.end());
    for (int i = 0; i < cheapCnt; ++i)
        answer.push_back(cheap[i].idx);

    return answer;
}

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