제출 #1252450

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1252450		flashmt	Festival (IOI25_festival)	C++20	66 / 100	77 ms	8244 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;
  };

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

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

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

  int maxT = *max_element(begin(T), end(T));

  // sub 1 + 2 + 3
  if (maxT <= 2)
  {
    int best = -1;
    vector<int> buy;
    long long has = A;
    for (int i = 0; i <= int(size(a[2])); i++)
    {
      int u = upper_bound(begin(sum1), end(sum1), has) - begin(sum1) - 1;
      if (u + i > best)
      {
        best = u + i;
        buy = {u, i};
      }

      if (i == int(size(a[2])))
        break;

      auto [x, _] = a[2][i];
      if (has < x)
        break;

      has = min((has - x) * 2, oo);
    }

    vector<int> ans;
    for (int i = size(buy) - 1; i >= 0; i--)
      for (int j = 0; j < buy[i]; j++)
        ans.push_back(a[i + 1][j].second);
    return ans;
  }

  // sub 4
  if (n <= 70)
  {
    int best = -1;
    vector<int> ans;
    for (int i = 0; i <= int(size(a[2])); i++)
      for (int j = 0; j <= int(size(a[3])); j++)
        for (int k = 0; k <= int(size(a[4])); k++)
        {
          vector<int> ids;
          for (int u = 0; u < i; u++)
            ids.push_back(a[2][u].second);
          for (int u = 0; u < j; u++)
            ids.push_back(a[3][u].second);
          for (int u = 0; u < k; u++)
            ids.push_back(a[4][u].second);

          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)
              break;
          }

          if (has < 0)
            continue;

          int u = upper_bound(begin(sum1), end(sum1), has) - begin(sum1) - 1;
          int sz = size(ids);
          if (u + sz > best)
          {
            best = u + sz;
            ans = ids;
            for (int q = 0; q < u; q++)
              ans.push_back(a[1][q].second);
          }
        }

    return ans;
  }

  // sub 5
  vector<int> ids(n);
  iota(begin(ids), end(ids), 0);
  sort(begin(ids), end(ids), comp);

  return ids;
}

• 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: 0 / 16
• Subtask 7: 0 / 18