Cod sursa(job #3142398)

Utilizator xDemonstyMatei Haba Ionut xDemonsty Data 21 iulie 2023 10:05:21
Problema Oo Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.52 kb
#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;
    }
    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;
}