Submission #1350798
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
#define for_(i,a,b) for(int i=(a);i<(b);++i)
int n, m, a[55], b[55], dp[2][3][55][55][55][55];
int rec(int cur_a, int cur_b, int prv_a, int prv_b, int turn, int pass) {
if (cur_a == n && prv_a == n) {
int res = 0;
for_(i,prv_b,m) if (b[i] > 0) res -= b[i];
return res;
}
if (cur_b == m && prv_b == m) {
int res = 0;
for_(i,prv_a,n) if (a[i] > 0) res += a[i];
return res;
}
int& res = dp[turn][pass][cur_a][cur_b][prv_a][prv_b];
if (abs(res) != 1e9) return res;
if (turn == 0 && cur_a < n) res = max(res, rec(cur_a + 1, cur_b, prv_a, (a[cur_a] == -1 ? cur_b : prv_b), 1, 0));
if (turn == 1 && cur_b < m) res = min(res, rec(cur_a, cur_b + 1, (b[cur_b] == -1 ? cur_a : prv_a), prv_b, 0, 0));
int sum_a = 0, sum_b = 0;
for_(i,prv_a,cur_a) if (a[i] > 0) sum_a += a[i];
for_(i,prv_b,cur_b) if (b[i] > 0) sum_b += b[i];
if (turn == 0 && pass < 2) res = max(res, rec(cur_a, cur_b, cur_a, cur_b, 1, pass + 1) + sum_a - sum_b);
if (turn == 1 && pass < 2) res = min(res, rec(cur_a, cur_b, cur_a, cur_b, 0, pass + 1) + sum_a - sum_b);
return res;
}
int main() {
cin >> n >> m;
for_(i,0,n) cin >> a[i];
for_(i,0,m) cin >> b[i];
for_(t,0,2) for_(p,0,3) for_(i,0,55) for_(j,0,55) for_(ii,0,55) for_(jj,0,55) dp[t][p][i][j][ii][jj] = (t ? 1e9 : -(1e9));
cout << rec(0, 0, 0, 0, 0, 0) << endl;
}
Submission Info
Submission Time |
|
Task |
D - インビジブル |
User |
tsukasa_diary |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
1419 Byte |
Status |
WA |
Exec Time |
92 ms |
Memory |
214784 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 |
WA |
76 ms |
214656 KB |
00_sample_01 |
AC |
77 ms |
214656 KB |
00_sample_02 |
AC |
77 ms |
214656 KB |
30_random_small_000 |
WA |
76 ms |
214656 KB |
30_random_small_001 |
WA |
76 ms |
214656 KB |
30_random_small_002 |
WA |
77 ms |
214656 KB |
30_random_small_003 |
WA |
76 ms |
214656 KB |
30_random_small_004 |
AC |
76 ms |
214656 KB |
30_random_small_005 |
WA |
76 ms |
214784 KB |
30_random_small_006 |
WA |
76 ms |
214656 KB |
30_random_small_007 |
WA |
76 ms |
214656 KB |
30_random_small_008 |
WA |
76 ms |
214656 KB |
30_random_small_009 |
WA |
76 ms |
214656 KB |
31_random_skewed_000 |
WA |
77 ms |
214784 KB |
31_random_skewed_001 |
WA |
77 ms |
214784 KB |
31_random_skewed_002 |
WA |
77 ms |
214784 KB |
31_random_skewed_003 |
WA |
77 ms |
214784 KB |
31_random_skewed_004 |
WA |
77 ms |
214784 KB |
32_random_skewed_000 |
WA |
77 ms |
214784 KB |
32_random_skewed_001 |
WA |
77 ms |
214784 KB |
32_random_skewed_002 |
WA |
77 ms |
214784 KB |
32_random_skewed_003 |
WA |
77 ms |
214784 KB |
32_random_skewed_004 |
AC |
77 ms |
214784 KB |
33_random_frequent_invisible_000 |
WA |
77 ms |
214656 KB |
33_random_frequent_invisible_001 |
WA |
77 ms |
214656 KB |
33_random_frequent_invisible_002 |
WA |
77 ms |
214784 KB |
33_random_frequent_invisible_003 |
AC |
77 ms |
214656 KB |
33_random_frequent_invisible_004 |
WA |
77 ms |
214656 KB |
35_random_all_invisible_000 |
AC |
77 ms |
214784 KB |
36_random_all_same_score_000 |
AC |
91 ms |
214784 KB |
37_increasing_000 |
AC |
92 ms |
214784 KB |
38_decreasing_000 |
AC |
91 ms |
214784 KB |
40_random_max_000 |
WA |
78 ms |
214784 KB |
40_random_max_001 |
WA |
79 ms |
214784 KB |
40_random_max_002 |
WA |
79 ms |
214784 KB |
40_random_max_003 |
WA |
79 ms |
214784 KB |
40_random_max_004 |
WA |
79 ms |
214784 KB |