Submission #17517104


Source Code Expand

Copy
#include <iostream>
#include <algorithm>
using namespace std;

const int INF = 1e8;
int dp[1002][1002], A[1001], B[1001], an, bn;

int dfs(int a, int b) {
	if (a == an && b == bn) return 0;
	if (dp[a][b] > 0) return dp[a][b];

	int res;

	if ((a + b) & 1) {
		res = INF;
		if (an > a) res = min(res, dfs(a + 1, b));
		if (bn > b) res = min(res, dfs(a, b + 1));
	}
	else {
		res = 0;
		if (an > a) res = max(res, dfs(a + 1, b) + A[a]);
		if (bn > b) res = max(res, dfs(a, b + 1) + B[b]);
	}
	return dp[a][b] = res;
}

int main() {
	cin >> an >> bn;
	for (int i = 0; i < an; i++) cin >> A[i];
	for (int i = 0; i < bn; i++) cin >> B[i];
	cout << dfs(0, 0) << endl;

	return 0;
}

Submission Info

Submission Time
Task B - ゲーム
User nekosun
Language C++ (GCC 9.2.1)
Score 3
Code Size 708 Byte
Status
Exec Time 25 ms
Memory 7548 KB

Judge Result

Set Name All
Score / Max Score 3 / 3
Status
× 5
Set Name Test Cases
All 00, 01, 02, 90, 91
Case Name Status Exec Time Memory
00 9 ms 3408 KB
01 18 ms 6624 KB
02 25 ms 7548 KB
90 4 ms 3492 KB
91 3 ms 3604 KB