Cod sursa(job #949570)

Utilizator OnimushaLordTiberiu Copaciu OnimushaLord Data 14 mai 2013 11:14:40
Problema Oo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 kb
#include<cstdio>
#include<algorithm>
using namespace std;
int a[100010],v[100010];
int n,i,MAX,x,y;
inline void fill()
{
    int i;
    for (i=1;i<=n;i++)
        v[i]=0;
    return;
}
int main()
{
    freopen("oo.in","r",stdin);
    freopen("oo.out","w",stdout);
    scanf("%d\n",&n);
    for (i=1;i<=n;i++)
    {
        scanf("%d",&x);
        a[i]=x+y;
        y=x;
    }
    a[1]+=x;
    x=0;
    fill();

    //fixam sectoarele de pe pozitiile 1 si 2 ca inceput

    v[2]=a[2];
    MAX=max(MAX,a[2]);
    for( i=5;i<=n-1;i++) //putem lua oua de la oricare sector incepand de la 5 pana la n-1
    {
        x=max(v[i-3],v[i-4]);
        if (i>5) x=max(x,v[i-5]);
        v[i]=x+a[i];
        MAX=max(MAX,v[i]);
    }
    fill();

    //fixam sectoarele de pe pozitiile 1 si n ca inceput

    v[1]=a[1];
    MAX=max(MAX,a[1]);
    for (i=4;i<=n-2;i++) //putem lua oua de la oricare sector incepand de la 4 pana la n-2
    {
        x=max(v[i-4],v[i-3]);
        if (i>5) x=max(x,v[i-5]);
        v[i]=x+a[i];
        MAX=max(MAX,v[i]);
    }
    fill();

    //fixam sectoarele de pe pozitiile 2 si 3 ca inceput

    v[3]=a[3];
    MAX=max(MAX,a[3]);
    for (i=6;i<=n;i++) //putem lua oua de la oricare sector incepand de la 6 pana la n
    {
        x=max(v[i-4],v[i-3]);
        if (i>5) x=max(x,v[i-5]);
        v[i]=x+a[i];
        MAX=max(MAX,v[i]);
    }
    printf("%d\n",MAX);
    fclose(stdin);
    fclose(stdout);
    return 0;
}