Cod sursa(job #855313)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 14 ianuarie 2013 21:08:20
Problema Oo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <fstream>

using namespace std;

int v[100100];

int maxim(int a,int b)
{
	if(a>b)
		return a;
	return b;
}

int dinamica(int *v,int n)
{
	//cout<<v[0]<<' '<<v[n-1]<<endl;
	//cout<<n<<endl;
	int i;
	//sa pun conditii la n mic
	if(n<2)return 0;
	if(n==3)return (maxim(v[n-3],v[n-1])+v[n-2]);
	
	
	int m[100100];
	m[n-1]=0;
	//cout<<"m["<<n-1<<"]=0"<<endl;
	//cout<<m[n-1]<<endl;
	m[n-2]=v[n-1]+v[n-2];
	//cout<<"m["<<n-2<<"v["<<n-1<<"+"<<"v["<<n-2<<"]"<<endl;
	
	m[n-3]=maxim(v[n-3],v[n-1])+v[n-2];
	
	for(i=n-4;i>=0;i--)
		m[i]=maxim(m[i+1],m[i+3]+v[i]+v[i+1]);
	
	return m[0];
}

int main()
{
	ifstream fin("oo.in");
	ofstream fout("oo.out");
	
	int n,i,solutie=0,x;
	fin>>n;
	
	for(i=0;i<n;i++)
	{
		fin>>v[i];
	}
	
	x=dinamica(v+3,n-4)+v[0]+v[1];
	if(x>solutie)
		solutie=x;
	
	x=dinamica(v+2,n-4)+v[0]+v[n-1];
	if(x>solutie)
		solutie=x;
	
	x=dinamica(v+1,n-4)+v[n-1]+v[n-2];
	if(x>solutie)
		solutie=x;
	
	x=dinamica(v+1,n-2);
	if(x>solutie)
		solutie=x;
	
	fout<<solutie<<endl;
	
	fin.close();
	fout.close();
	
	return 0;
}