Submission #1262228

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262228		avighna	Festival (IOI25_festival)	C++20	100 / 100	124 ms	111432 KiB

festival

#include <bits/stdc++.h>

struct item {
  int64_t i, p, t;
};

std::vector<int> max_coupons(int _a, std::vector<int> P, std::vector<int> T) {
  int n = P.size();
  std::vector<item> a(n);
  for (int i = 0; i < n; ++i) {
    a[i] = {i, P[i], T[i]};
  }
  std::sort(a.begin(), a.end(), [&](item i, item j) {
    if (i.t == j.t and i.t == 1) {
      return i.p < j.p;
    }
    return (j.p + i.p * i.t) * j.t < (i.p + j.p * j.t) * i.t;
  });
  int64_t A = _a;
  const int64_t inf = 1e15;
  int cnt_remove = 0;
  std::vector<int> ans;
  for (int i = 0; i < n; ++i) {
    if ((A - a[i].p) * a[i].t < A) {
      break;
    }
    ans.push_back(a[i].i);
    A = std::min((A - a[i].p) * a[i].t, inf);
    cnt_remove++;
  }
  for (int i = cnt_remove; i < n; ++i) {
    a[i - cnt_remove] = a[i];
  }
  for (int i = 0; i < cnt_remove; ++i) {
    a.pop_back();
  }
  n -= cnt_remove;
  int _n = n;
  for (int i = 0; i < n; ++i) {
    if (a[i].t == 1) {
      _n = i;
      break;
    }
  }
  if (_n == 0) {
    int64_t cur = A;
    for (auto &i : a) {
      if (cur - i.p < 0) {
        break;
      }
      cur = (cur - i.p) * i.t;
      ans.push_back(i.i);
    }
    return ans;
  }
  std::vector<int64_t> psum(n);
  if (n != _n) {
    psum[_n] = a[_n].p;
  }
  for (int i = _n + 1; i < n; ++i) {
    psum[i] = psum[i - 1] + a[i].p;
  }

  const int lg = 60;
  std::vector dp(_n, std::vector<int64_t>(std::min(_n + 1, lg), -inf));
  for (int i = 0; i < _n; ++i) {
    for (int j = 0; j <= std::min(_n, lg - 1); ++j) {
      if (j == 0) {
        dp[i][j] = A;
        continue;
      }
      if (j > i + 1) {
        dp[i][j] = -inf;
        continue;
      }
      if (i == 0) {
        dp[i][j] = A - a[i].p >= 0 ? (A - a[i].p) * a[i].t : -inf;
        continue;
      }
      dp[i][j] = dp[i - 1][j];
      if (dp[i - 1][j - 1] - a[i].p >= 0) {
        dp[i][j] = std::max(dp[i][j], (dp[i - 1][j - 1] - a[i].p) * a[i].t);
      }
    }
    for (int j = 0; j <= std::min(_n, lg - 1); ++j) {
      dp[i][j] = std::min(dp[i][j], inf);
    }
  }

  int max_ans = 0, corr_j = 0;
  for (int j = 0; j <= std::min(_n, lg - 1); ++j) {
    if (dp[_n - 1][j] < 0) {
      continue;
    }
    int got = j + std::upper_bound(psum.begin(), psum.end(), dp[_n - 1][j]) - psum.begin() - _n;
    if (got > max_ans) {
      max_ans = got;
      corr_j = j;
    }
  }

  std::vector<int> t_ans;
  int i = _n - 1, j = corr_j;
  while (i >= 0 and j > 0) {
    if (i == 0) {
      if (j != 0) {
        t_ans.push_back(i);
        j--;
      }
      i--;
      continue;
    }
    if (i != 0 and dp[i - 1][j - 1] - a[i].p >= 0 and (dp[i - 1][j - 1] - a[i].p) * a[i].t > dp[i - 1][j]) {
      j--;
      t_ans.push_back(i);
    }
    i--;
  }
  std::reverse(t_ans.begin(), t_ans.end());
  for (int size = max_ans - t_ans.size(), i = 0; i < size; ++i) {
    t_ans.push_back(_n + i);
  }
  for (int &i : t_ans) {
    ans.push_back(a[i].i);
  }
  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