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
AC × 37
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