Submission #1253440

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253440		flashmt	Festival (IOI25_festival)	C++20	100 / 100	85 ms	8760 KiB

festival

#include "festival.h"
#include <bits/stdc++.h>
#ifdef LOCAL
#include "Debug.h"
#else
#define debug(...) 42
#endif
using namespace std;
const long long oo = 1LL << 60;

vector<int> max_coupons(int A, vector<int> P, vector<int> T) {
  auto comp = [&](int u, int v)
  {
    long long costUV = 1LL * P[u] * T[u] * T[v] + 1LL * P[v] * T[v];
    long long costVU = 1LL * P[v] * T[v] * T[u] + 1LL * P[u] * T[u];
    return costUV < costVU;
  };

  auto buy = [&](vector<int> &ids)
  {
    sort(begin(ids), end(ids), comp);
    long long has = A;
    for (int i : ids)
    {
      has = min((has - P[i]) * T[i], oo);
      if (has < 0)
        return has;
    }
    return has;
  };

  vector<pair<int, int>> a[4];
  int n = size(P);
  for (int i = 0; i < n; i++)
    a[T[i] - 1].push_back({P[i], i});

  for (int i = 0; i < 4; i++)
    sort(begin(a[i]), end(a[i]));

  vector<long long> sum1 = {0};
  for (auto [x, _] : a[0])
    sum1.push_back(sum1.back() + x);

  vector<int> ids(n);
  iota(begin(ids), end(ids), 0);
  if (buy(ids) >= 0)
    return ids;


  int bound = 0;
  long long curA = A;
  vector<int> prefixAns;
  while (bound < n)
  {
    int i = ids[bound];
    long long newA = (curA - P[i]) * T[i];
    if (newA < curA)
      break;
    curA = newA;
    prefixAns.push_back(i);
    bound++;
  }

  vector<vector<int>> cand(4);
  for (int i = bound; i < n; i++)
  {
    int id = ids[i];
    if (T[id] >= 2)
      cand[T[id] - 1].push_back(i);
  }

  int best = -1, ans1 = -1;
  vector<int> suffixAns;
  for (int i = 0; i <= min(int(size(cand[1])), 35); i++)
    for (int j = 0; j <= min(int(size(cand[2])), 25); j++)
      for (int k = 0; k <= min(int(size(cand[3])), 20); k++)
      {
        vector<int> useIds;
        for (int u = 0; u < i; u++)
          useIds.push_back(cand[1][u]);
        for (int u = 0; u < j; u++)
          useIds.push_back(cand[2][u]);
        for (int u = 0; u < k; u++)
          useIds.push_back(cand[3][u]);

        sort(begin(useIds), end(useIds));
        long long has = curA;
        for (int pos : useIds)
        {
          int id = ids[pos];
          has = (has - P[id]) * T[id];
          if (has < 0)
            break;
        }
        if (has < 0)
          continue;

        int cnt1 = upper_bound(begin(sum1), end(sum1), has) - begin(sum1) - 1;
        int sz = size(useIds);
        if (sz + cnt1 > best)
        {
          best = sz + cnt1;
          suffixAns.clear();
          for (int pos : useIds)
            suffixAns.push_back(ids[pos]);
          ans1 = cnt1;
        }
      }

  vector<int> ans = prefixAns;
  for (int x : suffixAns)
    ans.push_back(x);
  for (int i = 0; i < ans1; i++)
    ans.push_back(a[0][i].second);
  return ans;
}

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