Submission #5447489

---

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[1001], -1 );
  dp[0][0] = 0;

  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) {
    int t = b[B-bsize] + turn2(asize, bsize-1);
    dp[asize][bsize] = t;
    return t;
  }

  if(bsize == 0) {
    int t = a[A-asize] + turn2(asize-1, bsize); 
    dp[asize][bsize] = t;
    return t;
  }

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

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) {
    int t = turn1(asize, bsize-1); 
    dp[asize][bsize] = t;
    return t;
  }
  if(bsize == 0) {
    int t = turn1(asize-1, bsize);
    dp[asize][bsize] = t;
    return t;
  }

  int t = min(turn1(asize-1, bsize),
              turn1(asize, bsize-1));
  dp[asize][bsize] = t;
  return t;
}

Submission Info

Judge Result