Create a gist now

Instantly share code, notes, and snippets.

#include <bits/stdc++.h>
using namespace std;
#define int long long // <-----!!!!!!!!!!!!!!!!!!!
#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
#define rrep2(i,a,b) for (int i=(a)-1;i>=b;i--)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define printV(_v) for(auto _x:_v){cout<<_x<<" ";}cout<<endl
#define printVS(vs) for(auto x : vs){cout << x << endl;}
#define printVV(_vv) for(auto _v:_vv){for(auto _x:_v){cout<<_x<<" ";}cout<<endl;}
#define printP(p) cout << p.first << " " << p.second << endl
#define printVP(vp) for(auto p : vp) printP(p);
#define readV(_v) rep(j, _v.size()) cin >> _v[j];
#define readVV(_vv) rep(i, _vv.size()) readV(_vv[i]);
#define output(_x) cout << _x << endl;
typedef long long ll;
typedef pair<int, int> Pii;
typedef tuple<int, int, int> TUPLE;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<Pii> vp;
const int inf = 1e9;
const int mod = 1e9 + 7;
const int MAX = 52;
int n, m;
int a[MAX];
int b[MAX];
int dp[MAX][MAX][MAX][MAX][2][3];
int dfs(int l0, int r0, int l1, int r1, int turn, int pass, int p0, int p1) {
int& ret = dp[l0][r0][l1][r1][turn][pass];
if (ret != inf && ret != -inf) return ret;
if (!turn) {
// stackに積む場合
if (r0 < n) {
if (a[r0] > 0) {
// 得点カードを積む場合
ret = max(ret, dfs(l0, r0 + 1, l1, r1, turn^1, 0, p0 + a[r0], p1));
} else {
// 妨害カードを積む場合
ret = max(ret, dfs(l0, r0 + 1, l1, r1, turn^1, 0, p0, 0));
}
}
// パスする場合
if (l0 == r0 && l1 == r1) {
// stackが空のとき
if (pass == 0) {
assert(p0 == 0 && p1 == 0);
ret = max(ret, dfs(r0, r0, r1, r1, turn^1, 1, 0, 0));
} else if (pass == 1) {
ret = max(ret, 0ll);
}
} else {
// stackが空でないとき
assert(pass == 0);
ret = max(ret, dfs(r0, r0, r1, r1, turn^1, 0, 0, 0) + p0 - p1);
}
} else {
// stackに積む場合
if (r1 < m) {
if (b[r1] > 0) {
// 得点カードを積む場合
ret = min(ret, dfs(l0, r0, l1, r1 + 1, turn^1, 0, p0, p1 + b[r1]));
} else {
// 妨害カードを積む場合
ret = min(ret, dfs(l0, r0, l1, r1 + 1, turn^1, 0, 0, p1));
}
}
// パスする場合
if (l0 == r0 && l1 == r1) {
// stackが空のとき
if (pass == 0) {
assert(p0 == 0 && p1 == 0);
ret = min(ret, dfs(r0, r0, r1, r1, turn^1, 1, 0, 0));
} else if (pass == 1) {
ret = min(ret, 0ll);
}
} else {
// stackが空でないとき
assert(pass == 0);
ret = min(ret, dfs(r0, r0, r1, r1, turn^1, 0, 0, 0) + p0 - p1);
}
}
return ret;
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
cin >> n >> m;
rep(i, n) cin >> a[i];
rep(i, m) cin >> b[i];
rep(i, MAX) rep(j, MAX) rep(k, MAX) rep(l, MAX) rep(p, 2) rep(q, 3) {
dp[i][j][k][l][p][q] = (!p ? -inf : inf);
}
cout << dfs(0, 0, 0, 0, 0, 0, 0, 0) << endl;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment