제출 #1276494

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1276494		mehrzad	축제 (IOI25_festival)	C++17	12 / 100	1037 ms	2162688 KiB

festival

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

const long long INF = (1LL << 60);          // large enough, behaves as "infinite"

struct Coupon {
    int idx;            // original index
    long long price;
    int    t;           // multiplier (2,3,4)
};

/* comparison by  need = price * t / (t-1)  (ascending)                */
static bool needCmp(const Coupon& a, const Coupon& b) {
    // compare a.price * a.t * (b.t-1)  <  b.price * b.t * (a.t-1)
    __int128 lhs = (__int128)a.price * a.t * (b.t - 1);
    __int128 rhs = (__int128)b.price * b.t * (a.t - 1);
    return lhs < rhs;
}

/* multiply with saturation at INF                                        */
static long long mul_sat(long long x, int mul) {
    if (x >= INF) return INF;
    __int128 prod = (__int128)x * mul;
    if (prod > INF) return INF;
    return (long long)prod;
}

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

    /* split coupons ----------------------------------------------------- */
    vector<Coupon> mult;                     // T > 1
    vector<pair<long long,int>> cheap;       // T == 1   (price , original idx)

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

    /* sort cheap by price, mult by need (see Lemma 1) -------------------- */
    sort(cheap.begin(), cheap.end(),
         [](const auto& a, const auto& b){ return a.first < b.first; });
    sort(mult.begin(), mult.end(), needCmp);

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

    /* DP tables ---------------------------------------------------------- */
    // dp[i][k] – after first i coupons, taking exactly k of them,
    // maximum token amount ( -1 = unreachable )
    vector<vector<long long>> dp(M+1, vector<long long>(M+1, -1));
    vector<vector<char>> take(M+1, vector<char>(M+1, 0)); // did we take i‑th coupon?
    dp[0][0] = A;

    for (int i = 1; i <= M; ++i) {
        const Coupon &c = mult[i-1];
        for (int k = 0; k <= i; ++k) {
            // case: do not take this coupon
            dp[i][k] = dp[i-1][k];
            take[i][k] = 0;

            // case: take it (need k>=1)
            if (k > 0 && dp[i-1][k-1] >= c.price) {
                long long before = dp[i-1][k-1] - c.price;
                long long after  = mul_sat(before, c.t);
                if (after > dp[i][k]) {
                    dp[i][k] = after;
                    take[i][k] = 1;
                }
            }
        }
    }

    /* prefix sums of cheap coupons --------------------------------------- */
    int Ccheap = (int)cheap.size();
    vector<long long> pref(Ccheap+1, 0);
    for (int i = 1; i <= Ccheap; ++i) pref[i] = pref[i-1] + cheap[i-1].first;

    /* find best total ---------------------------------------------------- */
    int bestK = 0;
    int bestCheap = 0;
    long long bestToken = -1;
    int bestTotal = -1;
    for (int k = 0; k <= M; ++k) {
        long long tok = dp[M][k];
        if (tok < 0) continue;
        int cheapCnt;
        if (tok >= INF) {
            cheapCnt = Ccheap;
        } else {
            // largest w with pref[w] <= tok
            cheapCnt = (int)(upper_bound(pref.begin(), pref.end(), tok) - pref.begin() - 1);
        }
        int total = k + cheapCnt;
        if (total > bestTotal) {
            bestTotal = total;
            bestK = k;
            bestCheap = cheapCnt;
            bestToken = tok;
        }
    }

    if (bestTotal <= 0) return {};   // nothing can be bought

    /* reconstruct the chosen mult coupons -------------------------------- */
    vector<int> seqMult;
    int i = M, k = bestK;
    while (i > 0) {
        if (take[i][k]) {
            seqMult.push_back(mult[i-1].idx);
            --k;
        }
        --i;
    }
    reverse(seqMult.begin(), seqMult.end());

    /* add the cheap coupons                                               */
    vector<int> result = seqMult;
    for (int i = 0; i < bestCheap; ++i) result.push_back(cheap[i].second);

    return result;
}

• 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