Cod sursa(job #3142413)

Utilizator xDemonstyMatei Haba Ionut xDemonsty Data 21 iulie 2023 10:28:00
Problema Oo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.66 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];
    }


    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  ]);
    }

    vector<long long> dp3;
    dp3.resize(n+1);
    dp3 [ 0 ] = 0 ;
    dp3 [ 1 ] = 0 ;
    dp3 [ 2 ] = 0 ;
    for ( int i = 2 ; i < n ; i ++ )
    {
        long long t = 0 ;
        if ( i <= 2 )
            t = 0 ;
        else
            t = dp3 [ i - 3 ];
        dp3 [ i ] = max ( a [ i ] + t, dp3 [ i - 1 ]) ;
    }

    cout << max ( dp2 [ n - 2 ],max(dp1[ n ],dp3[ n-1 ]) )<< '\n';


    return 0;
}