제출 #1276487

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

festival

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

struct Coupon {
    int idx;          // original index
    long long p;      // price
    int t;            // type (multiplier)
};

/*  comparison for coupons with T > 1:
    increasing K = p * t / (t-1)
    (compare a.p * a.t * (b.t-1)  with  b.p * b.t * (a.t-1) )
*/
bool cmpK(const Coupon& a, const Coupon& b) {
    // both a.t > 1 and b.t > 1
    __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;
    // tie‑break – any deterministic rule is fine
    if (a.t != b.t) return a.t > b.t;        // larger multiplier first
    return a.p > b.p;                         // larger price first
}

/* ------------------------------------------------------------ */

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

    /* split coupons */
    vector<Coupon> pos, ones;
    for (int i = 0; i < N; ++i) {
        if (T[i] > 1)
            pos.push_back({i, P[i], T[i]});
        else
            ones.push_back({i, P[i], T[i]});   // T == 1
    }

    /* sort as proved in the analysis */
    sort(pos.begin(), pos.end(), cmpK);                 // increasing K
    sort(ones.begin(), ones.end(),
         [](const Coupon& a, const Coupon& b) {
             return a.p < b.p;                         // cheapest first
         });

    vector<Coupon> all;
    all.reserve(N);
    all.insert(all.end(), pos.begin(), pos.end());
    all.insert(all.end(), ones.begin(), ones.end());
    const int M = (int)all.size();                     // M == N

    /* DP */
    const __int128 INF = (__int128)1 << 120;           // huge enough

    vector<vector<__int128>> dp(M + 1, vector<__int128>(M + 1, -1));
    vector<vector<char>>   take(M + 1, vector<char>(M + 1, 0));

    dp[0][0] = (__int128)A;

    for (int i = 1; i <= M; ++i) {
        const Coupon& c = all[i - 1];
        dp[i][0] = dp[i - 1][0];
        take[i][0] = 0;
        for (int k = 1; k <= i; ++k) {
            /* skip */
            dp[i][k] = dp[i - 1][k];
            take[i][k] = 0;

            /* take */
            if (dp[i - 1][k - 1] != -1 && dp[i - 1][k - 1] >= c.p) {
                __int128 base = dp[i - 1][k - 1] - c.p;
                __int128 after;
                if (base > INF / c.t) after = INF;
                else after = base * (__int128)c.t;
                if (after > dp[i][k]) {
                    dp[i][k] = after;
                    take[i][k] = 1;
                }
            }
        }
    }

    /* best obtainable number of coupons */
    int best = 0;
    for (int k = M; k >= 0; --k) {
        if (dp[M][k] != -1) {
            best = k;
            break;
        }
    }

    /* reconstruction */
    vector<int> answer;
    int i = M, k = best;
    while (i > 0) {
        if (take[i][k]) {
            answer.push_back(all[i - 1].idx);
            --k;
        }
        --i;
    }
    reverse(answer.begin(), answer.end());
    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