Cod sursa(job #2490988)

Utilizator Vlad_NituNitu Vlad-Petru Vlad_Nitu Data 11 noiembrie 2019 16:43:27
Problema Oo Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <bits/stdc++.h>
#define NMAX 100005
using namespace std;
ifstream f("oo.in");
ofstream g ("oo.out") ;
int N , dp[NMAX] , a[NMAX] , Max = -1;
int main()
{
    f >> N ;
    for (int i = 1 ; i <= N ; ++i) f >> a[i];
    //caz1 : iau de pe 1 si 2
    dp[1] = dp[N] = 0 ;
    dp[2] = a[1] + a[2] ;
    dp[3] = dp[4] = 0;
    for (int i = 5 ; i <= N ; ++i) {dp[i] = max(dp[i-1] , a[i-1] + a[i] + dp[i-3]) ;
    Max = max(Max,dp[i]) ;}

    //caz 2 : iau pe 1 si N
    dp[1] = a[N] + a[1] ;
    dp[2] = dp[3] = 0 ;
    dp[N-1]=dp[N]=0;
    for (int i = 4 ; i <= N-1 ; ++i)
        {dp[i] = max(dp[i-1] , a[i-1] + a[i] + dp[i-3]) ;
    Max = max(Max,dp[i]) ;}

    //caz 3 : iau pe 2 si 3
    dp[3] = a[2] + a[3] ;
    dp[2] = dp[1] = 0;
    dp[4] = dp[5] = 0;
    for (int i = 6 ; i <= N + 1 ; ++i)
        {dp[i] = max(dp[i-1] , a[i-1] + a[i] + dp[i-3]) ;
    Max = max(Max,dp[i]) ;}
    g << Max << '\n';
}