Cod sursa(job #40594)

Utilizator mariusdrgdragus marius mariusdrg Data 27 martie 2007 15:40:45
Problema Oo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include<stdio.h>
#include<algorithm>

const int maxn = 200010;

int i;
int last[maxn];
int n;
int j;
int k;
int sum;
int a[maxn];
int din[maxn];
int maxi;

int max(int i, int j)
{
        if (i < j) return j;
        return i;
}


int main()
{
        freopen("oo.in","r",stdin);
        freopen("oo.out","w",stdout);
        scanf("%d",&n);
        for(i = 1;i <= n; ++i)
        {
                scanf("%d",&a[i]);
        }
        for(j = n + 1; j <= n * 2; ++j)
        {
                a[j] = a[j - n];
        }
        for(i = 1;i <= 5; ++i)
        {
                for(j = 1;j <= n - 1; ++j)
                {
                        sum = a[j + i] + a[j + i - 1];
                        din[i + j] = sum;
                        last[i + j] = i + j - 1;
                        for(k = i + j - 3;k  > i + j - 7 && k >= i; --k)
                        {
                                if (last[k] == i && j == n - 1)  continue;
                                din[i + j] = max(din[i + j], din[k] + sum);
                                if (din[i + j] == din[k] + sum) last[i + j] = last[k];
                        }
                        if (din[i + j] > maxi)
                        {
                                maxi = din[i + j];
                        }
                }
                memset(din,0,sizeof(din));

        }


        printf("%d\n",maxi);

        return 0;
}