제출 #1255558

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1255558		BigBadBully	Festival (IOI25_festival)	C++20	5 / 100	1097 ms	6036 KiB

festival

#include "festival.h"
#include <cassert>
#include <cstdio>
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
std::vector<int> max_coupons(int A, std::vector<int> v, std::vector<int> t)
{
    ll a = A;
    array<vector<int>, 5> mile;
    ll n = v.size();
    for (int i = 0; i < n; i++)
        mile[t[i]].push_back(i);
    for (int g = 1; g <= 4; g++)
        sort(mile[g].begin(), mile[g].end(), [&](int a, int b)
             { return v[a] < v[b]; });
    bool mozesve = 0;
    vector<int> uzet;
    vector<bool> ovde(n, 0);
    array<ll, 5> dosad = {0, 0, 0, 0, 0};
    while (1)
    {
        if (a > n * 1e9)
        {
            for (int i = 0; i < n; i++)
                if (!ovde[i])
                    uzet.push_back(i);
            return uzet;
        }
        bool gud = 0;
        for (ll g = 2; g <= 4; g++)
            if (dosad[g] < mile[g].size())
            {
                int idx = mile[g][dosad[g]];
                if (g * (a - v[idx]) >= a)
                {
                    uzet.push_back(idx);
                    gud = 1;
                    ovde[idx] = 1;
                    a = g * (a - v[idx]);
                    dosad[g]++;
                }
            }
        if (!gud)
            break;
    }
    int sz0 = mile[1].size();
    vector<ll> pref(sz0, 0);
    for (int i = 0; i < sz0; i++)
        pref[i] = (i > 0 ? pref[i - 1] : 0ll) + v[mile[1][i]];
    array<ll, 5> idi = dosad;
    for (int g = 2; g <= 4; g++)
    {
        ll val = a;
        ll &idx = idi[g];
        while (idx < mile[g].size() && g * (val - v[idx]) >= 0)
            val = g * (val - v[idx++]);
    }
    ll ans = -1;
    for (int it = 0; it < 2; it++)
    {
        ll res = -1;
        for (ll g1 = 0; g1 <= mile[1].size(); g1++)
            for (ll g2 = dosad[2]; g2 <= idi[2]; g2++)
                for (ll g3 = dosad[3]; g3 <= idi[3]; g3++)
                    for (ll g4 = dosad[4]; g4 <= idi[4]; g4++)
                    {
                        auto nv = dosad;
                        array<ll, 5> bnd = {0, g1, g2, g3, g4};
                        ll val = a;
                        while (1)
                        {
                            if (val < 0)
                                break;
                            bool naso = 0;
                            ll maxi = -1;
                            for (int g = 1; g <= 4; g++)
                                if (nv[g] < bnd[g])
                                    maxi = max(maxi, g * (val - v[mile[g][nv[g]]])), naso = 1;
                            if (!naso)
                                break;
                            for (int g = 4; g >= 1; g--)
                                if (nv[g] < bnd[g])
                                    if (g * (val - v[mile[g][nv[g]]]) == maxi)
                                    {
                                        nv[g]++;
                                        break;
                                    }
                            val = maxi;
                        }
                        if (val >= 0)
                        {
                            res = max(res, g2 - dosad[2] + g3 - dosad[3] + g4 - dosad[4] +
                                               g1);
                            if (it == 1 && res == ans)
                            {

                                nv = dosad;
                                val = a;
                                while (1)
                                {
                                    ll maxi = -1;
                                    bool naso = 0;
                                    for (int g = 1; g <= 4; g++)
                                        if (nv[g] < bnd[g])
                                            maxi = max(maxi, g * (val - v[mile[g][nv[g]]])), naso = 1;
                                    if (!naso)
                                        break;
                                    for (int g = 4; g >= 1; g--)
                                        if (nv[g] < bnd[g])
                                            if (g * (val - v[mile[g][nv[g]]]) == maxi)
                                            {
                                                uzet.push_back(mile[g][nv[g]++]);
                                                break;
                                            }
                                    val = maxi;
                                }
                                return uzet;
                            }
                        }
                    }
        ans = res;
    }
    return uzet;
}

• 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