Submission #1350819

---

Source Code Expand

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

#define for_(i,a,b) for(int i=(a);i<(b);++i)

int n, m, a[55], b[55], dp[2][2][55][55][55][55];

int rec(int cur_a, int cur_b, int prv_a, int prv_b, int sum_a, int sum_b, int turn, int pass) {
	if (pass == 2) return 0;
	if (cur_a == n && cur_b == m && prv_a == n && prv_b == m) return 0;
	
	int& res = dp[turn][pass][cur_a][cur_b][prv_a][prv_b];
	if (abs(res) != 1e9) return res;
	
	if (turn) {
		if (cur_b < m) {
			int nxt_sum_a = (b[cur_b] == -1 ? 0 : sum_a), nxt_sum_b = sum_b + (b[cur_b] == -1 ? 0 : b[cur_b]);
			res = min(res, rec(cur_a, cur_b + 1, (b[cur_b] == -1 ? cur_a : prv_a), prv_b, nxt_sum_a, nxt_sum_b, 0, 0));
		}
		res = min(res, rec(cur_a, cur_b, cur_a, cur_b, 0, 0, 0, (cur_a == prv_a && cur_b == prv_b ? pass + 1 : 0)) + sum_a - sum_b);
	} else {
		if (cur_a < n) {
			int nxt_sum_a = sum_a + (a[cur_a] == -1 ? 0 : a[cur_a]), nxt_sum_b = (a[cur_a] == -1 ? 0 : sum_b);
			res = max(res, rec(cur_a + 1, cur_b, prv_a, (a[cur_a] == -1 ? cur_b : prv_b), nxt_sum_a, nxt_sum_b, 1, 0));
		}
		res = max(res, rec(cur_a, cur_b, cur_a, cur_b, 0, 0, 1, (cur_a == prv_a && cur_b == prv_b ? pass + 1 : 0)) + sum_a - sum_b);
	}
	
	return res;
}

int main() {
	cin >> n >> m;
	for_(i,0,n) cin >> a[i];
	for_(i,0,m) cin >> b[i];
	
	for_(t,0,2) for_(p,0,2) for_(i,0,55) for_(j,0,55) for_(ii,0,55) for_(jj,0,55) dp[t][p][i][j][ii][jj] = (t ? 1e9 : -(1e9));
	
	cout << rec(0, 0, 0, 0, 0, 0, 0, 0) << endl;
}

Submission Info

Judge Result