Pagini recente » Cod sursa (job #1973709) | Cod sursa (job #470811) | Cod sursa (job #2385109) | Cod sursa (job #158523) | Cod sursa (job #3142399)
#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 << max ( a[ 1 ] , a[ 2 ]) << '\n';
return 0;
}
else if ( n == 3 )
{
cout << max ( a [ 1 ], max (a [ 2], a [ 3 ]));
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;
}