Cod sursa(job #2305362)

Utilizator florin_salamFlorin Salam florin_salam Data 19 decembrie 2018 23:16:10
Problema Oo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <fstream>
#include <algorithm>

using namespace std;

const int NMAX = 1e5 + 5;
int n, a[NMAX], b[NMAX], c[NMAX], cost[NMAX];

int main()
{
	ifstream fin("oo.in");
	ofstream fout("oo.out");
	fin >> n;
	for (int i = 1;i <= n;++i)
		fin >> cost[i];
	cost[n + 1] = cost[1];
	//daca luam gainile 1 si 2: 0, 1 1 0
	a[2] = a[3] = cost[1] + cost[2];
	for (int i = 4;i <= n - 1;++i)
		a[i] = max(a[i - 1], a[i - 3] + cost[i] + cost[i - 1]);
	//daca luam gainile 2 si 3: 0 1 1 0
	b[3] = b[4] = cost[2] + cost[3];
	for (int i = 5;i <= n;++i)
		b[i] = max(b[i - 1], b[i - 3] + cost[i] + cost[i - 1]);
	//daca luam gainile 3 si 4: ? 0 1 1 0
	c[4] = c[5] = cost[3] + cost[4];
	for (int i = 6;i <= n + 1;++i)
		c[i] = max(c[i - 1], c[i - 3] + cost[i] + cost[i - 1]);
	fout << max(a[n - 1], max(b[n], c[n + 1])) << "\n";
	fin.close();
	fout.close();
	return 0;
}