Cod sursa(job #389726)

Utilizator alexandru.mMardare Alexandru-Gabriel alexandru.m Data 2 februarie 2010 10:42:41
Problema Oo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include<fstream>
#include<iostream>

using namespace std;

int a[100001],n,c[100001],d[100001],e[100001];

void Citire()
{
	int i;
	ifstream f("oo.in");
	f>>n;
	for (i=0;i<n;i++)
		f>>a[i];
	f.close();
}

int Maxim(int a, int b)
{
	return a>b?a:b;
}

void Solve()
{
	int i,maxim;
	maxim=-1;
	
	if (n==2) maxim=a[0]+a[1];
	else 
		if (n==3) 
		{
			maxim=a[0]+a[1];
			if (maxim<a[1]+a[2]) maxim=a[1]+a[2];
		}
	else
	{
		c[0]=0;
		c[1]=a[0]+a[1];
		c[2]=c[1];
		c[3]=c[1];
		for (i=4;i<=n-2;i++)
			c[i]=Maxim(a[i]+a[i-1]+c[i-3], c[i-1]);
		maxim=c[n-2];
		d[1]=0;
		d[2]=a[1]+a[2];
		d[3]=d[2];
		d[4]=d[2];
		for (i=5;i<=n-1;i++)
			d[i]=Maxim(a[i]+a[i-1]+d[i-3],d[i-1]);
		if (maxim<d[n-1]) maxim=d[n-1];
		e[0]=a[0]+a[n-1];
		e[1]=e[0];
		e[2]=e[0];
		for (i=3;i<=n-3;i++)
			e[i]=Maxim(a[i]+a[i-1]+e[i-3], e[i-1]);
		if (maxim<e[n-3]) maxim=e[n-3];
	}
	ofstream fout ("oo.out");
	fout<<maxim<<"\n";
	fout.close();
}

int main ()
{
	Citire();
	Solve();
	return 0;
}