Cod sursa(job #2241491)

Utilizator ardutgamerAndrei Bancila ardutgamer Data 16 septembrie 2018 09:11:54
Problema Oo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <cstdio>
#include <algorithm>

using namespace std;

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

int main()
{
    freopen("oo.in","r",stdin);
    freopen("oo.out","w",stdout);
    scanf("%d",&n);
    int ma = -INF;
    for(int i = 1 ; i <= n ; i++)
        scanf("%d",&v[i]);
    /// cazul 1 - luam 1 si 2
    dp[1] = v[1];
    dp[2] = v[1]+v[2];
    for(int i = 3 ; i < n ; i++)
        dp[i] = max(dp[i-1],dp[i-3]+v[i-1]+v[i]);
    ma = max(ma,dp[n-1]);
    /// cazul 2 - luma n si 1
    dp[1] = v[n]+v[1];
    dp[2] = v[n]+v[1];
    for(int i = 2 ; i < n-1 ; i++)
        dp[i] = max(dp[i-1],dp[i-3]+v[i-1]+v[i]);
    ma = max(ma,dp[n-2]);
    ///cazul 3 - nu o luam pe prima
    dp[1] = 0;
    dp[2] = v[2];
    dp[3] = v[2]+v[3];
    for(int i = 4; i <= n ; i++)
        dp[i] = max(dp[i-1],dp[i-3]+v[i-1]+v[i]);
    ma = max(ma,dp[n]);

    printf("%d",ma);
    return 0;
}