Cod sursa(job #36354)

Utilizator ionescu_bogdanIonescu Bogdan-Gabriel ionescu_bogdan Data 23 martie 2007 14:06:06
Problema Oo Scor 70
Compilator c Status done
Runda Arhiva de probleme Marime 0.84 kb
/* Time Complexity: O(N) */

#include <stdio.h>
#define filein "oo.in"
#define fileout "oo.out"
#define maxn 100010
#define maxim(a,b) ((a>b)?a:b)

long long eggs[maxn];
long long best[maxn], max;

int main()
{
long long i, j, k, N;

freopen(filein, "r", stdin);
scanf("%lld", &N);
for (i = 0; i < N; i++)
  scanf("%lld", &eggs[i]);

max = 0;
if (N == 2)
  max = eggs[0] + eggs[1];
else
  {
    for (k = 0; k < 2; k = (k+1)%N)
      {
        best[k] = 0;
        best[(k+1)%N] = 0;
        best[(k+2)%N] = eggs[(k+1)%N] + eggs[(k+2)%N];
        for (i = (k+3)%N; i!=k; i = (i+1)%N)
          best[i] = maxim(best[(i-1+N)%N], best[(i-3+N)%N] +
                          eggs[(i-1+N)%N] + eggs[i]);


        max = maxim(max, best[(k-1+N)%N]);
      }
  }

freopen(fileout, "w", stdout);
printf("%lld\n", max);

return 0;
}