Submission #705183

---

Source Code Expand

/*
                   _ooOoo_
                  o8888888o
                  88" . "88
                  (| -_- |)
                  O\  =  /O
               ____/`---'\____
             .'  \\|     |//  `.
            /  \\|||  :  |||//  \
           /  _||||| -:- |||||-  \
           |   | \\\  -  /// |   |
           | \_|  ''\---/''  |   |
           \  .-\__  `-`  ___/-. /
         ___`. .'  /--.--\  `. . __
      ."" '<  `.___\_<|>_/___.'  >'"".
     | | :  `- \`.;`\ _ /`;.`/ - ` : | |
     \  \ `-.   \_ __\ /__ _/   .-` /  /
======`-.____`-.___\_____/___.-`____.-'======
                   `=---='
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
            pass System Test!
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template <typename T>
std::ostream &operator<<(std::ostream &out, const std::vector<T> &v) {
  if (!v.empty()) {
    out << '[';
    std::copy(v.begin(), v.end(), std::ostream_iterator<T>(out, ", "));
    out << "\b\b]";
  }
  return out;
}
template <typename T1, typename T2>
std::ostream &operator<<(std::ostream &out, const std::pair<T1, T2> &p) {
  out << "[" << p.first << ", " << p.second << "]";
  return out;
}
template <class T, class U>
void chmin(T &t, U f) {
  if (t > f) t = f;
}

template <class T, class U>
void chmax(T &t, U f) {
  if (t < f) t = f;
}

vector<int> a, b;
const int64_t INF = 1e18;

vector<vector<map<tuple<int64_t, int64_t>, int64_t>>> dp1;
vector<vector<map<tuple<int64_t, int64_t>, int64_t>>> dp1p;
vector<vector<map<tuple<int64_t, int64_t>, int64_t>>> dp2;
vector<vector<map<tuple<int64_t, int64_t>, int64_t>>> dp2p;

int64_t dfs(bool player1, bool one_passed, int pos1, int pos2, int64_t st1,
            int64_t st2) {
  auto t = make_tuple(st1, st2);

  if (player1) {
    map<tuple<int64_t, int64_t>, int64_t> &dp =
        one_passed ? dp1p[pos1][pos2] : dp1[pos1][pos2];
    if (dp.count(t)) return dp[t];

    int64_t ret = -INF;

    // Not Pass
    if (pos1 < a.size()) {
      int card = a[pos1];
      if (card == -1) {
        // Attack Card
        chmax(ret, dfs(false, false, pos1 + 1, pos2, st1, 0));
      } else {
        // Point Card
        chmax(ret, dfs(false, false, pos1 + 1, pos2, st1 + card, st2));
      }
    }

    // Pass
    if (one_passed) {
      chmax(ret, 0);
    } else {
      if (st1 == 0 && st2 == 0)
        chmax(ret, dfs(false, true, pos1, pos2, 0, 0) + st1 - st2);
      else
        chmax(ret, dfs(false, false, pos1, pos2, 0, 0) + st1 - st2);
    }

    // cout << player1 << "," << one_passed << "," << pos1 << "," << pos2 << ","
    //      << st1 << "," << st2 << "," << p1 << "," << p2 << endl;
    // cout << ret << endl;

    dp[t] = ret;
    return ret;
  } else {
    map<tuple<int64_t, int64_t>, int64_t> &dp =
        one_passed ? dp2p[pos1][pos2] : dp2[pos1][pos2];
    if (dp.count(t)) return dp[t];
    int64_t ret = INF;

    // Not Pass
    if (pos2 < b.size()) {
      int card = b[pos2];
      if (card == -1) {
        // Attack Card
        chmin(ret, dfs(true, false, pos1, pos2 + 1, 0, st2));
      } else {
        // Point Card
        chmin(ret, dfs(true, false, pos1, pos2 + 1, st1, st2 + card));
      }
    }

    // Pass
    if (one_passed) {
      chmin(ret, 0);
    } else {
      if (st1 == 0 && st2 == 0)
        chmin(ret, dfs(true, true, pos1, pos2, 0, 0) + st1 - st2);
      else
        chmin(ret, dfs(true, false, pos1, pos2, 0, 0) + st1 - st2);
    }

    // cout << player1 << "," << one_passed << "," << pos1 << "," << pos2 << ","
    //      << st1 << "," << st2 << "," << p1 << "," << p2 << endl;
    // cout << ret << endl;

    dp[t] = ret;
    return ret;
  }
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  int N, M;
  cin >> N >> M;
  a.resize(N), b.resize(M);
  for (int i = 0; i < N; ++i) cin >> a[i];
  for (int i = 0; i < M; ++i) cin >> b[i];

  dp1.resize(N + 1);
  dp1p.resize(N + 1);
  dp2.resize(N + 1);
  dp2p.resize(N + 1);
  for (int i = 0; i < N + 1; ++i) {
    dp1[i].resize(M + 1);
    dp1p[i].resize(M + 1);
    dp2[i].resize(M + 1);
    dp2p[i].resize(M + 1);
  }

  cout << dfs(true, false, 0, 0, 0, 0) << endl;
}

Submission Info

Judge Result