Submission #1253674

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253674		fasterthanyou	Festival (IOI25_festival)	C++20	5 / 100	116 ms	17092 KiB

festival

#include <bits/stdc++.h>

#include <ranges>
using namespace std;

#ifdef LOCAL
#include "../../debug.h"
#else
#define debug(...) 42
#endif

namespace utils {
template <typename T>
bool chMax(T& target, const T& value) {
    if (value > target) {
        target = value;
        return true;
    }
    return false;
}

template <typename T>
bool chMin(T& target, const T& value) {
    if (value < target) {
        target = value;
        return true;
    }
    return false;
}
}  // namespace utils
using namespace utils;

using ll = long long;
using ld = long double;
using mp = vector<vector<int>>;
const char el = '\n';

vector<int> max_coupons(int A, vector<int> P, vector<int> T) {
    using cp = pair<ll, int>;
    set<cp> coupons[5];
    int N = P.size();
    for (int i = 0; i < N; i++) {
        coupons[T[i]].insert({P[i], i});
    }

    vector<int> ans;
    while (true) {
        if (A == 0) break;

        int best = -1;
        int best_t = -1;
        for (int t = 1; t <= 4; ++t) {
            if (coupons[t].empty()) continue;
            auto it = coupons[t].begin();
            ll new_A = (A - it->first) * t;
            if (new_A > best) {
                best = new_A;
                best_t = t;
            }
        }

        if (best_t == -1) break;
        A = best;
        debug(A);
        ans.push_back(coupons[best_t].begin()->second);
        coupons[best_t].erase(coupons[best_t].begin());
    }

    debug(ans); 
    return ans;
}

// int main() {
//     max_coupons(13, {4, 500, 8, 14}, {1, 3, 3, 4});
//     return 0;
// }

• 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: 0 / 16
• Subtask 7: 0 / 18