Submission #1232596

---

Source Code Expand

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <set>
using namespace std;

int m,n;
vector<vector<long long>> mem;
vector<long long> a,b;
vector<long long> sua,sub;
long long solve(int i, int j){
  if(mem[i][j]>-1)return mem[i][j];
  long long res=0;
  if(i==m&&j==n)return 0;
  if(i==m){
    int jp=j;
    while(jp<n){
      res+=b[jp];
      jp+=2;
    }
    mem[i][j]=res;
    return res;
  }
  if(j==n){
    int ip=i;
    while(ip<m){
      res+=a[ip];
      ip+=2;
    }
    mem[i][j]=res;
    return res;
  }
  res=min(solve(i+1,j),solve(i,j+1));
  res=sua[i]+sub[j]-res;
  mem[i][j]=res;
  // cout<<i<<" "<<j<<" "<<res<<endl;
  return res;
}
long long M=1000000007;
int main(int argc, char const *argv[]) {
  cin>>m>>n;
  a=vector<long long>(m);
  b=vector<long long>(n);
  for(int i=0;i<m;++i)cin>>a[i];
  for(int i=0;i<n;++i)cin>>b[i];
  sua=vector<long long>(m+1);
  sub=vector<long long>(n+1);
  for(int i=m-1;i>-1;--i)sua[i]=sua[i+1]+a[i];
  for(int i=n-1;i>-1;--i)sub[i]=sub[i+1]+b[i];
  mem=vector<vector<long long>>(m+1,vector<long long>(n+1,-1));
  cout<<solve(0,0)<<endl;
  return 0;
}

Submission Info

Judge Result