Submission #1444414

---

Source Code Expand

#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(),(x).end()
#define LL long long

using namespace std;

int main(){
    int A,B;
    cin>>A>>B;
    int a[A];
    int b[B];
    REP(i,A)cin>>a[i];
    REP(i,B)cin>>b[i];
    int sum[A+1][B+1];
    int dp[A+1][B+1];
    fill(sum[0],sum[A+1],0);
    fill(dp[0],dp[A+1],0);

    REP(i,A+1){
        if(i>0)sum[i][0]=sum[i-1][0]+a[i-1];
        REP(j,B+1){
            if(j>0)sum[i][j]=sum[i][j-1]+b[j-1];
            if(i>0)dp[i][j]=sum[i][j]-dp[i-1][j];
            if(j>0)dp[i][j]=max(dp[i][j],sum[i][j]-dp[i][j-1]);
        }
    }

    cout<<((A+B)%2==0 ? sum[A][B]-max(dp[A-1][B],dp[A][B-1]) : dp[A][B])<<endl;

    return 0;
}

Submission Info

Judge Result