結果

問題 No.3130 Twin's Add Max Min Game
ユーザー PNJ
提出日時 2025-04-25 22:36:14
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 157 ms / 2,000 ms
コード長 13,086 bytes
コンパイル時間 3,662 ms
コンパイル使用メモリ 288,616 KB
実行使用メモリ 11,204 KB
最終ジャッジ日時 2025-04-25 22:36:31
合計ジャッジ時間 11,940 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 56
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

template <class T>
using vc = vector<T>;
template <class T>
using vvc = vector<vc<T>>;
template <class T>
using vvvc = vector<vvc<T>>;
template <class T>
using vvvvc = vector<vvvc<T>>;
template <class T>
using vvvvvc = vector<vvvvc<T>>;

#define vv(type, name, h, w) vector<vector<type>> name(h, vector<type>(w))
#define vvv(type, name, h, w, l) vector<vector<vector<type>>> name(h, vector<vector<type>>(w, vector<type>(l)))
#define vvvv(type, name, a, b, c, d) vector<vector<vector<vector<type>>>> name(a, vector<vector<vector<type>>>(b, vector<vector<type>>(c, vector<type>(d))))
#define vvvvv(type, name, a, b, c, d, e) vector<vector<vector<vector<vector<type>>>>> name(a, vector<vector<vector<vector<type>>>>(b, vector<vector<vector<type>>>(c, vector<vector<type>>(d, vector<type>(e)))))

#define elif else if

#define FOR1(a) for (long long _ = 0; _ < (long long)(a); _++)
#define FOR2(i, n) for (long long i = 0; i < (long long)(n); i++)
#define FOR3(i, l, r) for (long long i = l; i < (long long)(r); i++)
#define FOR4(i, l, r, c) for (long long i = l; i < (long long)(r); i += c)
#define FOR1_R(a) for (long long _ = (long long)(a) - 1; _ >= 0; _--)
#define FOR2_R(i, n) for (long long i = (long long)(n) - 1; i >= (long long)(0); i--)
#define FOR3_R(i, l, r) for (long long i = (long long)(r) - 1; i >= (long long)(l); i--)
#define FOR4_R(i, l, r, c) for (long long i = (long long)(r) - 1; i >= (long long)(l); i -= (c))
#define overload4(a, b, c, d, e, ...) e
#define FOR(...) overload4(__VA_ARGS__, FOR4, FOR3, FOR2, FOR1)(__VA_ARGS__)
#define FOR_R(...) overload4(__VA_ARGS__, FOR4_R, FOR3_R, FOR2_R, FOR1_R)(__VA_ARGS__)
#define FOR_in(a, A) for (auto a: A)
#define FOR_each(a, A) for (auto &&a: A)
#define FOR_subset(t, s) for(long long t = (s); t >= 0; t = (t == 0 ? -1 : (t - 1) & (s)))

#define all(x) x.begin(), x.end()
#define len(x) int(x.size())

int popcount(int x) { return __builtin_popcount(x); }
int popcount(uint32_t x) { return __builtin_popcount(x); }
int popcount(long long x) { return __builtin_popcountll(x); }
int popcount(uint64_t x) { return __builtin_popcountll(x); }
// __builtin_clz(x)は最上位bitからいくつ0があるか.
int topbit(int x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); }
int topbit(uint32_t x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); }
int topbit(long long x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); }
int topbit(uint64_t x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); }

// 入力
void rd() {}
void rd(char &c) { cin >> c; }
void rd(string &s) { cin >> s; }
void rd(int &x) { cin >> x; }
void rd(uint32_t &x) { cin >> x; }
void rd(long long &x) { cin >> x; }
void rd(uint64_t &x) { cin >> x; }
template<class T>
void rd(vector<T> &v) {
  for (auto& x:v) rd(x);
}

void read() {}
template <class H, class... T>
void read(H &h, T &... t) {
  rd(h), read(t...);
}

#define CHAR(...) \
  char __VA_ARGS__; \
  read(__VA_ARGS__)

#define STRING(...) \
  string __VA_ARGS__; \
  read(__VA_ARGS__)

#define INT(...) \
  int __VA_ARGS__; \
  read(__VA_ARGS__)

#define U32(...) \
  uint32_t __VA_ARGS__; \
  read(__VA_ARGS__)

#define LL(...) \
  long long __VA_ARGS__; \
  read(__VA_ARGS__)

#define U64(...) \
  uint64_t __VA_ARGS__; \
  read(__VA_ARGS__)

#define VC(t, a, n) \
  vector<t> a(n); \
  read(a)

#define VVC(t, a, h, w) \
  vector<vector<t>> a(h, vector<t>(w)); \
  read(a)

//出力
void wt() {}
void wt(const char c) { cout << c; }
void wt(const string s) { cout << s; }
void wt(int x) { cout << x; }
void wt(uint32_t x) { cout << x; }
void wt(long long x) { cout << x; }
void wt(uint64_t x) { cout << x; }
void wt(double x) { cout << fixed << setprecision(16) << x; }
void wt(long double x) { cout << fixed << setprecision(16) << x; }

template<class T>
void wt(const vector<T> v) {
  int n = v.size();
  for (int i = 0; i < n; i++) {
    if (i) wt(' ');
    wt(v[i]);
  }
}

void print() { wt('\n'); }
template <class Head, class... Tail>
void print(Head &&head, Tail &&... tail) {
  wt(head);
  if (sizeof...(Tail)) wt(' ');
  print(forward<Tail>(tail)...);
}

/////////////////////////////////////////////////////////////////////////////////////////
long long min(long long a, long long b) { return a < b ? a : b; }

template <class T>
T min(vector<T> A) {
  assert (A.size());
  T S = A[0];
  for (T a : A) S = min(a, S);
  return S;
}

long long max(long long a, long long b) { return a > b ? a : b; }

template <class T>
T max(vector<T> A) {
  assert (A.size());
  T S = A[0];
  for (T a : A) S = max(a, S);
  return S;
}

long long add(long long x, long long y) {return x + y; }

template <class mint>
mint add(mint x, mint y) { return x + y; }

template <class T>
bool chmin(T & x, T a) { return a < x ? (x = a, true) : false; }

template <class T>
bool chmax(T & x, T a) { return a > x ? (x = a, true) : false; }

template <class T>
T sum(vector<T> A) {
  T S = 0;
  for (int i = 0; i < int(A.size()); i++) S += A[i];
  return S;
}

uint64_t random_u64(uint64_t l, uint64_t r) {
  static std::random_device rd;
  static std::mt19937_64 gen(rd());
  std::uniform_int_distribution<uint64_t> dist(l, r);
  return dist(gen);
}

long long gcd(long long a, long long b) {
  while (a) {
    b %= a;
    if (b == 0) return a;
    a %= b;
  }
  return b;
}

long long lcm(long long a, long long b) {
  if (a * b == 0) return 0;
  return a * b / gcd(a, b);
}

long long pow_mod(long long a, long long r, long long mod) {
  long long res = 1, p = a % mod;
  while (r) {
    if ((r % 2) == 1) res = res * p % mod;
    p = p * p % mod, r >>= 1;
  }
  return res;
}

long long mod_inv(long long a, long long mod) {
  if (mod == 1) return 0;
  a %= mod;
  long long b = mod, s = 1, t = 0;
  while (1) {
    if (a == 1) return s;
    t -= (b / a) * s;
    b %= a;
    if (b == 1) return t + mod;
    s -= (a / b) * t;
    a %= b;
  }
}

long long Garner(vector<long long> Rem, vector<long long> Mod, int MOD) {
  assert (Rem.size() == Mod.size());
  long long mod = MOD;
  Rem.push_back(0);
  Mod.push_back(mod);
  long long n = Mod.size();
  vector<long long> coffs(n, 1);
  vector<long long> constants(n, 0);
  for (int i = 0; i < n - 1; i++) {
    long long v = (Mod[i] + Rem[i] - constants[i]) % Mod[i];
    v *= mod_inv(coffs[i], Mod[i]);
    v %= Mod[i];
    for (int j = i + 1; j < n; j++) {
      constants[j] = (constants[j] + coffs[j] * v) % Mod[j];
      coffs[j] = (coffs[j] * Mod[i]) % Mod[j];
    }
  }
  return constants[n - 1];
}

long long Tonelli_Shanks(long long a, long long mod) {
  a %= mod;
  if (a < 2) return a;
  if (pow_mod(a, (mod - 1) / 2, mod) != 1) return -1;
  if (mod % 4 == 3) return pow_mod(a, (mod + 1) / 4, mod);

  long long b = 3;
  if (mod != 998244353) {
    while (pow_mod(b, (mod - 1) / 2, mod) == 1) {
      b = random_u64(2, mod - 1);
    }
  }

  long long q = mod - 1;
  long long Q = 0;
  while (q % 2 == 0) {
    Q++, q /= 2;
  }

  long long x = pow_mod(a, (q + 1) / 2, mod);
  b = pow_mod(b, q, mod);

  long long shift = 2;
  while ((x * x) % mod != a) {
    long long error = (((pow_mod(a, mod - 2, mod) * x) % mod) * x) % mod;
    if (pow_mod(error, 1 << (Q - shift), mod) != 1) {
      x = (x * b) % mod;
    }
    b = (b * b) % mod;
    shift++;
  }
  return x;
}

/////////////////////////////////////////////////////////////////////////////////////////
template <typename T>
class AVL {
  struct Node {
    T key;
    int height, size, count;
    Node* left;
    Node* right;
    Node(const T &k) : key(k), height(1), size(1), count(1), left(nullptr), right(nullptr) {}
  };
  Node* root = nullptr;
  int le = 0;

  int height(Node* n) { return n ? n->height : 0; }
  int size(Node* n) { return n ? n->size : 0; }

  void update(Node* n) {
    if (n) {
      n->height = 1 + max(height(n->left), height(n->right));
      n->size = n->count + size(n->left) + size(n->right);
    }
  }

  int balance_factor(Node* n) { return height(n->left) - height(n->right); }

  Node* rotate_right(Node* y) {
    Node* x = y->left;
    y->left = x->right;
    x->right = y;
    update(y); update(x);
    return x;
  }

  Node* rotate_left(Node* x) {
    Node* y = x->right;
    x->right = y->left;
    y->left = x;
    update(x); update(y);
    return y;
  }

  Node* balance(Node* n) {
    update(n);
    int bf = balance_factor(n);
    if (bf > 1) {
      if (balance_factor(n->left) < 0) n->left = rotate_left(n->left);
      return rotate_right(n);
    }
    if (bf < -1) {
      if (balance_factor(n->right) > 0) n->right = rotate_right(n->right);
      return rotate_left(n);
    }
    return n;
  }

  Node* insert(Node* n, const T &key) {
    if (!n) return new Node(key);
    if (key < n->key) n->left = insert(n->left, key);
    else if (key > n->key) n->right = insert(n->right, key);
    else n->count++;
    return balance(n);
  }

  Node* erase(Node* n, const T &key) {
    if (!n) return nullptr;
    if (key < n->key) n->left = erase(n->left, key);
    else if (key > n->key) n->right = erase(n->right, key);
    else {
      if (n->count > 1) n->count--;
      else {
        if (!n->left || !n->right) {
          Node* temp = n->left ? n->left : n->right;
          delete n;
          return temp;
        }
        else {
          Node* succ = n->right;
          while (succ->left) succ = succ->left;
          n->key = succ->key;
          n->count = succ->count;
          succ->count = 1;
          n->right = erase(n->right, succ->key);
        }
      }
    }
    return balance(n);
  }

  bool contains(Node* n, const T &key) {
    if (!n) return false;
    if (key < n->key) return contains(n->left, key);
    if (key > n->key) return contains(n->right, key);
    return true;
  }

  int count(Node* n, const T &key) {
    if (!n) return 0;
    if (key < n->key) return count(n->left, key);
    if (key > n->key) return count(n->right, key);
    return n->count;
  }

  int count_less(Node* n, const T &key) {
    if (!n) return 0;
    if (key <= n->key) return count_less(n->left, key);
    return size(n->left) + n->count + count_less(n->right, key);
  }

  int count_leq(Node* n, const T &key) {
    if (!n) return 0;
    if (key < n->key) return count_leq(n->left, key);
    return size(n->left) + n->count + count_leq(n->right, key);
  }

  int count_geq(Node* n, const T &key) {
    if (!n) return 0;
    if (key > n->key) return count_geq(n->right, key);
    return size(n->right) + n->count + count_geq(n->left, key);
  }

  int count_greater(Node* n, const T &key) {
    if (!n) return 0;
    if (key >= n->key) return count_greater(n->right, key);
    return size(n->right) + n->count + count_greater(n->left, key);
  }

  optional<T> get_kth(Node* n, int k) {
    if (!n || k < 0 || k >= size(n)) return nullopt;
    int left_size = size(n->left);
    if (k < left_size) return get_kth(n->left, k);
    if (k < left_size + n->count) return n->key;
    return get_kth(n->right, k - left_size - n->count);
  }

  Node* find_max_leq(Node* n, const T &key) {
    if (!n) return nullptr;
    if (n->key > key) return find_max_leq(n->left, key);
    Node* right = find_max_leq(n->right, key);
    return right ? right : n;
  }

  Node* find_min_geq(Node* n, const T &key) {
    if (!n) return nullptr;
    if (n->key < key) return find_min_geq(n->right, key);
    Node* left = find_min_geq(n->left, key);
    return left ? left : n;
  }

  void to_vector(Node* n, vector<T> &res) {
    if (!n) return;
    to_vector(n->left, res);
    for (int i = 0; i < n->count; i++) res.push_back(n->key);
    to_vector(n->right, res);
  }

public:
  int size() const { return le; }
  void insert(const T &key) { le++, root = insert(root, key); }
  void erase(const T &key) {
    assert (contains(root, key));
    le--, root = erase(root, key);
  }

  bool contains(const T &key) { return contains(root, key); }
  int count(const T &key) { return count(root, key); }

  int count_less(const T &key) { return count_less(root, key); }
  int count_leq(const T &key) { return count_leq(root, key); }
  int count_greater(const T &key) { return count_greater(root, key); }
  int count_geq(const T &key) { return count_geq(root, key); }

  T get(int k) {
    auto res = get_kth(root, k);
    assert (res != nullopt);
    return *res;
  }

  T max_leq(const T &key) {
    Node* res = find_max_leq(root, key);
    assert (res != nullptr);
    return res->key;
  }

  T min_geq(const T &key) {
    Node* res = find_min_geq(root, key);
    assert (res != nullptr);
    return res->key;
  }

  vector<T> to_vector() {
    vector<T> res;
    to_vector(root, res);
    return res;
  }
};

void solve() {
  
}

int main() {
  INT(N);
  VC(long long, A, N);
  sort(all(A));
  VC(string, C, N);
  int add = 0, max = 0, min = 0;
  FOR_in(c, C) {
    if (c == "add") add++;
    else if (c == "max") max++;
    else min++;
  }
  while (min > 1) {
    A.pop_back();
    min--;
  }
  long long m = 0;
  if (add + max > 0) {
    m += A[add + max - 1];
    if (add) add--;
    else max--;
    FOR(i, add) m += A[i];
  }
  if (min > 0 && m > A[int(A.size()) - 1]) m = A[int(A.size()) - 1];
  print(m);
}
0