Submission #1253692

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253692		fasterthanyou	Festival (IOI25_festival)	C++20	0 / 100	134 ms	151736 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';

int memo[71][71][71][71];

vector<int> max_coupons(int A, vector<int> P, vector<int> T) {
    using cp = pair<ll, int>;
    vector<vector<cp>> coupons(5);

    int N = P.size();
    for (int i = 0; i < N; ++i) {
        coupons[T[i]].emplace_back(P[i], i);
    }

    for (int i = 1; i <= 4; ++i) {
        ranges::sort(coupons[i]);
        debug(i, coupons[i]);
    }

    memset(memo, -1, sizeof(memo));

    function<int(int, int, int, int, ll)> dp = [&](int a, int b, int c, int d, ll tk) {
        int &ret = memo[a][b][c][d];
        if (ret != -1) return ret;

        ret = 0;
        if (a + b + c + d == N or tk == 0) {
            return ret;
        }

        if (a < (int)coupons[1].size() and coupons[1][a].first <= tk) {
            ret = max(ret, dp(a + 1, b, c, d, tk - coupons[1][a].first) + 1);
        }
        if (b < (int)coupons[2].size() and coupons[2][b].first <= tk) {
            ret = max(ret, dp(a, b + 1, c, d, (tk - coupons[2][b].first) * 2) + 1);
        }
        if (c < (int)coupons[3].size() and coupons[3][c].first <= tk) {
            ret = max(ret, dp(a, b, c + 1, d, (tk - coupons[3][c].first) * 3) + 1);
        }
        if (d < (int)coupons[4].size() and coupons[4][d].first <= tk) {
            ret = max(ret, dp(a, b, c, d + 1, (tk - coupons[4][d].first) * 4) + 1);
        }
        
        return ret;
    };

    int res = dp(0, 0, 0, 0, A);
    debug(res);

    vector<int> ans;
    vector<int> p(5, 0);
    ll tk = A;
    while (true) {
        int a = p[1], b = p[2], c = p[3], d = p[4];
        if (a + b + c + d == N or tk == 0) break;

        int best = 0;
        int best_type = 0;
        for (int i = 1; i <= 4; ++i) {
            if (p[i] < (int)coupons[i].size() && coupons[i][p[i]].first <= tk) {
                int new_value = 1 + dp(a + (i == 1), b + (i == 2), c + (i == 3), d + (i == 4), (tk - coupons[i][p[i]].first) * i);
                if (new_value > best) {
                    best = new_value;
                    best_type = i;
                }
            }
        }

        if (best == 0) break;
        ans.push_back(coupons[best_type][p[best_type]].second);
        tk = (tk - coupons[best_type][p[best_type]].first) * best_type;
        p[best_type]++;
        debug(p[1], p[2], p[3], p[4], tk);
    }

    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: 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