Cod sursa(job #32903)

Utilizator vlad_popaVlad Popa vlad_popa Data 18 martie 2007 18:03:33
Problema Oo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <cstdio>

#define FIN "oo.in"
#define FOUT "oo.out"
#define NMAX 100001

int s1[NMAX], s2[NMAX], s3[NMAX], v[NMAX], N;

void read ()
{
  freopen (FIN, "rt", stdin);
  freopen (FOUT, "wt", stdout);

  scanf ("%d", &N);
  for (int i = 1; i <= N; ++ i)
    scanf ("%d", &v[i]);
}

void solve ()
{
  int val, max = 0;
  
  s1[2] = v[1] + v[2];
  s1[3] = s1[4] = s1[2];

  for (int i = 5; i <= N; ++ i)
   {
     s1[i] = s1[i - 1];
     val = v[i] + v[i-1];
     s1[i] = s1[i] > val + s1[i-3] ? s1[i] : val + s1[i-3];
     s1[i] = s1[i] > val + s1[i-4] ? s1[i] : val + s1[i-4];
     s1[i] = s1[i] > val + s1[i-5] ? s1[i] : val + s1[i-5];
   }

  max = s1[N-1];

  s2[3] = v[2] + v[3];
  s2[4] = s2[5] = s2[3];

  for (int i = 6; i <= N; ++ i)
   {
     s2[i] = s2[i-1];
     val = v[i] + v[i-1];
     s2[i] = s2[i] > val + s2[i-3] ? s2[i] : val + s2[i-3];
     s2[i] = s2[i] > val + s2[i-4] ? s2[i] : val + s2[i-4];
     s2[i] = s2[i] > val + s2[i-5] ? s2[i] : val + s2[i-5];
   }

  max = max > s2[N] ? max : s2[N];

  s3[1] = v[1] + v[N];
  s3[2] = s3[3] = s3[1];

  for (int i = 4; i <= N-2; ++ i)
   {
     s3[i] = s3[i-1];
     val = v[i] + v[i-1];
     s3[i] = s3[i] > val + s3[i-3] ? s3[i] : val + s3[i-3];
     s3[i] = s3[i] > val + s3[i-4] ? s3[i] : val + s3[i-4];
     s3[i] = s3[i] > val + s3[i-5] ? s3[i] : val + s3[i-5];
   }

  max = max > s3[N-2] ? max : s3[N-2];

  printf ("%d\n", max);
}

int
 main ()
{
  read ();
  solve ();
  return 0;
}