Cod sursa(job #1820505)

Utilizator stoianmihailStoian Mihail stoianmihail Data 1 decembrie 2016 20:23:59
Problema DreptPal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.43 kb
#include <stdio.h>

#define MAX_N 1000

typedef struct {
  int h, end;
} pair;

int N, M;
int s[MAX_N + 1];
short int delta[MAX_N + 1][MAX_N + 1];

int ss;
pair stack[MAX_N + 1];

int MIN(int X, int Y) {
  return X < Y ? X : Y;
}

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

int main(void) {
  int i, j, r, c, h, endPoint, max = 1;
  FILE *f = fopen("dreptpal.in", "r");

  fscanf(f, "%d %d", &N, &M);
  for (i = 1; i <= N; i++) {
    r = c = 0;
    for (j = 1; j <= M; j++) {
      fscanf(f, "%d", &s[j]);
    }
    for (j = 1; j <= M; j++) {
      if (j < r) {
        delta[i][j] = MIN(delta[i][2 * c - j], r - j);
      }
      while (j - delta[i][j] - 1 >= 1 && j + delta[i][j] + 1 <= M && s[j - delta[i][j] - 1] == s[j + delta[i][j] + 1]) {
        delta[i][j]++;
      }
      if (j + delta[i][j] > r) {
        r = j + delta[i][j];
        c = j;
      }
    }
  }

  for (j = 1; j <= M; j++) {
    ss = 1;
    for (i = 1; i <= N + 1; i++) {
      if (i == N + 1) {
        h = 0;
      } else {
        h = (delta[i][j] << 1) + 1;
      }
      endPoint = stack[ss - 1].end;
      while (h < stack[ss - 1].h) {
        max = MAX(max, stack[ss - 1].h * (endPoint - stack[ss - 2].end));
        ss--;
      }
      stack[ss].h = h;
      stack[ss++].end = endPoint + 1;
    }
  }

  freopen("dreptpal.out", "w", stdout);
  fprintf(stdout, "%d\n", max);
  fclose(stdout);
  return 0;
}