Pagini recente » Cod sursa (job #1084621) | Cod sursa (job #2104191) | Cod sursa (job #141607) | Cod sursa (job #3145818) | Cod sursa (job #3142397)
#include <fstream>
#include <vector>
using namespace std;
ifstream cin("oo.in");
ofstream cout("oo.out");
long long n ;
int main()
{
cin >> n ;
vector<long long> a ;
vector<long long> v;
a.resize( n + 1);
v.resize( n + 1);
for ( int i = 1; i <= n ; i ++ )
{
cin >> v[ i ];
}
for (int i = 1; i <= n ; i ++ )
{
a [ i ] = v [ i ];
if (i == n )
a [ i ] += v[ 1 ];
else
a [ i ] += v[ i + 1];
}
if ( n == 2 )
{
cout << a[ 1 ] << '\n';
return 0;
}
vector<long long> dp1 ;
dp1.resize( n + 1) ;
dp1 [ 0 ] = 0 ;
dp1 [ 1 ] = 0 ;
dp1 [ 2 ] = 0 ;
vector<long long> dp2 ;
dp2.resize( n + 1 );
dp2[ 0 ] = 0 ;
for ( int i = 3 ; i <= n ; i ++ )
{
long long t = 0 ;
if ( i - 3 > 2 )
t = dp1 [ i - 3 ];
else
t = 0 ;
dp1 [ i ] = max ( a [ i ] + t, dp1 [ i - 1 ] ) ;
//cout << dp1 [ i ] << " " << a[ i ] << " " << t << '\n';
}
for ( int i = 1 ; i < n - 1 ; i ++ )
{
long long t = 0 ;
if ( i <= 2 )
t = 0 ;
else
t = dp2 [ i - 3 ] ;
dp2 [ i ] = max ( a [ i ] + t, dp2 [ i - 1 ]);
}
cout << max ( dp2 [ n - 2 ] ,dp1[ n ] )<< '\n';
return 0;
}