제출 #1281513

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1281513		M_W_13	Festival (IOI25_festival)	C++20	100 / 100	395 ms	639500 KiB

festival

#include "festival.h"
#include <bits/stdc++.h>

using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
typedef long long ll;
#define pb push_back
#define st first
#define nd second
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(a) a.begin(), a.end()
const ll INF = 1e17;
const int MAXN = 2e5 + 7;
const int K = 200;
ll dp[MAXN][K];
pii last[MAXN][K];

pll f(pll x) {
  if (x.nd == 2ll) {
    return {x.st, 1};
  }
  if (x.nd == 3ll) {
    return {x.st * 3ll, 4ll};
  }
  return {x.st * 2ll, 3ll};
}

bool por(pair<pll, int> a, pair<pll, int> b) {
  pll x = f(a.st);
  pll y = f(b.st);
  return ((x.st * y.nd) < (y.st * x.nd));
}

ll lic(ll x, pll p) {
  return ((x - p.st) * p.nd);
}

std::vector<int> max_coupons(int A, std::vector<int> P1, std::vector<int> T1) {
  int n = P1.size();
  vector<pair<pll, int>> tab;
  vector<pair<ll, int>> pom;
  // cout << n << " " << A << '\n';
  rep(i, n) {
    // cout << P1[i] << " " << T1[i] << '\n';
    if (T1[i] == 1) {
      pom.pb({P1[i], i});
    }
    else {
      tab.pb({{P1[i], T1[i]}, i});
    }
  }
  sort(all(tab), por);
  sort(all(pom));
  pair<pll, int> T[n];
  int it = 0;
  for (auto p: tab) {
    T[it] = p;
    it++;
  }
  for (auto p: pom) {
    T[it] = {{p.st, 1ll}, p.nd};
    it++;
  }
  ll val = A;
  vector<int> ans;
  bool dodan[n];
  rep(i, n) {
    dodan[i] = false;
  }
  it = 0;
  rep(i, n) {
    if (val >= INF) {
      for (auto x: ans) {
        dodan[x] = true;
      }
      rep(j, n) {
        if (dodan[j]) continue;
        ans.pb(j);
      }
      return ans;
    }
    if (lic(val, T[i].st) >= val) {
      val = lic(val, T[i].st);
      ans.pb(T[i].nd);
    }
    else break;
    it = i + 1;
  }
  rep(i, n + 1) {
    rep(j, K) {
      dp[i][j] = -1;
    }
  }
  dp[it][0] = val;
  // cout << "val = " << val << '\n';
  int n2 = tab.size();
  // cout << "it = " << it << " n2 = " << n2 << '\n';
  for (int i = it; i < n2; i++) {
    dp[i + 1][0] = dp[i][0];
    rep(j, K - 1) {
      dp[i + 1][j + 1] = dp[i][j + 1];
      last[i + 1][j + 1] = last[i][j + 1];
      ll nowa = (dp[i][j] - T[i].st.st) * T[i].st.nd;
      if (nowa > dp[i + 1][j + 1]) {
        dp[i + 1][j + 1] = nowa;
        last[i + 1][j + 1] = {i, T[i].nd};
      }
    }
  }
  int sz = pom.size();
  ll pref[sz + 1];
  pref[0] = 0ll;
  rep(i, sz) {
    pref[i + 1] = pref[i] + pom[i].st;
  }
  int maks = 0;
  int kt = sz;
  int il2 = 0;
  int kt2 = 0;
  rep(il, K) {
    if (dp[n2][il] < 0) break;
    while (kt > 0 && (pref[kt] > dp[n2][il])) {
      kt--;
    }
    if ((kt + il) > maks) {
      maks = kt + il;
      il2 = il;
      kt2 = kt;
    }
  }
  int it1 = n2;
  // cout << "kt2 = " << kt2 << " il2 = " << il2 << '\n';
  vector<int> vect;
  while (il2 > 0) {
    vect.pb(last[it1][il2].nd);
    it1 = last[it1][il2].st;
    il2--;
  }
  reverse(all(vect));
  for (auto x: vect) {
    ans.pb(x);
  }
  rep(i, kt2) {
    ans.pb(pom[i].nd);
  }
  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