Submission #3423501

---

Source Code Expand

#include <algorithm>
#include <functional>
#include <iostream>
#include <vector>

using namespace std;
#define rep(i, N) for (int i = 0; i < (N); i++)

const int INF = 1e8;

int main() {
    int NA, NB;
    cin >> NA >> NB;
    vector<int> A(NA), B(NB);
    rep(i, NA) cin >> A[i];
    rep(i, NB) cin >> B[i];

    vector<vector<int>> dp(NA + 1, vector<int>(NB + 1, -1));

    function<int(bool, int, int)> dfs = [&](bool snuke, int a, int b) {
        if (dp[a][b] > 0) return dp[a][b];
        if (a == NA and b == NB) return 0;
        int worst       = snuke ? -INF : INF;
        int l           = a < NA ? dfs(!snuke, a + 1, b) + A[a] * snuke : worst;
        int r           = b < NB ? dfs(!snuke, a, b + 1) + B[b] * snuke : worst;
        return dp[a][b] = snuke ? max(l, r) : min(l, r);
    };
    cout << dfs(true, 0, 0) << endl;
    return 0;
}

Submission Info

Judge Result