Submission #5898037

---

Source Code Expand

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

static const int MAX = 1000;

int main(){
    int A, B;
    cin >> A >> B;
    vector<int> left(A), right(B);

    for(int i= 0 ; i < A; i++){
        cin >> left[i];
    }
    for(int i = 0; i < B; i++){
        cin >> right[i];
    }
    int pointa = A, pointb = B;

    bool s = (A + B) % 2;
    int sumu = 0, sume = 0;

    int dp[MAX+1][MAX+1];//状態量を意識する（ここでは右・左の残りの数に最善手を行ったときの価値を載せていく)
    //dp[i][j] := 左の山にi個、右の山にj個残ってる時に先手が終了までに手に入れることのできる価値
    //先手 = すぬけ
    dp[0][0] = 0;
    /*
    int cnt = 1;
    while(cnt <= A + B){
        if(s == 0){
            for(int i = 0; i <= cnt; i++){
                if(cnt - i <= ) dp[i][cnt-i] = min(dp[i-1][cnt-i], dp[i][cnt-i-1]);

            }
        }else{
            dp[pointa][pointb-1] = dp[pointa][pointb];
        }
        s = !s;
        cnt++;
    }
    */
    for(int i = 1; i <= B; i++){
        if( i % 2 == (A + B) % 2 ){
            dp[0][i] = dp[0][i-1] + right[B - i];
        }else{
            dp[0][i] = dp[0][i-1];
        }
    }
    for(int i = 1; i <= A; i++){
        if( i%2 == (A+B)%2 ){
            dp[i][0] = dp[i-1][0] + left[A-i];
        }else{
            dp[i][0] = dp[i-1][0];
        }
    }

    for(int i = 1; i <= A; i++){
        for(int j = 1; j <= B; j++){
            if((i + j) % 2 == (A + B) % 2){
                dp[i][j] = max(dp[i-1][j] + left[A-i], dp[i][j-1] + right[B-j]);
            }else{
                dp[i][j] = min(dp[i-1][j], dp[i][j-1]);
            }
        }
    }
/*
    for(int i = 0; i <= A; i++){
        for(int j = 0; j <= B; j++){
            cout << dp[i][j] << " ";
        }
        cout << endl;
    }
*/
    cout << dp[A][B] << endl;

    return 0;
}

Submission Info

Judge Result