Submission #1251295

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251295		jtnydv25	Festival (IOI25_festival)	C++20	100 / 100	179 ms	175772 KiB

festival

#include "festival.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define all(c) ((c).begin()), ((c).end())
#define sz(x) ((int)(x).size())

#ifdef LOCAL
#include <print.h>
#else
#define trace(...)
#define endl "\n" // remove in interactive
#endif

std::vector<int> max_coupons(int AA, std::vector<int> PP, std::vector<int> TT) {
  ll A = AA;
  int n = sz(PP);
  vector<ll> P(n), T(n);
  for(int i = 0; i < n; i++){
      P[i] = PP[i];
      T[i] = TT[i];
  }
  
  vector<int> perm(n);
  iota(all(perm), 0);
  sort(all(perm), [&](int i, int j) {
      if(T[i] == T[j]) return P[i] < P[j];
      return P[i] * T[i] * T[j] + P[j] * T[j] < P[j] * T[i] * T[j] + P[i] * T[i];
      // equivalent to: P[i] * T[i]/(T[i] - 1) < P[j] * T[j]/(T[j] - 1) => valid comparator
  });

  int I = 0; while(I < n && T[perm[I]] > 1) I++;
  // trace(I);
  vector<ll> X_min(I + 1, LLONG_MAX);
  vector<ll> suff(n + 1);

  for(int i = n - 1; i >= 0; i--) suff[i] = suff[i + 1] + P[perm[i]];
  // trace(perm);
  for(int i = I - 1; i >= 0; i--){
      ll p = P[perm[i]];
      ll t = T[perm[i]];
      // (X - p) * t >= X
      // X >= p * t / (t - 1)
      X_min[i] = min(X_min[i + 1], (p * t + t - 2) / (t - 1));
  }

  const int MX = 100; // No more than 3 * 32 reductions!
  int J = 0;
  vector<int> ans;
  while(J < I){
      if(A >= suff[0]){
          ans.clear();
          for(int i = 0; i < n; i++) ans.push_back(perm[i]);
          return ans;
      }
      ll p = P[perm[J]];
      ll t = T[perm[J]];
      if(A >= X_min[J]){
          if( (A - p) * t >= A){
              ans.push_back(perm[J]);
              A = (A - p) * t;
          }
          J++;
      } else break;
  }
  vector<vector<ll>> dp(n + 1, vector<ll>(MX + 1, -1));
  dp[J][0] = A;
  for(int i = J; i < I; i++){
      for(int j = 0; j <= MX; j++){
          if(dp[i][j] == -1) continue;
          ll p = P[perm[i]];
          ll t = T[perm[i]];
          dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]); // skip
          if(j < MX && dp[i][j] >= p){
              ll X = (dp[i][j] - p) * t;
              dp[i + 1][j + 1] = max(dp[i + 1][j + 1], X);
          }
      }
  }
  int best = 0, best_j = 0;
  for(int j = 0; j <= MX; j++){
      ll R = dp[I][j];
      if(R < 0)  continue;
      // [I, I + 1, .., j-1] => suff[I] - suff[j] <= R

      int lo = I, hi = n;
      while(lo < hi){
          int mid = (lo + hi + 1) / 2;
          if(suff[I] - suff[mid] <= R) lo = mid;
          else hi = mid - 1;
      }
      if(lo - I + j > best){
          best = lo - I + j;
          best_j = j;
      }
  }
  int osz = sz(ans);
  int j = best_j;
  for(int i = I; i > J; i--){
      if(dp[i][j] == dp[i - 1][j]) continue; // skip
      ans.push_back(perm[i - 1]);
      j--;
  }
  reverse(ans.begin() + osz, ans.end());
  for(int i = I + best - best_j - 1; i >= I; i--) ans.push_back(perm[i]);
  // reverse(all(ans));
  // trace(ans);
  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