제출 #1276468

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

festival

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

using int64 = long long;
using i128 = __int128_t;

struct Mult {
    int idx;
    int64 P;
    int T;
};

static bool cmpMult(const Mult& a, const Mult& b) {
    // Compare a.P * a.T / (a.T-1)  <  b.P * b.T / (b.T-1)
    // cross‑multiply: a.P * a.T * (b.T-1)  <  b.P * b.T * (a.T-1)
    i128 left  = (i128)a.P * a.T * (b.T - 1);
    i128 right = (i128)b.P * b.T * (a.T - 1);
    return left < right;
}

vector<int> max_coupons(int A, vector<int> P, vector<int> T) {
    int N = (int)P.size();
    vector<Mult> mult;
    vector<int> oneIdx;               // indices with T == 1
    for (int i = 0; i < N; ++i) {
        if (T[i] == 1) oneIdx.push_back(i);
        else mult.push_back({i, (int64)P[i], T[i]});
    }

    // sort multipliers by the metric Pi*Ti/(Ti-1)
    sort(mult.begin(), mult.end(), cmpMult);
    int M = (int)mult.size();

    const i128 INF = (i128)4'000'000'000'000'000'000LL;   // 4·10^18, far larger than any needed value

    // dp[i][k] = maximal token after considering first i multipliers and taking exactly k of them
    vector<vector<i128>> dp(M + 1, vector<i128>(M + 1, -1));
    vector<vector<char>> take(M + 1, vector<char>(M + 1, 0));
    dp[0][0] = (i128)A;

    for (int i = 1; i <= M; ++i) {
        const Mult& cur = mult[i - 1];
        // not taking this coupon
        for (int k = 0; k <= i; ++k) {
            dp[i][k] = dp[i - 1][k];
            take[i][k] = 0;
        }
        // trying to take it
        for (int k = 1; k <= i; ++k) {
            if (dp[i - 1][k - 1] != -1 && dp[i - 1][k - 1] >= (i128)cur.P) {
                i128 newToken = (dp[i - 1][k - 1] - (i128)cur.P) * (i128)cur.T;
                if (newToken > INF) newToken = INF;
                if (newToken > dp[i][k]) {
                    dp[i][k] = newToken;
                    take[i][k] = 1;
                } else if (newToken == dp[i][k] && !take[i][k]) {
                    // Prefer a path that takes the coupon (helps reconstruction)
                    take[i][k] = 1;
                }
            }
        }
    }

    // sort type‑1 coupons by price (to maximise count later)
    sort(oneIdx.begin(), oneIdx.end(),
         [&](int a, int b) { return P[a] < P[b]; });

    int bestTotal = -1;
    int bestK = 0;
    i128 bestToken = -1;

    // evaluate each possible number of taken multipliers
    for (int k = 0; k <= M; ++k) {
        if (dp[M][k] == -1) continue;
        i128 token = dp[M][k];
        i128 cur = token;
        int tCnt = 0;
        for (int idx : oneIdx) {
            if (cur >= (i128)P[idx]) {
                cur -= (i128)P[idx];
                ++tCnt;
            } else break;
        }
        int total = k + tCnt;
        if (total > bestTotal) {
            bestTotal = total;
            bestK = k;
            bestToken = token;
        }
    }

    // reconstruct the chosen multipliers
    vector<int> answer;
    int curK = bestK;
    for (int i = M; i >= 1; --i) {
        if (curK > 0 && take[i][curK]) {
            answer.push_back(mult[i - 1].idx);
            --curK;
        }
    }
    reverse(answer.begin(), answer.end());

    // apply the remaining token to take type‑1 coupons greedily
    i128 token = bestToken;
    for (int idx : oneIdx) {
        if (token >= (i128)P[idx]) {
            token -= (i128)P[idx];
            answer.push_back(idx);
        } else break;
    }
    return answer;
}

• 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