Submission #1255885

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255885		eradax	Festival (IOI25_festival)	C++20	5 / 100	80 ms	47276 KiB

festival

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

#ifndef EVAL
#define dbg(expr) cerr << "[" << __FUNCTION__ << ", " << __LINE__ << "] " << #expr << ": " << expr << endl
#else
#define dbg(expr)
#endif

using ll = long long;
using vl = vector<ll>;
using vvl = vector<vl>;

using vi = vector<int>;
using vvi = vector<vi>;

using a3 = array<ll, 3>;
using v3 = vector<a3>;

#define sz(c) ((int)c.size())

vi max_coupons(int _a, vi p, vi t) {
  int n = sz(p);
  assert(n == sz(t));

  ll a = _a;

  v3 coup;
  vector<pair<ll, int>> ones;
  for (int i = 0; i < n; i++) {
    if (t[i] > 1)
      coup.push_back({p[i], t[i], i});
    else
      ones.push_back({p[i], i});
  }

  sort(ones.begin(), ones.end());
  vl pref = {0};
  for (auto [v, i] : ones)
    pref.push_back(pref.back() + v);

  if (sz(coup) == 0) {
    int lo = 0;
    int hi = sz(pref);
    while (lo + 1 < hi) {
      int mi = lo + (hi - lo) / 2;
      if (pref[mi] <= a)
        lo = mi;
      else
        hi = mi;
    }

    vi ret;
    for (int i = 0; i < lo; i++)
      ret.push_back(ones[i].second);
    
    return ret;
  }

  sort(coup.begin(), coup.end(), [](auto lhs, auto rhs) {
    auto [x, y, lind] = lhs;
    auto [z, w, rind] = rhs;

    return x * y * (w - 1) < z * w * (y - 1);
  });

  for (auto [x, y, i] : coup) {
    dbg(x); dbg(y); dbg(i);
  }

  vvl dp(sz(coup) + 1, vl(__bit_width(n) + 2, -1));
  dp[0][0] = a;
  for (int i = 1; i < sz(dp); i++) {
    dp[i][0] = a;
    for (int j = 1; j < sz(dp[0]); j++) {
      dp[i][j] = max(dp[i - 1][j], max(min((dp[i - 1][j - 1] - coup[i - 1][0]) * coup[i - 1][1], (ll)1e15), (ll)-1));
    }
  }

  vector<pair<int, int>> states;
  for (int i = 0; i < sz(dp.back()); i++) {
    ll mon = dp.back().at(i);
    int len = i;

    if (mon < 0)
      continue;

    dbg(len);
    dbg(mon);

    int lo = 0;
    int hi = sz(pref);
    while (lo + 1 < hi) {
      int mi = lo + (hi - lo) / 2;
      if (pref[mi] <= mon)
        lo = mi;
      else
        hi = mi;
    }

    dbg(lo);
    
    len += lo;
    states.push_back({len, i});
  }

  int i = sz(dp) - 1;
  auto [len, j] = *max_element(states.begin(), states.end());
  len -= j;

  dbg(i);
  dbg(j);

  vi ret;
  for (; i > 0 && j > 0; i--) {
    dbg(dp[i][j]);
    dbg(dp[i - 1][j]);
    dbg(dp[i - 1][j - 1]);
    int nj = j - (max(min((dp[i - 1][j - 1] - coup[i - 1][0]) * coup[i - 1][1], (ll)1e15), (ll)-1) == dp[i][j]);
    dbg(i);
    dbg(j);
    if (nj != j)
      ret.push_back(coup[i - 1][2]);
    j = nj;
  }

  reverse(ret.begin(), ret.end());

  for (int i = 0; i < len; i++)
    ret.push_back(ones[i].second);

  return ret;
}

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