Submission #5412796

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

#define REP(i,n) for(int i=0;i<n;i++)
typedef long long int lli;
typedef pair<int, int> P;


// dp[i][j]: ai、bj まで使った状態での価値の最大値
lli dp[1001][1001];
int main() {
    int A, B;
    cin >> A >> B;
    lli a[A];
    lli b[B];
    REP(i, A) {
        cin >> a[i];
    }
    REP(i, B) {
        cin >> b[i];
    }

    lli ans = 1;
    for(int i=0;i<=A;i++) {
        for (int j=0; j<=B; j++) {
            // 相手のターン
            if ((i + j) % 2 == 1) {
                // a を使う
                if (i < A)
                    dp[i+1][j] = dp[i][j];
                // b を使う
                if (j < B)
                    dp[i][j+1] = dp[i][j];
            }
            else {
                // a を使う
                if (i < A)
                    dp[i+1][j] = max(dp[i+1][j], dp[i][j] + a[i]);
                // b を使う
                if (j < B)
                    dp[i][j+1] = max(dp[i][j+1], dp[i][j] + b[j]);
                //if (i == 0 && j == 1) {
                //    cout << "dp["<<i<<"]["<<j<<"]: " << dp[i][j]<<endl;
                //    cout << "dp["<<i<<"]["<<j+1<<"]: " << dp[i][j+1]<<endl;
                //    cout << "dp["<<i+1<<"]["<<j<<"]: " << dp[i+1][j]<<endl;
                //}
            }
        }
    }

    //for(int i=0;i<=A;i++) {
    //    for (int j=0; j<=B; j++) {
    //        cout << "dp["<<i<<"]["<<j<<"]: " << dp[i][j]<<endl;
    //    }
    //}


    cout << dp[A][B] << endl;
}

Submission Info

Judge Result