Invisible http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2741

aoj2741.cpp

#include <bits/stdc++.h>
using namespace std;
#define int long long   // <-----!!!!!!!!!!!!!!!!!!!

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
#define rrep2(i,a,b) for (int i=(a)-1;i>=b;i--)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define printV(_v) for(auto _x:_v){cout<<_x<<" ";}cout<<endl
#define printVS(vs) for(auto x : vs){cout << x << endl;}
#define printVV(_vv) for(auto _v:_vv){for(auto _x:_v){cout<<_x<<" ";}cout<<endl;}
#define printP(p) cout << p.first << " " << p.second << endl
#define printVP(vp) for(auto p : vp) printP(p);
#define readV(_v) rep(j, _v.size()) cin >> _v[j];
#define readVV(_vv) rep(i, _vv.size()) readV(_vv[i]);
#define output(_x) cout << _x << endl;

typedef long long ll;
typedef pair<int, int> Pii;
typedef tuple<int, int, int> TUPLE;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<Pii> vp;
const int inf = 1e9;
const int mod = 1e9 + 7;

const int MAX = 52;
int n, m;
int a[MAX];
int b[MAX];
int dp[MAX][MAX][MAX][MAX][2][3];

int dfs(int l0, int r0, int l1, int r1, int turn, int pass, int p0, int p1) {
    int& ret = dp[l0][r0][l1][r1][turn][pass];
    if (ret != inf && ret != -inf) return ret;

    if (!turn) {
        // stackに積む場合
        if (r0 < n) {
            if (a[r0] > 0) {
                // 得点カードを積む場合
                ret = max(ret, dfs(l0, r0 + 1, l1, r1, turn^1, 0, p0 + a[r0], p1));
            } else {
                // 妨害カードを積む場合
                ret = max(ret, dfs(l0, r0 + 1, l1, r1, turn^1, 0, p0, 0));
            }
        }
        // パスする場合
        if (l0 == r0 && l1 == r1) {
            // stackが空のとき
            if (pass == 0) {
                assert(p0 == 0 && p1 == 0);
                ret = max(ret, dfs(r0, r0, r1, r1, turn^1, 1, 0, 0));
            } else if (pass == 1) {
                ret = max(ret, 0ll);
            }
        } else {
            // stackが空でないとき
            assert(pass == 0);
            ret = max(ret, dfs(r0, r0, r1, r1, turn^1, 0, 0, 0) + p0 - p1);
        }
    } else {
        // stackに積む場合
        if (r1 < m) {
            if (b[r1] > 0) {
                // 得点カードを積む場合
                ret = min(ret, dfs(l0, r0, l1, r1 + 1, turn^1, 0, p0, p1 + b[r1]));
            } else {
                // 妨害カードを積む場合
                ret = min(ret, dfs(l0, r0, l1, r1 + 1, turn^1, 0, 0, p1));
            }
        }
        // パスする場合
        if (l0 == r0 && l1 == r1) {
            // stackが空のとき
            if (pass == 0) {
                assert(p0 == 0 && p1 == 0);
                ret = min(ret, dfs(r0, r0, r1, r1, turn^1, 1, 0, 0));
            } else if (pass == 1) {
                ret = min(ret, 0ll);
            }
        } else {
            // stackが空でないとき
            assert(pass == 0);
            ret = min(ret, dfs(r0, r0, r1, r1, turn^1, 0, 0, 0) + p0 - p1);
        }
    }

    return ret;
}

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

    cin >> n >> m;
    rep(i, n) cin >> a[i];
    rep(i, m) cin >> b[i];

    rep(i, MAX) rep(j, MAX) rep(k, MAX) rep(l, MAX) rep(p, 2) rep(q, 3) {
        dp[i][j][k][l][p][q] = (!p ? -inf : inf);
    }
    cout << dfs(0, 0, 0, 0, 0, 0, 0, 0) << endl;

}