Cod sursa(job #597518)

Utilizator scipianusFMI Ciprian Olariu scipianus Data 22 iunie 2011 14:50:36
Problema Oo Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.5 kb
#include<fstream>
using namespace std;
int n,v[100010];
int a[100010],b[100010],c[100010],d[100010];
int main()
{
	int i,maxim=-2000000000;
	ifstream fin("oo.in");
	fin>>n;
	for(i=1;i<=n;i++)
		fin>>v[i];
	fin.close();
	if(n==2)
		maxim=v[1]+v[2];
	else
		if(n==3)
			maxim=max(v[1]+v[2],max(v[1]+v[3],v[2]+v[3]));
		else
			if(n==4)
				maxim=max(v[1]+v[2],max(v[1]+v[4],max(v[2]+v[3],v[3]+v[4])));
			else
				if(n==5)
					maxim=max(v[1]+v[2],max(v[1]+v[5],max(v[2]+v[3],max(v[3]+v[4],v[4]+v[5]))));
				else
				{
					// Cazul I
					a[1]=0;
					a[2]=v[1]+v[2];
					a[3]=0;
					maxim=max(maxim,a[2]);
					for(i=4;i<n;i++)
					{
						a[i]=v[i]+v[i-1]+max(a[i-3],a[i-4]);
						maxim=max(maxim,a[i]);
					}
					// Cazul II
					b[1]=v[n]+v[1];
					b[2]=0;
					b[3]=0;
					maxim=max(maxim,b[1]);
					for(i=4;i<n-1;i++)
					{
						b[i]=v[i]+v[i-1]+max(b[i-3],b[i-4]);
						maxim=max(maxim,b[i]);
					}
					// Cazul III
					c[0]=v[n-1]+v[n];
					c[1]=0;
					c[2]=0;
					c[3]=c[0]+v[2]+v[3];
					maxim=max(maxim,c[3]);
					for(i=4;i<n-2;i++)
					{
						c[i]=v[i]+v[i-1]+max(c[i-3],c[i-4]);
						maxim=max(maxim,c[i]);
					}
					// Cazul IV
					d[1]=0;
					d[2]=0;
					d[3]=v[2]+v[3];
					d[4]=0;
					d[5]=0;
					maxim=max(maxim,d[3]);
					for(i=6;i<=n;i++)
					{
						d[i]=v[i]+v[i-1]+max(d[i-3],d[i-4]);
						maxim=max(maxim,d[i]);
					}
				}
	ofstream fout("oo.out");
	fout<<maxim<<"\n";
	fout.close();
	return 0;
}