結果

問題 No.3130 Twin's Add Max Min Game
ユーザー yamate11
提出日時 2025-04-25 23:49:32
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,537 bytes
コンパイル時間 4,107 ms
コンパイル使用メモリ 285,552 KB
実行使用メモリ 11,236 KB
最終ジャッジ日時 2025-04-25 23:49:52
合計ジャッジ時間 9,175 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 28 WA * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <cassert>
using namespace std;
using ll = long long int;
using u64 = unsigned long long;
using pll = pair<ll, ll>;
// #include <atcoder/all>
// using namespace atcoder;
#define REP(i, a, b) for (ll i = (a); i < (b); i++)
#define REPrev(i, a, b) for (ll i = (a); i >= (b); i--)
#define ALL(coll) (coll).begin(), (coll).end()
#define SIZE(v) ((ll)((v).size()))
#define REPOUT(i, a, b, exp, sep) REP(i, (a), (b)) cout << (exp) << (i + 1 == (b) ? "" : (sep)); cout << "\n"

// @@ !! LIM(binsearch)

// ---- inserted library file binsearch.cc

template <typename T>
requires integral<T>
T binsearch(auto check, T yes, T no) {
  while (abs(no - yes) > 1) {
    T mid = yes + (no - yes) / 2;  // avoiding unnecessary overflow
    if (check(mid)) yes = mid;
    else            no  = mid;
  }
  return yes;
}

template <typename T>
requires floating_point<T>
T binsearch(auto check, T yes, T no, T err, const bool abs_only = false) {
  T rep_in_t = ceil(log(abs(yes - no) / err) / log(2.0));
  constexpr int lim = INT_MAX - 10;
  int rep = rep_in_t > (T)lim ? lim : llround(rep_in_t) + 1;
  for (int r = 0; r < rep; r++) {
    T mid = (yes + no) / 2.0;
    if (not abs_only) {
      if (abs(yes - mid) < err * min(abs(mid), abs(yes))) return mid;
    }
    if (check(mid)) yes = mid;
    else            no  = mid;
  }
  return yes;
}

// ---- end binsearch.cc

// @@ !! LIM -- end mark --

int main(/* int argc, char *argv[] */) {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout << setprecision(20);

  ll N; cin >> N;
  // @InpVec(N, A) [7Zq19OHl]
  auto A = vector(N, ll());
  for (int i = 0; i < N; i++) { ll v; cin >> v; A[i] = v; }
  // @End [7Zq19OHl]
  // @InpVec(N, S, type=string) [4nUiuvuQ]
  auto S = vector(N, string());
  for (int i = 0; i < N; i++) { string v; cin >> v; S[i] = v; }
  // @End [4nUiuvuQ]

  ll x0 = 0;
  
  auto check = [&](ll a) -> bool {
    auto f_akane = [&](auto r_akane, auto r_aoi, ll x, const auto& v_akane, const auto& v_aoi) -> bool {
      bool found = false;
      REP(i, 0, N) {
        if (v_akane[i]) {
          found = true;
          auto w_akane = v_akane;
          w_akane[i] = false;
          if (not r_aoi(r_akane, r_aoi, x, A[i], w_akane, v_aoi)) return true;
        }
      }
      if (found) return false;
      return x >= a;
    };

    auto f_aoi = [&](auto r_akane, auto r_aoi, ll x, ll vala, const auto& v_akane, const auto& v_aoi) -> bool {
      REP(i, 0, N) {
        if (v_aoi[i]) {
          auto w_aoi = v_aoi;
          w_aoi[i] = false;
          ll new_x;
          if (S[i] == "add") new_x = x + vala;
          else if (S[i] == "min") new_x = min(x, vala);
          else if (S[i] == "max") new_x = max(x, vala);
          else assert(0);
          if (not r_akane(r_akane, r_aoi, new_x, v_akane, w_aoi)) return true;
        }
      }
      return false;
    };

    vector<bool> v_akane(N, true);
    vector<bool> v_aoi(N, true);
    return f_akane(f_akane, f_aoi, x0, v_akane, v_aoi);
  };

  if (false) {
    ll a = binsearch<ll>(check, 1, (ll)1e18);
    cout << a << endl;
  }
  ll n_add = 0, n_min = 0, n_max = 0;
  REP(i, 0, N) {
    if (S[i] == "add") n_add++;
    else if (S[i] == "min") n_min++;
    else if (S[i] == "max") n_max++;
    else assert(0);
  }
  sort(ALL(A));
  ll ans = 0;
  if (n_add == 0) {
    if (n_max == 0) {
      ans = 0;
    }else {
      ans = A[N - 1 - n_min];
    }
  }else {
    ans = A[N - 1 - n_min];
    REP(i, 0, n_add - 1) ans += A[i];
  }
  cout << ans << endl;

  return 0;
}
0