Submission #1187291
Source Code Expand
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef tuple<int,int,int,int,int,int,int> P;
map<P,int> mp;
int n,m;
int a[51],b[51];
int dfs(int al,int ar,int bl,int br,int f,int t,int s){
if(mp.count(make_tuple(al,ar,bl,br,f,t,s)))
return mp[make_tuple(al,ar,bl,br,f,t,s)];
//cout<<al<<" "<<ar<<" "<<bl<<" "<<br<<" "<<f<<" "<<t<<" "<<s<<endl;
int res;
if(s==2){
res=0;
}else{
int ta=0,tb=0;
int ia=al,ib=bl;
while(ia<ar||ib<br){
if(f){
if(ib<br){
if(~b[ib]) tb+=b[ib];
else ta=0;
ib++;
}
if(ia<ar){
if(~a[ia]) ta+=a[ia];
else tb=0;
ia++;
}
}else{
if(ia<ar){
if(~a[ia]) ta+=a[ia];
else tb=0;
ia++;
}
if(ib<br){
if(~b[ib]) tb+=b[ib];
else ta=0;
ib++;
}
}
}
res=ta-tb;
if(t) res*=-1;
res-=dfs(ar,ar,br,br,!t,!t,s+1);
}
if(t==1&&br<m){
res=max(res,-dfs(al,ar,bl,br+1,f,!t,0));
}
if(t==0&&ar<n){
res=max(res,-dfs(al,ar+1,bl,br,f,!t,0));
}
//cout<<al<<" "<<ar<<" "<<bl<<" "<<br<<" "<<f<<" "<<t<<" "<<s<<"/"<<res<<endl;
return mp[make_tuple(al,ar,bl,br,f,t,s)]=res;
}
signed main(){
cin>>n>>m;
for(int i=0;i<n;i++) cin>>a[i];
for(int i=0;i<m;i++) cin>>b[i];
cout<<dfs(0,0,0,0,0,0,0)<<endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
D - インビジブル |
User |
beet |
Language |
C++14 (GCC 5.4.1) |
Score |
100 |
Code Size |
1377 Byte |
Status |
AC |
Exec Time |
144 ms |
Memory |
20480 KB |
Judge Result
Set Name |
All |
Score / Max Score |
100 / 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 |
AC |
1 ms |
256 KB |
00_sample_01 |
AC |
1 ms |
256 KB |
00_sample_02 |
AC |
1 ms |
256 KB |
30_random_small_000 |
AC |
2 ms |
384 KB |
30_random_small_001 |
AC |
1 ms |
256 KB |
30_random_small_002 |
AC |
1 ms |
256 KB |
30_random_small_003 |
AC |
1 ms |
384 KB |
30_random_small_004 |
AC |
1 ms |
256 KB |
30_random_small_005 |
AC |
2 ms |
384 KB |
30_random_small_006 |
AC |
1 ms |
256 KB |
30_random_small_007 |
AC |
1 ms |
256 KB |
30_random_small_008 |
AC |
1 ms |
256 KB |
30_random_small_009 |
AC |
1 ms |
256 KB |
31_random_skewed_000 |
AC |
9 ms |
1920 KB |
31_random_skewed_001 |
AC |
9 ms |
1920 KB |
31_random_skewed_002 |
AC |
7 ms |
1408 KB |
31_random_skewed_003 |
AC |
2 ms |
512 KB |
31_random_skewed_004 |
AC |
9 ms |
1920 KB |
32_random_skewed_000 |
AC |
6 ms |
1408 KB |
32_random_skewed_001 |
AC |
1 ms |
384 KB |
32_random_skewed_002 |
AC |
5 ms |
1280 KB |
32_random_skewed_003 |
AC |
1 ms |
384 KB |
32_random_skewed_004 |
AC |
1 ms |
384 KB |
33_random_frequent_invisible_000 |
AC |
3 ms |
640 KB |
33_random_frequent_invisible_001 |
AC |
49 ms |
8320 KB |
33_random_frequent_invisible_002 |
AC |
31 ms |
5376 KB |
33_random_frequent_invisible_003 |
AC |
3 ms |
640 KB |
33_random_frequent_invisible_004 |
AC |
3 ms |
768 KB |
35_random_all_invisible_000 |
AC |
4 ms |
1024 KB |
36_random_all_same_score_000 |
AC |
135 ms |
20480 KB |
37_increasing_000 |
AC |
137 ms |
20480 KB |
38_decreasing_000 |
AC |
138 ms |
20480 KB |
40_random_max_000 |
AC |
144 ms |
20480 KB |
40_random_max_001 |
AC |
143 ms |
20480 KB |
40_random_max_002 |
AC |
141 ms |
20480 KB |
40_random_max_003 |
AC |
142 ms |
20480 KB |
40_random_max_004 |
AC |
142 ms |
20480 KB |