Cod sursa(job #36316)

Utilizator ionescu_bogdanIonescu Bogdan-Gabriel ionescu_bogdan Data 23 martie 2007 13:25:42
Problema Oo Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 0.76 kb
/*
   GREEDY
   Time Complexity: O(N^2)
*/

#include <stdio.h>
#include <string.h>
#define filein "oo.in"
#define fileout "oo.out"
#define maxn 10000

int oo[maxn], blocked[maxn];

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

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

memset(blocked, 0, sizeof(blocked));
sw = 1, max = 0;
while (sw)
  {
    for (sw = best = i = 0; i < N; i++)
      if (!blocked[i] && !blocked[(i+1)%N] && oo[i]+oo[(i+1)%N] > best)
        best = oo[i]+oo[(i+1)%N], j = i, sw = 1;

    if (sw)
      blocked[j] = blocked[(j+1)%N] = blocked[(j+2)%N] = blocked[(j-1+N)%N] = 1,
      max += best;
  }

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

return 0;
}