Submission #1255604

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255604		BigBadBully	Festival (IOI25_festival)	C++20	40 / 100	60 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;
        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)
                {
                    uzet.push_back(idx);
                    gud = 1;
                    ovde[idx] = 1;
                    a = g * (a - v[idx]);
                    dosad[g]++;
                    break;
                }
            }
        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:99:37: warning: narrowing conversion of 'g2' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
   99 |                 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