Submission #17876430

---

Source Code Expand

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

int main()
{
    static const int64_t inf = 1e+13;
    int N;
    cin >> N;
    vector<int64_t> A_vec(N);
    for (int i = 0; i < N; ++i)
        cin >> A_vec.at(i);
    vector<vector<int64_t>> dp(N/2 + 1, vector<int64_t>(N, -inf));
    for (int j = 0; j < N; ++j)
        dp.at(0).at(j) = 0;
    for (int i = 0; i < N/2; ++i) {
        for (int j = 0; j < N; ++j) {
            int j1 = (j + 1) % N;
            int j2 = (j + 2*i) % N;
            int j3 = (j - 1 + N) % N;
            int j4 = (j + 2*i + 1) % N;
            int64_t A_j = A_vec.at(j);
            int64_t A_j2 = A_vec.at(j2);
            int64_t tmp = max(dp[i][j] + A_j2, dp[i][j1] + A_j);
            if (A_vec.at(j3) < A_vec.at(j4))
                dp[i + 1][j] = max(dp[i + 1][j], tmp);
            else
                dp[i + 1][j3] = max(dp[i + 1][j3], tmp);
        }
    }
    if (N % 2 == 0) {
        cout << *max_element(dp[N/2].begin(), dp[N/2].end()) << endl;
        return 0;
    }
    int64_t max_sum = -1;
    for (int j = 0; j < N; ++j) {
        int j3 = (j + N - 1) % N;
        int64_t sum = dp[N/2][j] + A_vec.at(j3);
        if (max_sum < sum)
            max_sum = sum;
    }
    cout << max_sum << endl;
}

Submission Info

Judge Result