Cod sursa(job #2000267)

Utilizator DavidLDavid Lauran DavidL Data 13 iulie 2017 11:43:16
Problema Oo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <cstdio>
#include <cstring>
#include <fstream>
#define MAX 100005
using namespace std;

int n,x[MAX];

int solve(int minim,int maxim)
{
    int dp[MAX]; ///dp[i]=s-a cules maxim pana la gaina i (nu sunt gaini culese mai in dreapta)
    memset(dp,0,sizeof(dp));
    dp[minim+1]=x[minim]+x[minim+1];
    for (int i=minim+2; i<=maxim; i++)
        dp[i]=max(dp[i-1],dp[i-3]+x[i-1]+x[i]);
    return dp[maxim];
}

int main()
{
    freopen("oo.in","r",stdin);
    freopen("oo.out","w",stdout);
    scanf("%d",&n);
    for (int i=1; i<=n; i++)
        scanf("%d",&x[i]);
    ///facem vectorul sa para circular
    x[0]=x[n];
    x[n+1]=x[1];

    int rez=0;
    rez=max(rez,solve(1,n-1)); ///daca incepem culegerea cu prima gaina, atunci e speriata a n-a
    rez=max(rez,solve(2,n)); ///daca incepem cu a doua, atunci e speriata doar prima
    rez=max(rez,solve(3,n+1)); ///daca incepem cu a treia, atunci e speriata a doua
    ///daca incepem cu una mai mare, atunci a 2a nu e speriata, deci putem incepe si cu prima
    printf("%d",rez);
    return 0;
}