Cod sursa(job #2085837)

Utilizator flibiaVisanu Cristian flibia Data 10 decembrie 2017 19:58:59
Problema Oo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.71 kb
#include <bits/stdc++.h>

using namespace std;

ifstream in("oo.in");
ofstream out("oo.out");

int n, a[100100], dp1[100100], dp2[100100], dp3[100100], bst;

void solve(int st){
	for(int i = 1; i <= n + 3; i++)
		dp1[i] = dp2[i] = dp3[i] = 0;
	int dr = st + n - 1;
	dp1[st] = a[st];
	dp2[st + 1] = a[st] + a[st + 1];
	for(int i = st + 2; i <= dr; i++){
		dp1[i] = dp3[i - 1] + a[i];
		dp2[i] = dp1[i - 1] + a[i];
		dp3[i] = max(dp3[i - 1], dp2[i - 1]);
		if(i < dr)
			bst = max(bst, dp2[i]);
		bst = max(bst, dp3[i]);
	}
}

int main(){
	in >> n;
	for(int i = 1; i <= n; i++)
		in >> a[i + 1];
	a[1] = a[n + 1];
	a[n + 2] = a[2];
	solve(1);	
	solve(2);
   solve(3);
	out << bst;
	return 0;
}