Submission #1253640

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253640		bynix	Festival (IOI25_festival)	C++20	27 / 100	1116 ms	1697772 KiB

festival

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

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

#define chk 

vector<int> max_coupons(int A, vector<int> P, vector<int> T) {
  vector<int> R;

  ll N = P.size();
  vector<vector<ll>> t1, t;
  vector<ll> pre1(N+1, lim*2);

  for (ll i = 0; i < N; i++){
    if (T[i] == 1) t1.push_back({P[i], i});
    else t.push_back({P[i], i, T[i]});
  }

  ll t1s = t1.size(), ts = t.size();
  sort(t1.begin(), t1.end());
  sort(t.begin(), t.end(), [](vector<ll>& a, vector<ll>& b){
    ll l = a[2]*((b[0]*b[2]) + a[0]), r = b[2]*((a[0]*a[2]) + b[0]);
    return l > r;
  });

  vector<vector<ll>> dp(ts + 1, vector<ll>(ts + 1, -1)), log(ts + 1, vector<ll>(ts + 1, -1));
  dp[0][0] = A;
  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] - t[i-1][0])*t[i-1][2];
      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);
    }
  }

  pre1[0] = 0;
  for (ll i = 0; i < t1s; i++)
    pre1[i + 1] = pre1[i] + t1[i][0], pre1[i + 1] = min(pre1[i + 1], lim);

  ll mc = 0ll, mt1 = 0ll, mt = 0ll, ct1 = 0ll;
  for (ll i = 0; i <= ts; i++){
    if (dp[ts][i] < 0) break;

    ll pos = upper_bound(pre1.begin(), pre1.end(), dp[ts][i]) - pre1.begin();
    if (pos == 0) ct1 = 0;
    else ct1 = min(pos - 1, t1s);

    if (ct1 + i > mc) mc = ct1 + i, mt1 = ct1, mt = i;
  }

  int cur = mt, c = ts, b = 0;
  while (R.size() < mt){
    if (log[c][cur] >= 0){
      R.push_back(t[c-1][1]);
      b++;
    }
    cur = mt - b, c--;
  }
  reverse(R.begin(), R.end());
  for (ll i = 0; i < mt1; i++) R.push_back(t1[i][1]);

  return R;
}

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