Cod sursa(job #2241490)

Utilizator ardutgamerAndrei Bancila ardutgamer Data 16 septembrie 2018 08:50:22
Problema Oo Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <cstdio>
#include <algorithm>

using namespace std;

const int INF = 2000000005;
const int NMAX = 100005;
int dp[NMAX][3];
int v[NMAX];
int n;

inline void INIT()
{
    for(int i = 1 ; i <= n ; i++)
        dp[i][0] = dp[i][1] = -INF;
}

int main()
{
    freopen("oo.in","r",stdin);
    freopen("oo.out","w",stdout);
    scanf("%d",&n);
    int a,b;
    for(int i = 1 ; i <= n ; i++)
        scanf("%d",&v[i]);
    ///cazul 1 in care NU il luam pe 1
    INIT();
    dp[1][0] = 0;
    dp[1][1] = -INF;
    for(int i = 2 ; i <= n ; i++)
    {
        dp[i][0] = max(dp[i-1][0],dp[i-1][1]);
        if(i == 2)
            dp[i][1] = dp[n][0]+v[i]+v[i-1];
        else
            dp[i][1] = dp[i-2][0]+v[i]+v[i-1];
    }
    a = max(dp[n][1],dp[n][0]);

    ///cazul 2 in care il luam pe 1
    INIT();
    dp[1][0] = -INF;
    dp[1][1] = 0;
    for(int i = 2 ; i <= n ; i++)
    {
        dp[i][0] = max(dp[i-1][0],dp[i-1][1]);
        if(i == 2)
            dp[i][1] = dp[n][0]+v[i]+v[i-1];
        else
            dp[i][1] = dp[i-2][0]+v[i]+v[i-1];
    }
    b = max(dp[n][1],dp[n][0]);

    printf("%d\n",max(a,b));
    return 0;
}