Submission #3900997

---

Source Code Expand

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

int64_t dp[2001][2001][2];
void chmax(int64_t& a, int64_t b){
    a = max(a, b);
}

int main(){
    int L, N, X[2001], Y[2001];
    cin >> L >> N;
    for(int i=1; i<=N; i++){
        cin >> X[i];
        Y[N+1-i] = L - X[i];
    }
    X[0] = Y[0] = 0;

    assert(N<=2000);

    for(int i=0; i<=N; i++){
        for(int j=0; j<=N; j++){
            if(i<N){
                chmax(dp[i+1][j][0], dp[i][j][0] + X[i+1] - X[i]);
                chmax(dp[i+1][j][0], dp[i][j][1] + X[i+1] + Y[j]);
            }
            if(j<N){
                chmax(dp[i][j+1][1], dp[i][j][1] + Y[j+1] - Y[j]);
                chmax(dp[i][j+1][1], dp[i][j][0] + X[i] + Y[j+1]);
            }
        }
    }
    int64_t ans = 0;
    for(int i=0; i<=N; i++) for(int k=0; k<2; k++){
        chmax(ans, dp[i][N-i][k]);
    }
    cout << ans << endl;
    return 0;
}

Submission Info

Judge Result