Cod sursa(job #1558673)

Utilizator stoianmihailStoian Mihail stoianmihail Data 29 decembrie 2015 14:48:14
Problema Oo Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <stdio.h>

#define Nadejde 100001

int N;
int v[Nadejde];
int d1[Nadejde];
int d2[Nadejde];
int d3[Nadejde];

int max(int X, int Y) {
  return X > Y ? X : Y;
}

int MAX(int X, int Y, int Z) {
  return max(max(X, Y), Z);
}

int dynamic() {
  int i;

  d1[2] = v[1] + v[2];
  for (i = 5; i < N; i++) {
    d1[i] = v[i] + v[i - 1]+ MAX(d1[i - 3], d1[i - 4], d1[i - 5]);
  }

  d2[1] = v[1] + v[N];
  d2[4] = v[4] + v[3] + d2[1];
  for (i = 5; i < N - 1; i++) {
    d2[i] = v[i] + v[i - 1] + MAX(d2[i - 3], d2[i - 4], d2[i - 5]);
  }

  d3[N] = v[N] + v[N - 1];
  d3[3] = v[3] + v[2] + d3[N];
  d3[4] = v[4] + v[3] + d3[N];
  for (i = 5; i < N - 2; i++) {
    d3[i] = v[i] + v[i - 1] + MAX(d3[i - 3], d3[i - 4], d3[i - 5]);
  }

  int s1 = MAX(d1[N - 1], d1[N - 2], d1[N - 3]);
  int s2 = MAX(d2[N - 2], d2[N - 3], d2[N - 4]);
  int s3 = MAX(d3[N - 3], d3[N - 4], d3[N - 5]);
  return MAX(s1, s2, s3);
}

int main(void) {
  int i;
  FILE *f = fopen("oo.in", "r");

  /* Citirea datelor. */
  fscanf(f, "%d", &N);
  for (i = 1; i <= N; i++) {
    fscanf(f, "%d", &v[i]);
  }
  fclose(f);

  /* Calcularea solutiei si afisarea ei. */
  freopen("oo.out", "w", stdout);
  fprintf(stdout, "%d\n", dynamic());
  fclose(stdout);

  /// Multumim Doamne!
  puts("Doamne ajuta!");
  return 0;
}