Submission #1595354

---

Source Code Expand

//http://tdpc.contest.atcoder.jp/tasks/tdpc_game
//http://tdpc.contest.atcoder.jp/submissions/1532417
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <vector>
#include <string>
#include <string.h>
#include <iomanip>
#include <limits>
using namespace std;
const long long int INF=1e17;
const int MAX_N=10000;
int A,B,a[1000],b[1000];

int dp[1001][1001]; 
//dp[i][j]=Aがi個、Bがj個残っている状態から始めた時の終了時の価値の最大値。
//dp[i][j] = max(dp[i-1][j]+a[A-i+1], dp[i][j-1]+b[B-i+1]) /先手の番
//dp[i][j] = min(dp[i-1][j],dp[i][j-1]) /後手の番、先手の価値が少なくなるように動く
//dp[i][0] = dp[i-1][0]+a[A-i+1] /先手
//dp[i][0] = dp[i-1][0] /後手
//dp[0][j] = dp[0][j-1]+b[B-i+1] /先手
//dp[0][j] = dp[0][j-1] /後手

int main(){
	cin >> A >> B;
	for(int i=0;i<A;i++) cin >> a[i];
	for(int i=0;i<B;i++) cin >> b[i];
	
	int f=(A+B)%2;
	dp[0][0]=0;
	for(int i=0;i<A;i++) dp[i+1][0] = ((i+1)%2==f?dp[i][0]+a[A-i-1]:dp[i][0]);
	for(int j=0;j<B;j++) dp[0][j+1] = ((j+1)%2==f?dp[0][j]+b[B-j-1]:dp[0][j]);
	for(int i=0;i<A;i++){
		for(int j=0;j<B;j++){
			if((i+j)%2==f) dp[i+1][j+1] = max(dp[i][j+1]+a[A-i-1], dp[i+1][j]+b[B-j-1]);
			else dp[i+1][j+1] = min(dp[i][j+1],dp[i+1][j]);
		}
	}
	
	cout << dp[A][B] << endl;
	return 0;
}

Submission Info

Judge Result