Cod sursa(job #2824087)

Utilizator Madalin_IonutFocsa Ionut-Madalin Madalin_Ionut Data 30 decembrie 2021 21:27:09
Problema Oo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <bits/stdc++.h>

using namespace std;

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

int n, a[100003], dp1[100003], dp2[100003], dp3[100003];
///dp1[i] - numarul maxim de oua colectate pana la pozitia i pornind cu sectoarele 1,2
///dp2[i] - numarul maxim de oua colectate pana la pozitia i pornind cu sectoarele 2,3
///dp3[i] - numarul maxim de oua colectate pana la pozitia i pornind cu sectoarele n, 1

int main()
{
	int i;
	fin >> n;
	for (i = 1; i <= n; i++)
		fin >> a[i];
	dp1[2] = dp1[3] = a[1] + a[2];
	dp2[3] = a[2] + a[3];
	dp3[1] = a[n] + a[1];
	for (i = 4; i <= n; i++)
	{
		if (i < n - 1) dp3[i] = max(dp3[i - 1], dp3[i - 3] + a[i] + a[i - 1]);
		if (i < n) dp1[i] = max(dp1[i - 1], dp1[i - 3] + a[i] + a[i - 1]);
		dp2[i] = max(dp2[i - 1], dp2[i - 3] + a[i] + a[i - 1]);
	}
	fout << max({ dp2[n], dp1[n - 1], dp3[n - 2] }) << "\n";
}