Submission #1255607

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255607		BigBadBully	Festival (IOI25_festival)	C++20	40 / 100	58 ms	8888 KiB

festival

#include "festival.h"
#include <cassert>
#include <cstdio>
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll inf = 1e18;
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]; });
    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;
        ll maxi = -1;
        for (int it = 0; it < 2; it++)
            for (ll g = 4; g >= 2; g--)
                if (dosad[g] < mile[g].size())
                {
                    int idx = mile[g][dosad[g]];
                    if (g * (a - v[idx]) >= a)
                    {

                        gud = 1;
                        if (it == 1 && maxi == g * (a - v[idx]))
                        {
                            uzet.push_back(idx);
                            ovde[idx] = 1;
                            a = g * (a - v[idx]);
                            dosad[g]++;
                            break;
                        }
                        maxi = max(maxi, g * (a - v[idx]));
                    }
                }
        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]];
    vector<ll> dp[30][30][30];
    for (int i1 = 0; i1 < 30; i1++)
        for (int i2 = 0; i2 < 30; i2++)
            for (int i3 = 0; i3 < 30; i3++)
                dp[i1][i2][i3] = {-inf};
    dp[0][0][0] = {a};
    function<vector<ll>(array<int, 5>)> dfs = [&](array<int, 5> g) -> vector<ll>
    {
        if (dp[g[2]][g[3]][g[4]][0] > -inf)
            return dp[g[2]][g[3]][g[4]];
        ll maxi = -13;
        for (int i = 2; i <= 4; i++)
            if (g[i] > 0 && dosad[i] + g[i] - 1 < mile[i].size())
            {
                auto fk = g;
                fk[i]--;
                auto val = dfs(fk);
                if (val[0] < 0)
                    continue;
                maxi = max(maxi, i * (val[0] - v[mile[i][dosad[i] + g[i] - 1]]));
            }
        if (maxi < 0)
            return dp[g[2]][g[3]][g[4]] = {-inf + 1};
        for (int i = 2; i <= 4; i++)
            if (g[i] > 0 && dosad[i] + g[i] - 1 < mile[i].size())
            {
                auto fk = g;
                fk[i]--;
                auto val = dfs(fk);
                if (val[0] < 0)
                    continue;
                if (i * (val[0] - v[mile[i][dosad[i] + g[i] - 1]]) == maxi)
                {
                    val[0] = i * (val[0] - v[mile[i][dosad[i] + g[i] - 1]]);
                    val.push_back(mile[i][dosad[i] + g[i] - 1]);
                    dp[g[2]][g[3]][g[4]] = val;
                    break;
                }
            }
        return dp[g[2]][g[3]][g[4]];
    };
    ll ans = -1;
    for (ll it = 0; it < 2; it++)
        for (ll g2 = 0; g2 < 30; g2++)
            for (int g3 = 0; g3 < 30; g3++)
                for (int g4 = 0; g4 < 30; g4++)
                {
                    auto arr = dfs({0, 0, g2, g3, g4});
                    if (arr[0] < 0)
                        continue;
                    ll cm = g2 + g3 + g4 + upper_bound(pref.begin(), pref.end(), arr[0]) - pref.begin();
                    if (it == 0)
                        ans = max<ll>(ans, cm);
                    if (it == 1 && cm == ans)
                    {
                        int vl = arr[0];
                        arr.erase(arr.begin());
                        for (int x : arr)
                            uzet.push_back(x);
                        int bnd = (upper_bound(pref.begin(), pref.end(), vl) - pref.begin());
                        for (int i = 0; i < bnd; i++)
                            uzet.push_back(mile[1][i]);
                        return uzet;
                    }
                }

    return uzet;
}

Compilation message (stderr)

festival.cpp: In function 'std::vector<int> max_coupons(int, std::vector<int>, std::vector<int>)':
festival.cpp:106:43: warning: narrowing conversion of 'g2' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
  106 |                     auto arr = dfs({0, 0, g2, g3, g4});
      |                                           ^~

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