Submission #5447271

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;

int A,B;
vector<int> a, b;

int dp[1001][1001];

int turn1(int asize, int bsize);
int turn2(int asize, int bsize);


signed main()
{
  cin >> A >> B;
  a.reserve(A);
  b.reserve(B);
  for(int i=0; i<A; i++) cin >> a[i];
  for(int i=0; i<B; i++) cin >> b[i];

  std::fill( dp[0], dp[1000], -1 );

  cout << turn1(A,B) << endl;

  return 0;
}

int turn1(int asize, int bsize) {
  if(dp[asize][bsize] != -1) return dp[asize][bsize];
  if(asize ==0 && bsize == 0) return 0;
  if(asize == 0) return b[B-bsize] + turn2(asize, bsize-1);
  if(bsize == 0) return a[A-asize] + turn2(asize-1, bsize);

  return max(a[A-asize] + turn2(asize-1, bsize),
             b[B-bsize] + turn2(asize, bsize-1));
}

int turn2(int asize, int bsize) {
  if(dp[asize][bsize] != -1) return dp[asize][bsize];
  if(asize ==0 && bsize == 0) return 0;
  if(asize == 0) return turn1(asize, bsize-1);
  if(bsize == 0) return turn1(asize-1, bsize);

  return min(turn1(asize-1, bsize),
             turn1(asize, bsize-1));
}

Submission Info

Judge Result