Submission #97406

---

Source Code Expand

#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <typeinfo>
#include <queue>

using namespace std;
typedef long long ll;
int a, b;
int ad[1003], bd[1003];
int dp[1003][1003];

int calc(int x, int y) {
	if (dp[x][y] != -1) return dp[x][y];
	if (x > a || y > b) return -1;
	if (x == a && y == b) return 0;
	int r = 1e8;
	if ((x+y)%2) {
		if (x < a) {
			r = calc(x+1, y);
		}
		if (y < b) {
			r = min(r, calc(x, y+1));
		}
		dp[x][y] = r;
		return r;
	} else {
		r = 0;
		if (x < a) {
			r = calc(x+1, y) + ad[x];
		}
		if (y < b) {
			r = max(r, calc(x, y+1) + bd[y]);
		}
		dp[x][y] = r;
		return r;
	}
}

int main() {
	cin >> a >> b;
	for (int i = 0; i < a; i++) {
		cin >> ad[i];
	}
	for (int i = 0; i < b; i++) {
		cin >> bd[i];
	}
	fill((int *)dp, (int *)dp+1003*1003, -1);
	cout << calc(0, 0) << endl;
	return 0;
}

Submission Info

Judge Result