Cod sursa(job #2108402)

Utilizator brczBereczki Norbert Cristian brcz Data 18 ianuarie 2018 10:41:53
Problema Oo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#include<bits/stdc++.h>

#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define sz size
#define pb push_back
#define mp make_pair
#define bg begin
#define nd end
using namespace std;

#define int long long

const int maxn = 100003;
const int maxk = 1003;

int n;
int a[maxn];
int dp[maxn];

int sub(int a,int b) {
	int ret = a - b;
	if(ret < 0 ) ret+=n;
	return ret;
}

void print_dp() {
	for(int i=0;i<n;++i) {
		cout << dp[i] << ' ';
	}
	cout << '\n';
}

int32_t main(){

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

	ios_base::sync_with_stdio(false);
	cin.tie(0);

	fin >> n;
	for(int i=0;i<n;++i) {
		fin >> a[i];
	}
	dp[0] = dp[1] = dp[2] = dp[3] = a[0] + a[1];
	for(int i=4;i<n-1;++i) {
		dp[i] = max(dp[i-1],a[i] + a[i-1] + dp[i-3]);
	}
	int res = dp[n-2];
	dp[0] = dp[1] = dp[2] = a[n-1] + a[0];
	for(int i=3;i<n-2;++i) {
		dp[i] = max(dp[i-1],a[i] + a[i-1] + dp[i-3]);
	}
	res = max(res,dp[n-3]);
	dp[0] = dp[1] = 0;
	dp[2] = a[2] + a[1];
	for(int i=3;i<n;++i) {
		dp[i] = max(dp[i-1],dp[i-3] + a[i] + a[i-1]);
	}
	res = max(res,dp[n-1]);

	fout << res << '\n';

	return 0;
}