1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
| #include <iostream>
#include <sstream>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>
#include <map>
#include <stack>
#define REP(i, k, n) for(int i = k; i < n; i++)
#define rep(i, n) for(int i = 0; i < n; i++)
#define INF 1<<30
using namespace std;
typedef pair<int, int> P;
int n, m;
vector<int> a, b;
int f(stack<P> &st) {
int c = 0, d = 0;
bool cf = true, df = true;
while(st.size()) {
P p = st.top(); st.pop();
if(p.first == 0) {
if(p.second == -1) {
df = false;
} else if(cf) {
c += p.second;
}
} else {
if(p.second == -1) {
cf = false;
} else if(df) {
d += p.second;
}
}
}
return c - d;
}
int memo[55][55][2][2][105];
int dfs(int i, int j, stack<P> st, int turn, bool flag) {
if(memo[i][j][turn % 2][flag][st.size()] != INF) return memo[i][j][turn % 2][flag][st.size()];
int ret = 0, size = st.size();
if(flag) {
if(turn % 2 == 0) {
ret = 0;
if(i != n) {
st.push(P(0, a[i]));
ret = max(ret, dfs(i + 1, j, st, turn + 1, false));
st.pop();
}
} else {
ret = 0;
if(j != m) {
st.push(P(1, b[j]));
ret = min(ret, dfs(i, j + 1, st, turn + 1, false));
st.pop();
}
}
} else {
if(turn % 2 == 0) {
ret = -INF;
if(i != n) {
st.push(P(0, a[i]));
ret = max(ret, dfs(i + 1, j, st, turn + 1, false));
st.pop();
}
bool ch = (st.size() == 0);
int d = f(st);
ret = max(ret, dfs(i, j, st, turn + 1, ch) + d);
} else {
ret = INF;
if(j != m) {
st.push(P(1, b[j]));
ret = min(ret, dfs(i, j + 1, st, turn + 1, false));
st.pop();
}
bool ch = (st.size() == 0);
int d = f(st);
ret = min(ret, dfs(i, j, st, turn + 1, ch) + d);
}
}
return memo[i][j][turn % 2][flag][size] = ret;
}
int main() {
cin >> n >> m;
a.resize(n);
rep(i, n) cin >> a[i];
b.resize(m);
rep(i, m) cin >> b[i];
stack<P> st;
rep(i, 55) rep(j, 55) rep(k, 2) rep(l, 2) rep(o, 105) memo[i][j][k][l][o] = INF;
cout << dfs(0, 0, st, 0, false) << endl;
return 0;
}
|