Cod sursa(job #840615)

Utilizator mirceadinoMircea Popoveniuc mirceadino Data 22 decembrie 2012 22:13:40
Problema Oo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.42 kb
#include<cstdio>
#include<algorithm>
#define NMAX 100010
using namespace std;
int n,i,x,a,b,s[NMAX],v1[NMAX],v2[NMAX],v3[NMAX],solmax;
int main()
{
    freopen("oo.in","r",stdin);
    freopen("oo.out","w",stdout);
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%d",&a);
        s[i]=a+b; //s[i] = sectorul i + sectorul i-1
        b=a;
    }
    s[1]+=a;
    v1[1]=s[1]; //avem sectoarele n si 1 selectate => nu putem selecta 1-2, 2-3 si n-2 - n-1, n-1 - n
    solmax=max(solmax,v1[1]);
    for(i=4;i<=n-2;i++) //incepem de la 3-4 si mergem pana la n-3 - n-2
    {
        x=max(v1[i-3],v1[i-4]);
        if(i>5) x=max(x,v1[i-5]);
        v1[i]=x+s[i];
        solmax=max(solmax,v1[i]);
    }
    v2[2]=s[2]; //avem sectoarele 1 si 2 selectate => nu putem selecta 2-3, 3-4 si n-1 - n, n-1
    solmax=max(solmax,v2[2]);
    for(i=5;i<=n-1;i++) //incepem de la 4-5 si mergem pana la n-2 - n-1
    {
        x=max(v2[i-3],v2[i-4]);
        if(i>5) x=max(x,v2[i-5]);
        v2[i]=x+s[i];
        solmax=max(solmax,v2[i]);
    }
    v3[3]=s[3]; //avem sectoarele 2 si 3 selectate => nu putem selecta 3-4, 4-5 si n-1, 1-2
    solmax=max(solmax,v3[3]);
    for(i=6;i<=n;i++) //incepem de la 5-6 si mergem pana la n-1 - n
    {
        x=max(v3[i-3],v3[i-4]);
        if(i>5) x=max(x,v3[i-5]);
        v3[i]=x+s[i];
        solmax=max(solmax,v3[i]);
    }
    printf("%d",solmax);
    return 0;
}