Submission #1351973
Source Code Expand
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <functional>
using namespace std;
#define rep(i,a,n) for(int (i)=(a); (i)<(n); (i)++)
#define repq(i,a,n) for(int (i)=(a); (i)<=(n); (i)++)
#define repr(i,a,n) for(int (i)=(a); (i)>=(n); (i)--)
#define int long long int
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}
typedef pair<int, int> pii;
typedef long long ll;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
constexpr ll INF = 1001001001001001LL;
constexpr ll MOD = 1000000007LL;
int N, M, a[60], b[60];
int suma[60], sumb[60];
// memo[s][t][u][v][turn][pass] :=
// a についてスタックが [s, t) の範囲、
// b についてスタックが [u, v) の範囲、
// turn と pass の情報
// この時の point_a - point_b の値
int memo[60][60][60][60][2][3];
// pass は連続したパスの回数を指す
int dfs(int s, int t, int u, int v, int turn, int pass) {
int& val = memo[s][t][u][v][turn][pass];
if(val != -INF) return val;
// 今のスタックの状態で起こる得点差
val = suma[t] - suma[s];
val -= sumb[v] - sumb[u];
// 終了条件でなければ pass 可能
// パスすることによってスタックは空になる
// 以降の操作で得られる得点差をもらってくる
if(!(s == t && u == v && pass == 1)) {
if(s == t && u == v) val += dfs(t, t, v, v, turn^1, pass+1);
else val += dfs(t, t, v, v, turn^1, 0);
}
// take (first)
if(turn == 0) {
if(t < N) {
// 妨害 -> 現在スタックにある相手のカード全てが取れなくなる
// -> つまり相手スタックが空になるのと同じ
if(a[t] == -1) chmax(val, dfs(s, t+1, v, v, turn^1, 0));
else chmax(val, dfs(s, t+1, u, v, turn^1, 0));
}
}
// take (second)
else {
if(v < M) {
if(b[v] == -1) chmin(val, dfs(t, t, u, v+1, turn^1, 0));
else chmin(val, dfs(s, t, u, v+1, turn^1, 0));
}
}
return val;
}
signed main() {
rep(i,0,60) rep(j,0,60) rep(k,0,60) rep(l,0,60) rep(t,0,2) rep(p,0,3)
memo[i][j][k][l][t][p] = -INF;
cin >> N >> M;
rep(i,0,N) cin >> a[i];
rep(i,0,M) cin >> b[i];
// 1-indexed
rep(i,0,N) suma[i+1] = (a[i] == -1 ? suma[i] : suma[i] + a[i]);
rep(i,0,M) sumb[i+1] = (b[i] == -1 ? sumb[i] : sumb[i] + b[i]);
cout << dfs(0, 0, 0, 0, 0, 0) << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
D - インビジブル |
User |
tsutaj |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
3069 Byte |
Status |
MLE |
Exec Time |
224 ms |
Memory |
607872 KB |
Judge Result
Set Name |
All |
Score / Max Score |
0 / 100 |
Status |
|
Set Name |
Test Cases |
All |
00_sample_00, 00_sample_01, 00_sample_02, 30_random_small_000, 30_random_small_001, 30_random_small_002, 30_random_small_003, 30_random_small_004, 30_random_small_005, 30_random_small_006, 30_random_small_007, 30_random_small_008, 30_random_small_009, 31_random_skewed_000, 31_random_skewed_001, 31_random_skewed_002, 31_random_skewed_003, 31_random_skewed_004, 32_random_skewed_000, 32_random_skewed_001, 32_random_skewed_002, 32_random_skewed_003, 32_random_skewed_004, 33_random_frequent_invisible_000, 33_random_frequent_invisible_001, 33_random_frequent_invisible_002, 33_random_frequent_invisible_003, 33_random_frequent_invisible_004, 35_random_all_invisible_000, 36_random_all_same_score_000, 37_increasing_000, 38_decreasing_000, 40_random_max_000, 40_random_max_001, 40_random_max_002, 40_random_max_003, 40_random_max_004 |
Case Name |
Status |
Exec Time |
Memory |
00_sample_00 |
MLE |
224 ms |
607744 KB |
00_sample_01 |
MLE |
171 ms |
607744 KB |
00_sample_02 |
MLE |
150 ms |
607744 KB |
30_random_small_000 |
MLE |
150 ms |
607744 KB |
30_random_small_001 |
MLE |
150 ms |
607744 KB |
30_random_small_002 |
MLE |
149 ms |
607744 KB |
30_random_small_003 |
MLE |
150 ms |
607744 KB |
30_random_small_004 |
MLE |
150 ms |
607744 KB |
30_random_small_005 |
MLE |
149 ms |
607744 KB |
30_random_small_006 |
MLE |
150 ms |
607744 KB |
30_random_small_007 |
MLE |
149 ms |
607744 KB |
30_random_small_008 |
MLE |
149 ms |
607744 KB |
30_random_small_009 |
MLE |
150 ms |
607744 KB |
31_random_skewed_000 |
MLE |
150 ms |
607744 KB |
31_random_skewed_001 |
MLE |
152 ms |
607872 KB |
31_random_skewed_002 |
MLE |
150 ms |
607744 KB |
31_random_skewed_003 |
MLE |
150 ms |
607744 KB |
31_random_skewed_004 |
MLE |
150 ms |
607744 KB |
32_random_skewed_000 |
MLE |
150 ms |
607744 KB |
32_random_skewed_001 |
MLE |
150 ms |
607744 KB |
32_random_skewed_002 |
MLE |
150 ms |
607744 KB |
32_random_skewed_003 |
MLE |
150 ms |
607744 KB |
32_random_skewed_004 |
MLE |
150 ms |
607744 KB |
33_random_frequent_invisible_000 |
MLE |
150 ms |
607744 KB |
33_random_frequent_invisible_001 |
MLE |
150 ms |
607744 KB |
33_random_frequent_invisible_002 |
MLE |
150 ms |
607872 KB |
33_random_frequent_invisible_003 |
MLE |
150 ms |
607744 KB |
33_random_frequent_invisible_004 |
MLE |
150 ms |
607744 KB |
35_random_all_invisible_000 |
MLE |
149 ms |
607744 KB |
36_random_all_same_score_000 |
MLE |
157 ms |
607744 KB |
37_increasing_000 |
MLE |
157 ms |
607744 KB |
38_decreasing_000 |
MLE |
157 ms |
607744 KB |
40_random_max_000 |
MLE |
151 ms |
607744 KB |
40_random_max_001 |
MLE |
151 ms |
607744 KB |
40_random_max_002 |
MLE |
151 ms |
607744 KB |
40_random_max_003 |
MLE |
151 ms |
607872 KB |
40_random_max_004 |
MLE |
151 ms |
607744 KB |