Submission #1261360

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261360		Faggi	Festival (IOI25_festival)	C++20	12 / 100	1094 ms	9160 KiB

festival

#include <bits/stdc++.h>
#define ll long long
#define sz(x) int(x.size())
#define forn(i, n) for (i = 0; i < n; i++)
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define fr first
#define se second
using namespace std;
ll INF = 2e14;
vector<pair<ll, ll>> v[5];
bool todo=0;
vector<int> fal(vector<ll>in)
{
  todo=1;
  vector<int>a;
  ll i, j;
  for(i=1; i<=4; i++)
  {
    for(j=in[i]; j<sz(v[i]); j++)
    {
      a.pb(v[i][j].se);
    }
  }
  return a;
}

vector<int> calc(ll t, ll A, vector<ll> in)
{
  vector<int> mej, a, b;
  if (t == 0)
    return mej;
  mej = calc(t - 1, A, in);
  ll i, j;
  bool ag = 1;
  while (ag)
  {
    ag = 0;
    for (j = 2; j < t; j++)
    {
      while (in[j] < sz(v[j]) && (A / j) >= v[j][in[j]].fr)
      {
        A = A - v[j][in[j]].fr;
        A = A * j;
        a.pb(v[j][in[j]].se);
        in[j]++;
        ag = 1;
        if (A >= INF)
        {
          b = fal(in);
          for (auto k : b)
          {
            a.pb(k);
          }
          return a;
        }
      }
    }
  }
  for (i = 0; i < sz(v[t]); i++)
  {
    a.pb(v[t][i].se);
    A = A - v[t][i].fr;
    if (A < 0)
      break;
    A = A * t;
    if (A >= INF)
    {
      b = fal(in);
      for (auto k : b)
      {
        a.pb(k);
      }
      return a;
    }
    ag = 1;
    in[t] = i;
    while (ag)
    {
      ag = 0;
      for (j = 2; j < t; j++)
      {
        while (in[j] < sz(v[j]) && (A / j) >= v[j][in[j]].fr)
        {
          A = A - v[j][in[j]].fr;
          A = A * j;
          a.pb(v[j][in[j]].se);
          in[j]++;
          ag = 1;
          if (A >= INF)
          {
            b = fal(in);
            for (auto k : b)
            {
              a.pb(k);
            }
            return a;
          }
        }
      }
    }

    b = calc(t-1, A, in);
    if (sz(a) + sz(b) > sz(mej))
    {
      mej = a;
      for (auto k : b)
        mej.pb(k);
    }
  }
  return mej;
}

std::vector<int> max_coupons(int A, std::vector<int> P, std::vector<int> T)
{
  ll i, n = sz(P);
  vector<ll> in(5, 0);
  for (i = 0; i < n; i++)
  {
    v[T[i]].pb({P[i], i});
  }
  for (i = 1; i <= 4; i++)
    sort(all(v[i]));
  return calc(4, A, in);
}

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