Submission #1253772

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253772		bynix	Festival (IOI25_festival)	C++20	100 / 100	70 ms	13112 KiB

festival

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

typedef long long ll;
const ll lim = 1e18;

vector<int> max_coupons(int Ai, vector<int> Pi, vector<int> Ti){
  ll A = (ll) Ai;
  vector<ll> P, T;
  for (auto &e: Pi) P.push_back((ll) e);
  for (auto &e: Ti) T.push_back((ll) e);
  ll N = P.size();
  vector<ll> R;

  vector<ll> type1, temp;
  for (int i = 0; i < N; i++) {
    if (T[i] == 1) type1.push_back(i);
    else temp.push_back(i);
  }

  sort(type1.begin(), type1.end(), [&](ll& a, ll& b){return P[a] < P[b];});
  ll t1s = type1.size();
  vector<ll> pre(t1s + 1, -1);
  pre[0] = 0;
  for (int i = 0; i < t1s; i++){
    pre[i+1] = pre[i] + P[type1[i]];
    pre[i+1] = min(pre[i+1], lim);
  }


  sort(temp.begin(), temp.end(), [&](ll& a, ll& b){return T[b]*P[b]*(T[a] - 1) > T[a]*P[a]*(T[b] - 1);});
  ll ts = temp.size();
  ll oldM = A, lowI = -1;
  for (int i = 0; i < ts; i++){
    ll newM = (oldM - P[temp[i]])*T[temp[i]];
    newM = min(newM, lim);
    if (newM < oldM){ lowI = i; break; }
    oldM = newM;
  }
  if (lowI == -1) lowI = ts;
  for (int i = 0; i < lowI; i++) R.push_back(temp[i]);
  
  if (lowI < ts){
    vector<ll> t;
    map<ll, ll> frq;
    for (int i = lowI; i < ts; i++){
      frq[T[temp[i]]]++;
      if (frq[T[temp[i]]] <= 32) t.push_back(temp[i]);
    }
    ts = t.size();
    
    vector<vector<ll>> dp(ts+1, vector<ll>(ts+1, -1)), log(ts+1, vector<ll>(ts+1, -1));
    dp[0][0] = oldM;
    for (int i = 1; i <= ts; i++){
      for (int j = 0; j < i; j++){
        dp[i][j] = dp[i - 1][j];
        if (dp[i][j] < 0) break;
        dp[i][j] = min(dp[i][j], lim);
      }
      for (int j = 1; j <= i; j++){
        ll val = (dp[i-1][j-1] - P[t[i-1]]) * T[t[i-1]];
        val = min(val, lim);
        if (val >= dp[i][j]) dp[i][j] = val, log[i][j] = j;
        if (dp[i][j] < 0) break;
        dp[i][j] = min(dp[i][j], lim);
      }
    }

    ll maxCount = 0, t1Count = 0, tCount = 0;
    for (int i = 0; i <= ts; i++){
      oldM = min(dp[ts][i], lim);
      ll pos = upper_bound(pre.begin(), pre.end(), oldM) - pre.begin() - 1;
      pos = min(pos, t1s), pos = max(pos, 0ll);
      if (pos + i >= maxCount && oldM - pre[pos] >= 0) maxCount = pos + i, t1Count = pos, tCount = i;
    }

    vector<ll> R2;
    ll b = 0, i = ts, j = tCount;
    for (; i > 0; i--){
      if (b >= tCount) break;
      if (log[i][j] >= 0) R2.push_back(t[i-1]), b++, j = log[i][j] - 1;
    }
    reverse(R2.begin(), R2.end());

    for (auto &e: R2) R.push_back(e);
    for (int i = 0; i < t1Count; i++) R.push_back(type1[i]);

  } else {
    for (int i = 1; i <= t1s; i++)
      if (pre[i] <= oldM) R.push_back(type1[i-1]);
  }

  vector<int> intR;
  for (auto &e: R) intR.push_back((int) e);
  return intR;
}

• 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