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
AC × 9
WA × 28
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