Submission #1276461

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276461		mehrzad	Festival (IOI25_festival)	C++20	21 / 100	74 ms	7356 KiB

festival

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

struct ParentInfo {
    int couponIdx;   // original index of the coupon
    int prev;        // index in the parent vector of the previous state
    ParentInfo(int c = -1, int p = -1) : couponIdx(c), prev(p) {}
};

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

    /* -----------------------------------------------------------
       split the coupons
       ----------------------------------------------------------- */
    vector<int> multIdx;          // indices with T > 1
    vector<int> cheapIdx;         // indices with T == 1
    multIdx.reserve(N);
    cheapIdx.reserve(N);
    for (int i = 0; i < N; ++i) {
        if (T[i] == 1) cheapIdx.push_back(i);
        else           multIdx.push_back(i);
    }

    /* -----------------------------------------------------------
       sort multiplier coupons by w = Pi*Ti/(Ti-1)
       (compare Pi*Ti*(Tj-1)  <  Pj*Tj*(Ti-1))
       ----------------------------------------------------------- */
    sort(multIdx.begin(), multIdx.end(),
        [&](int a, int b) {
            long long left  = 1LL * P[a] * T[a] * (T[b] - 1);
            long long right = 1LL * P[b] * T[b] * (T[a] - 1);
            if (left != right) return left < right;
            return a < b;                     // deterministic tie‑break
        });

    /* -----------------------------------------------------------
       DP over a constant number of taken multiplier coupons
       ----------------------------------------------------------- */
    const int MAXK = 60;                     // > log2(1e9)
    const long long INF = (1LL << 60);
    vector<long long> dp(MAXK + 1, INF);     // minimal loss D
    vector<int> bestNode(MAXK + 1, -1);      // index in parent list
    dp[0] = 0;                               // no coupon, loss 0
    int curMax = 0;                          // largest k with dp[k] < INF

    vector<ParentInfo> parent;               // pool of nodes
    parent.reserve(multIdx.size() * 30);

    for (int idx : multIdx) {
        long long price = P[idx];
        int Ti = T[idx];
        long long Bi = 1LL * price * Ti - 1LL * A * (Ti - 1);   // >0

        for (int k = curMax; k >= 0; --k) {
            if (dp[k] == INF) continue;
            if (dp[k] <= (long long)A - price) {               // affordable
                long long newLoss = 1LL * Ti * dp[k] + Bi;     // (4)
                if (newLoss < dp[k + 1]) {
                    dp[k + 1] = newLoss;
                    parent.emplace_back(idx, bestNode[k]);
                    bestNode[k + 1] = (int)parent.size() - 1;
                    if (k + 1 > curMax) curMax = k + 1;
                }
            }
        }
    }

    /* -----------------------------------------------------------
       cheap coupons – sort by price and build prefix sums
       ----------------------------------------------------------- */
    vector<pair<int,int>> cheap;          // (price, original index)
    cheap.reserve(cheapIdx.size());
    for (int idx : cheapIdx) cheap.emplace_back(P[idx], idx);
    sort(cheap.begin(), cheap.end(),
        [&](const pair<int,int>& a, const pair<int,int>& b){
            if (a.first != b.first) return a.first < b.first;
            return a.second < b.second;
        });

    int C = (int)cheap.size();
    vector<long long> 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 multiplier coupons
       ----------------------------------------------------------- */
    int bestK = 0, bestCheap = 0;
    int bestTotal = -1;
    for (int k = 0; k <= curMax; ++k) {
        if (dp[k] == INF) continue;
        long long tokensLeft = (long long)A - dp[k];
        // maximal cheap coupons that fit into tokensLeft
        int cheapCnt = (int)(upper_bound(pref.begin(), pref.end(), tokensLeft) - pref.begin() - 1);
        int total = k + cheapCnt;
        if (total > bestTotal) {
            bestTotal = total;
            bestK = k;
            bestCheap = cheapCnt;
        }
    }

    /* -----------------------------------------------------------
       reconstruct the answer
       ----------------------------------------------------------- */
    vector<int> answer;

    // multiplier part (in the order we processed them)
    vector<int> multSeq;
    int node = bestNode[bestK];
    while (node != -1) {
        multSeq.push_back(parent[node].couponIdx);
        node = parent[node].prev;
    }
    reverse(multSeq.begin(), multSeq.end());
    answer.insert(answer.end(), multSeq.begin(), multSeq.end());

    // cheap part: first bestCheap cheapest coupons
    for (int i = 0; i < bestCheap; ++i) answer.push_back(cheap[i].second);

    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