提出 #534856

---

ソースコード 拡げる

#include<iostream>
#include<algorithm>
using namespace std;

int main(){
    int n;
    cin >> n;
    long a[n], b[n];
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> b[i];
    }
    long dp[n][n+1];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= n; j++) {
            dp[i][j] = -1;
        }
    }
    int x, y;
    if (a[0] < 0 && b[0] <= 0) {
        cout << 0 << endl;
    }else{
        long dp[2][n+1];
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < n+1; j++) {
                dp[i][j] = -1;
            }
        }
        dp[0][0] = b[0];
        dp[0][1] = a[0];
        long ans = max(dp[0][0], dp[0][1]);
        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= i+1; j++) {
                if (j == 0) {
                    dp[i%2][0] = dp[(i-1)%2][0]+b[0];
                }else{
                    if (dp[(i-1)%2][j-1]<0 && dp[(i-1)%2][j] < 0) {
                        dp[i%2][j] = -1;
                    }else if(dp[(i-1)%2][j-1]<0){
                        dp[i%2][j] =dp[(i-1)%2][j]+b[j];
                    }else if(dp[(i-1)%2][j] < 0){
                        dp[i%2][j] = dp[(i-1)%2][j-1]+a[j-1];
                    }else{
                        dp[i%2][j] = max(dp[(i-1)%2][j-1]+a[j-1], dp[(i-1)%2][j]+b[j]);
                    }
                }
                ans = max(ans, dp[i%2][j]);
            }
            if (ans < 0) {
                break;
            }
        }
        if (ans <= 0) {
            cout << 0 << endl;
        }else{
            cout << ans << endl;
        }
    }
    return 0;
}

提出情報

ジャッジ結果