Submission #1253094

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253094		EJIC_B_KEDAX	Festival (IOI25_festival)	C++20	48 / 100	142 ms	25892 KiB

festival

#include "festival.h"
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

struct dp_helper {
    

};

vector<int> max_coupons(int A, vector<int> P, vector<int> T) {
    int n = P.size();
    vector<vector<pair<int, int>>> can(4);
    for (int i = 0; i < n; i++) {
        T[i]--;
        can[T[i]].emplace_back(P[i], i);
    }
    for (int i = 0; i < 4; i++) {
        ranges::sort(can[i]);
    }

    vector<ll> pref(can[0].size() + 1, 0);
    for (int i = 0; i < can[0].size(); i++) {
        pref[i + 1] = pref[i] + can[0][i].first;
    }

    map<tuple<int, int, int>, pair<ll, int>> dp_cur, dp_next;
    map<tuple<int, int, int>, pair<ll, int>> saved;
    dp_cur[{0, 0, 0}] = {A, -1};

    bool has_inf = false;
    ll inf = 2'000'000'000'000'000;

    auto update_with_incr = [&](int i, int j, int l, int tr) -> void {
        ll res = dp_cur[{i, j, l}].first;
        if (tr == 1) {
            if (can[1].size() > i && (res - can[1][i].first) * 2 > res) {
                if ((res - can[1][i].first) * 2 > inf) has_inf == true;
                dp_next[{i + 1, j, l}] = max(dp_next[{i + 1, j, l}], {(res - can[1][i].first) * 2, 1});
            }
        } else if (tr == 2) {
            if (can[2].size() > j && (res - can[2][j].first) * 3 > res) {
                if ((res - can[2][j].first) * 3 > inf) has_inf == true;
                dp_next[{i, j + 1, l}] = max(dp_next[{i, j + 1, l}], {(res - can[2][j].first) * 3, 2});
            }
        } else {
            if (can[3].size() > l && (res - can[3][l].first) * 4 > res) {
                if ((res - can[3][l].first) * 4 > inf) has_inf == true;
                dp_next[{i, j, l + 1}] = max(dp_next[{i, j, l + 1}], {(res - can[3][l].first) * 4, 3});
            }
        }
    };

    auto update_with = [&](int i, int j, int l, int tr) -> void {
        ll res = dp_cur[{i, j, l}].first;
        if (tr == 1) {
            if (can[1].size() > i && res - can[1][i].first >= 0) {
                dp_next[{i + 1, j, l}] = max(dp_next[{i + 1, j, l}], {(res - can[1][i].first) * 2, 1});
            }
        } else if (tr == 2) {
            if (can[2].size() > j && res - can[2][j].first >= 0) {
                dp_next[{i, j + 1, l}] = max(dp_next[{i, j + 1, l}], {(res - can[2][j].first) * 3, 2});
            }
        } else {
            if (can[3].size() > l && res - can[3][l].first >= 0) {
                dp_next[{i, j, l + 1}] = max(dp_next[{i, j, l + 1}], {(res - can[3][l].first) * 4, 3});
            }
        }
    };

    auto max_ans = [&](int i, int j, int l) -> int {
        int l1 = 0, r1 = can[0].size();
        ll have = dp_cur[{i, j, l}].first;
        while (l1 != r1) {
            int m = (l1 + r1 + 1) / 2;
            if (pref[m] <= have) {
                l1 = m;
            } else {
                r1 = m - 1;
            }
        }
        return i + j + l + l1;
    };

    int now_sum = 0;
    while (true) {
        ll lst = 0;
        for (auto [k, v] : dp_cur) {
            for (int tr = 1; tr < 4; tr++) {
                update_with_incr(get<0>(k), get<1>(k), get<2>(k), tr);
            }
            saved[k] = v;
            lst = v.first;
        }
        if (dp_next.empty()) {
            // assert(lst < 2'000'000'001 || now_sum == can[1].size() + can[2].size() + can[3].size());
            break;
        }
        if (dp_next.size() > 51 * 51 + 100) break;
        if (has_inf) break;

        swap(dp_cur, dp_next);
        dp_next.clear();
        now_sum++;
    }

    tuple<int, int, int> ans_coords = {-1, -1, -1};

    if (!has_inf && dp_next.size() > 51 * 51 + 100) {
        swap(dp_next, dp_cur);
        dp_next.clear();
        for (auto [k1, v1] : dp_cur) {
            for (auto [k2, v2] : dp_cur) {
                if (abs(get<0>(k1) - get<0>(k2)) < 52 &&
                    abs(get<1>(k1) - get<1>(k2)) < 52 &&
                    abs(get<2>(k1) - get<2>(k2)) < 52) {
                    continue;
                }

                auto need = k1;

                if (v1.first < v2.first) {
                    ans_coords = k2;
                    need = k2;
                } else {
                    ans_coords = k1;
                }

                while (get<0>(ans_coords) < get<0>(need) && !has_inf) {
                    update_with_incr(get<0>(ans_coords), get<1>(ans_coords), get<2>(ans_coords), 1);
                    saved[ans_coords] = dp_cur[ans_coords];
                    get<0>(ans_coords)++;
                    swap(dp_next, dp_cur);
                    dp_next.clear();
                }

                while (get<1>(ans_coords) < get<1>(need) && !has_inf) {
                    update_with_incr(get<0>(ans_coords), get<1>(ans_coords), get<2>(ans_coords), 2);
                    saved[ans_coords] = dp_cur[ans_coords];
                    get<1>(ans_coords)++;
                    swap(dp_next, dp_cur);
                    dp_next.clear();
                }

                while (get<2>(ans_coords) < get<2>(need) && !has_inf) {
                    update_with_incr(get<0>(ans_coords), get<1>(ans_coords), get<2>(ans_coords), 3);
                    saved[ans_coords] = dp_cur[ans_coords];
                    get<2>(ans_coords)++;
                    swap(dp_next, dp_cur);
                    dp_next.clear();
                }

                assert(has_inf);
                break;
            }
            if (has_inf) break;
        }
        assert(has_inf);
    }

    if (!has_inf) {

        for (auto [k, v] : dp_cur) {
            ans_coords = k;
        }

        ll have = dp_cur[ans_coords].first;

        while (can[1].size() > get<0>(ans_coords) && (have - can[1][get<0>(ans_coords)].first) * 2 == have) {
            get<0>(ans_coords)++;
            saved[ans_coords] = {have, 1};
        }

        while (can[2].size() > get<1>(ans_coords) && (have - can[2][get<1>(ans_coords)].first) * 3 == have) {
            get<1>(ans_coords)++;
            saved[ans_coords] = {have, 2};
        }

        while (can[3].size() > get<2>(ans_coords) && (have - can[3][get<2>(ans_coords)].first) * 4 == have) {
            get<2>(ans_coords)++;
            saved[ans_coords] = {have, 3};
        }

        dp_cur.clear();
        dp_cur[ans_coords] = saved[ans_coords];

        // assert(dp_cur[ans_coords].first < 2'000'000'001 || get<0>(ans_coords) + get<1>(ans_coords) + get<2>(ans_coords) == can[1].size() + can[2].size() + can[3].size());

        int ans = max_ans(get<0>(ans_coords), get<1>(ans_coords), get<2>(ans_coords));

        int old_sum = now_sum;
        for (; now_sum < old_sum + 32; now_sum++) {
            for (auto [k, v] : dp_cur) {
                for (int tr = 1; tr < 4; tr++) {
                    update_with(get<0>(k), get<1>(k), get<2>(k), tr);
                }
                saved[k] = v;
            }

            swap(dp_cur, dp_next);
            dp_next.clear();

            for (auto [k, v] : dp_cur) {
                int ma = max_ans(get<0>(k), get<1>(k), get<2>(k));
                if (ma > ans) {
                    ans = ma;
                    ans_coords = k;
                }
            }
        }

        vector<int> vans;
        have = saved[ans_coords].first;
        while (ans_coords != make_tuple(0, 0, 0)) {
            int tr = saved[ans_coords].second;
            if (tr == 1) {
                vans.push_back(can[1][get<0>(ans_coords) - 1].second);
                get<0>(ans_coords)--;
            } else if (tr == 2) {
                vans.push_back(can[2][get<1>(ans_coords) - 1].second);
                get<1>(ans_coords)--;
            } else {
                vans.push_back(can[3][get<2>(ans_coords) - 1].second);
                get<2>(ans_coords)--;
            }
        }

        ranges::reverse(vans);

        int ptr = 0;
        while (ptr < can[0].size() && have >= can[0][ptr].first) {
            have -= can[0][ptr].first;
            vans.push_back(can[0][ptr].second);
            ptr++;
        }

        return vans;
    }

    vector<int> vans;
    tuple<int, int, int> s = ans_coords;
    while (ans_coords != make_tuple(0, 0, 0)) {
        int tr = saved[ans_coords].second;
        if (tr == 1) {
            vans.push_back(can[1][get<0>(ans_coords) - 1].second);
            get<0>(ans_coords)--;
        } else if (tr == 2) {
            vans.push_back(can[2][get<1>(ans_coords) - 1].second);
            get<1>(ans_coords)--;
        } else {
            vans.push_back(can[3][get<2>(ans_coords) - 1].second);
            get<2>(ans_coords)--;
        }
    }

    ranges::reverse(vans);

    for (int i = 0; i < can[0].size(); i++) {
        vans.push_back(can[0][i].second);
    }

    for (int i = get<0>(s); i < can[1].size(); i++) {
        vans.push_back(can[1][i].second);
    }

    for (int i = get<1>(s); i < can[2].size(); i++) {
        vans.push_back(can[2][i].second);
    }

    for (int i = get<2>(s); i < can[3].size(); i++) {
        vans.push_back(can[3][i].second);
    }

    return vans;

}

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 12
• Subtask 4: 0 / 15
• Subtask 5: 27 / 27
• Subtask 6: 16 / 16
• Subtask 7: 0 / 18