Cod sursa(job #867574)

Utilizator thesilverhand13FII Florea Toma Eduard thesilverhand13 Data 29 ianuarie 2013 20:51:47
Problema Oo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
 # include <fstream>
 # include <cstring>
 # include <algorithm>
 # include <vector>
 # include <iostream>
 
 # define dim 100005
 
 using namespace std;
 
 ifstream f("oo.in");
 ofstream g("oo.out");
 
 int A[ dim ], dp[ dim ];
 int N, sol = 0;
 
 void citire()
 {
	 int i;
	 f >> N;
	 for ( i = 1 ; i <= N ; i++ )
		 f >> A[ i ];
	  A[ N + 1 ] = A[ 1 ];
 }
 void rezolva( int stanga, int dreapta )
 {
	 int i;
	 dp[ stanga ] = 0;
	 dp[ stanga + 1 ] = A[ stanga ] + A[ stanga + 1 ]; 
	 
	 for ( i = stanga + 2 ; i <= dreapta ; i++ )
		 dp[ i ] = max( dp[ i - 1 ] ,dp[ max( 0, i - 3 ) ] + A[ i ] + A[ i - 1 ] );
	// for ( i = 1 ; i <= N ; i++ )
		// cout << dp[ i ] << " ";
	 
	 if ( sol < dp[ dreapta ] )
		 sol = dp[ dreapta ];
	 
	 
 }
 
 int main()
 {
	 citire();
	 rezolva( 1, N - 1 );
	 rezolva( 2, N );
	 rezolva( 3, N  + 1 );
	 g << sol;
	 return 0;
 }