Submission #17877614

---

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 + 1, vector<int64_t>(N, -inf));
    for (int j = 0; j < N; ++j)
        dp[0][j] = 0;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            int j1 = (j + 1) % N;
            int j2 = (j + i) % N;
            int j3 = (j + N - 1) % N;
            int64_t A_j = A_vec.at(j);
            int64_t A_j2 = A_vec.at(j2);
            int64_t A_j3 = A_vec.at(j3);
            if (i % 2 == 0)
                dp[i + 1][j] = max(dp[i][j1] + A_j, dp[i][j] + A_j2);
            else if (A_j3 < A_j2)
                dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);
            else
                dp[i + 1][j3] = max(dp[i + 1][j3], dp[i][j]);
        }
    }
    cout << *max_element(dp[N].begin(), dp[N].end()) << endl;
}

Submission Info

Judge Result