Submission #6438133

---

Source Code Expand

#include <bits/stdc++.h>
#define debug(x) cerr << #x << ": " << x << '\n';
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int INF = (int)1e9;

int main(void){
    int A, B;
    cin >> A >> B;
    vector<int> a(A), b(B);
    for(int i = 0; i < A; i++) cin >> a[i];
    for(int i = 0; i < B; i++) cin >> b[i];

    vector<vector<int>> dp(A+1, vector<int>(B+1));
    for(int i = 0; i <= A; i++){
        for(int j = 0; j <= B; j++){
            if(i == 0 and j == 0)continue;

            if((A+B-i-j)&1){
                if(i == 0) dp[i][j] = dp[i][j-1];
                else if(j == 0) dp[i][j] = dp[i-1][j];
                else dp[i][j] = min(dp[i-1][j], dp[i][j-1]);
            }else{
                if(i == 0) dp[i][j] = dp[i][j-1] + b[B-j];
                else if(j == 0) dp[i][j] = dp[i-1][j] + a[A-i];
                else dp[i][j] = max(dp[i-1][j] + a[A-i], dp[i][j-1] + b[B-j]);
            }
        }
    }

    cout << dp[A][B] << '\n';

    return 0;
}

Submission Info

Judge Result