Yellow Yacht

#include <iostream>
#include <cmath>

using namespace std;
typedef long long ll;

int n;
ll t[10005];
ll st[18][10005];

ll res = 0;

ll rmq(int a, int b) {
	int l = b-a+1;
	int k = (int)log2(l);
	return max(t[st[k][a]], t[st[k][a+(l-(1<<k))]]);
}

int main() {
	cin >> n;
	n++;
	for (int i = 0; i < n; ++i) {
		cin >> t[i];
	}
	
	for (int i = 0; i < n; ++i) st[0][i] = i;
	for (int j = 1; (1<<j) <= n; ++j) {
		for (int i = 0; i + (1<<j) <= n; ++i) {
			ll a = st[j-1][i];
			ll b = st[j-1][i+(1<<(j-1))];
			if (t[a] >= t[b]) st[j][i] = a;
			else st[j][i] = b;
		}
	}

	int m = n-1;
	for (int i = 0; i <= m; ++i) {
		for (int j = 0; j <= m; ++j) {
			if (i+j > m) break;
			ll cres = t[i]+t[j];
			int mx = (n-1)-(i+j);
			cres += rmq(0, mx);
			res = max(res, cres);
		}
	}
	cout << res << "\n";
	return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED

Test 18

Verdict: ACCEPTED

Test 19

Verdict: ACCEPTED

Test 20

Verdict: ACCEPTED

Test 21

Verdict: ACCEPTED

Test 22

Verdict: ACCEPTED

Test 23

Verdict: ACCEPTED

Test 24

Verdict: ACCEPTED

Test 25

Verdict: ACCEPTED

Test 26

Verdict: ACCEPTED

Test 27

Verdict: ACCEPTED

Test 28

Verdict: ACCEPTED

Test 29

Verdict: ACCEPTED

Test 30

Verdict: ACCEPTED

Test 31

Verdict: ACCEPTED

Test 32

Verdict: ACCEPTED

Test 33

Verdict: ACCEPTED

Test 34

Verdict: ACCEPTED

Test 35

Verdict: ACCEPTED

Test 36

Verdict: ACCEPTED

Test 37

Verdict: ACCEPTED

Test 38

Verdict: ACCEPTED

Test 39

Verdict: ACCEPTED

Test 40

Verdict: ACCEPTED