ProblemSolving/10714.cpp at master · mimseong/ProblemSolving · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <bitset>
#include <stdio.h>
#include <math.h>
#include <sstream>
#include<cassert>
#include <climits>
#include <tuple>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()
#define MAXV 987654321
#define FOR(i, n) for(int i = 0; i < (n); ++i)

using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using iis = pair<int, string>;
using ii64 = pair<i64, i64>;
using iii = tuple<int, int, int>;

int N;
i64 v[2005];
i64 dp[2005][2005];

i64 ioi(int li, int ri);
i64 joi(int li, int ri);

int left(int idx) {
    return (idx-1+N)%N;
}

int right(int idx) {
    return (idx+1)%N;
}

i64 ioi(int li, int ri) {
    if (left(li) == ri)
        return 0;
    if (v[left(li)] > v[right(ri)])
        return joi(left(li), ri);
    return joi(li, right(ri));
}

i64 joi(int li, int ri) {
    auto& ret = dp[li][ri];
    if (ret != -1)
        return ret;
    if (left(li) == ri)
        return 0;
    i64 ans1 = v[left(li)] + ioi(left(li), ri);
    i64 ans2 = v[right(ri)] + ioi(li, right(ri));
    return ret = max(ans1, ans2);
}

int main() {
	scanf("%d", &N);

	FOR(i, N) scanf("%lld", &v[i]);
	memset(dp, -1, sizeof(dp));

	i64 ans = 0;
	FOR(i, N) {
	    ans = max(ans, v[i] + ioi(i, i));
	}
	printf("%lld\n", ans);

	return 0;
}