AOJ2557.cpp

#include <bits/stdc++.h>

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(),(x).end()

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const int INF = 1e9;
const ld eps = 1e-9, pi = acos(-1.0);

typedef vector<int> Cards;
typedef vector<int> Score;
typedef pair<int,Score> P;

struct State {
  int player;
  Cards x, c[3];
  State(Cards x, Cards frog, Cards kappa, Cards weasel)
    : player(0), x(x), c{frog, kappa, weasel} {}
  bool end() const { return x.empty(); }
  int stay() {
    int res = x[0];
    REP(i,(int)x.size()-1) x[i] = x[i+1];
    x.pop_back();
    player = (player + 1) % 3;
    return res;
  }
  int play(int n) {
    if (n < 0) return stay();
    if (n >= (int)c[player].size()) return -INF;
    int v = c[player][n] - 1;
    for (int i = n; i < (int)c[player].size() - 1; ++i)
      c[player][i] = c[player][i+1];
    c[player].pop_back();
    if (v >= (int)x.size()) return stay();
    int res = x[v];
    for (int i = v; i < (int)x.size() - 1; ++i) x[i] = x[i+1];
    x.pop_back();
    player = (player + 1) % 3;
    return res;
  }
};

P dfs(const State &st) {
  if (st.end()) return P(0, Score(3));
  const int p = st.player;
  Score ma = {-INF, -INF, -INF};
  int action = -1;
  for (int i = -1;; ++i) {
    State nst = st;
    int val = nst.play(i);
    if (val == -INF) break;
    Score s = dfs(nst).second;
    s[p] += val;
    if (ma[p] < s[p]) { ma = s; action = i; }
  }
  return P(action, ma);
}

P dfs_kappa(const State &st) {
  if (st.end()) return P(0, Score(3));
  const int p = st.player;
  if (p != 1) {
    State nst = st;
    int val = nst.play(dfs(nst).first);
    P res = dfs_kappa(nst);
    res.second[p] += val;
    return res;
  }
  Score mi = {INF, INF, INF};
  int action = -1;
  for (int i = -1;; ++i) {
    State nst = st;
    int val = nst.play(i);
    if (val == -INF) break;
    Score s = dfs_kappa(nst).second;
    s[p] += val;
    if (mi[0] > s[0]) { mi = s; action = i; }
  }
  return P(action, mi);
}

int main() {
  vector<int> x(12), a(2), b(2), c(2);
  REP(i,12) cin >> x[i];
  REP(i,2) cin >> a[i]; sort(ALL(a));
  REP(i,2) cin >> b[i]; sort(ALL(b));
  REP(i,2) cin >> c[i]; sort(ALL(c));
  reverse(ALL(x));
  State st(x, a, b, c);
  Score sc = {0, 0, 0};
  while (!st.end()) {
    const int p = st.player;
    int val = st.play(p == 1 ? dfs_kappa(st).first : dfs(st).first);
    sc[p] += val;
  }
  cout << sc[0] << " " << sc[1] << " " << sc[2] << endl;
  return 0;
}