Submission #1256604

---

Source Code Expand

#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <queue>
#include <utility>
#include <vector>
#include <set>
#include <memory.h>
#include <iomanip>
#include <bitset>
#include <list>
#include <stack>
#include <deque>

using namespace std;

#define mod 1000000007

int n, m;
int a[52], b[52];
long long int asum[52] = {}, bsum[52] = {};
long long int result[52][52][52][52][2][3];

long long int solve(int l0, int l1, int r0, int r1, int player, int passnum)
{
	// cout << l0 << " " << l1 << " " << r0 << " " << r1 << " " << player << " " << passnum << endl;
	// プレイヤー0のスタック内に置かれてるカードはl0 + 1からr0
	// プレイヤー1のスタック内に置かれてるカードはl1 + 1からr1
	if(passnum == 2) return result[l0][l1][r0][r1][player][passnum] = 0;
	if(result[l0][l1][r0][r1][player][passnum] != mod) return result[l0][l1][r0][r1][player][passnum];
	long long int ans;
	// cout << bsum[r1] << " " << bsum[l1] << " " << (asum[r0] - asum[l0]) - (bsum[r1] - bsum[l1]) << endl;
	if(player == 0){
		// パスするとき
		if(l0 == r0 && l1 == r1) ans = solve(r0, r1, r0, r1, 1, passnum + 1);
		else ans = (asum[r0] - asum[l0]) - (bsum[r1] - bsum[l1]) + solve(r0, r1, r0, r1, 1, 0);
		// スタックに置くとき
		if(r0 + 1 <= n){
			if(a[r0 + 1] > 0)ans = max(ans, solve(l0, l1, r0 + 1, r1, 1, 0));
			else ans = max(ans, solve(l0, r1, r0 + 1, r1, 1, 0));
		}
	} else {
		// パスするとき
		if(l0 == r0 && l1 == r1) ans = solve(r0, r1, r0, r1, 0, passnum + 1);
		else ans = (asum[r0] - asum[l0]) - (bsum[r1] - bsum[l1]) + solve(r0, r1, r0, r1, 0, 0);
		// スタックに置くとき
		if(r1 + 1 <= m){
			if(b[r1 + 1] > 0)ans = min(ans, solve(l0, l1, r0, r1 + 1, 0, 0));
			else ans = min(ans, solve(r0, l1, r0, r1 + 1, 0, 0));
		}
	}
	return result[l0][l1][r0][r1][player][passnum] = ans;
}

int main()
{
	cin >> n >> m;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		if(a[i] > 0) asum[i] = a[i] + asum[i - 1];
		else asum[i] = asum[i - 1];
	}
	for(int i = 1; i <= m; i++){
		cin >> b[i];
		if(b[i] > 0) bsum[i] = b[i] + bsum[i - 1];
		else bsum[i] = bsum[i - 1];
	}
	for(int i = 0; i < 52; i++){
		for(int j = 0; j < 52; j++){
			for(int k = 0; k < 52; k++){
				for(int l = 0; l < 52; l++){
					for(int p = 0; p < 2; p++){
						for(int q = 0; q < 3; q++){
							result[i][j][k][l][p][q] = mod;
						}
					}
				}
			}
		}
	}
	cout << solve(0, 0, 0, 0, 0, 0) << endl;
	return 0;
}

Submission Info

Judge Result