Submission #1253445

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253445		flashmt	Festival (IOI25_festival)	C++20	100 / 100	86 ms	9020 KiB

festival

#include "festival.h"
#include <bits/stdc++.h>
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;
  };

  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);
  sort(begin(ids), end(ids), comp);

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

  if (bound == n)
    return ids;

  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