Cod sursa(job #2467702)

Utilizator dorufDoru Floare doruf Data 4 octombrie 2019 21:09:45
Problema Oo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.77 kb
#include <fstream>
#include <algorithm>
using namespace std;

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

const int MaxN = 5 + 100000;
int O[MaxN];
int dp[MaxN][3];
int n;

int main()
{
	fin >> n;

	for (int i = 1; i <= n; ++i)
		fin >> O[i];

	O[n + 1] = O[1];
	O[n + 2] = O[2];

	dp[2][0] = O[1] + O[2];
	dp[3][1] = O[2] + O[3];
	dp[4][2] = O[3] + O[4];

	for (int i = 3; i < n; ++i)
		dp[i][0] = max(dp[i - 1][0], dp[i - 3][0] + O[i] + O[i - 1]);

	for (int i = 4; i <= n; ++i)
		dp[i][1] = max(dp[i - 1][1], dp[i - 3][1] + O[i] + O[i - 1]);

	for (int i = 5; i <= n + 1; ++i)
		dp[i][2] = max(dp[i - 1][2], dp[i - 3][2] + O[i] + O[i - 1]);

	fout << max(dp[n - 1][0], max(dp[n][1], dp[n + 1][2]));

	fin.close();
	fout.close();

	return 0;
}