Cod sursa(job #2044189)

Utilizator TincaMateiTinca Matei TincaMatei Data 20 octombrie 2017 23:57:01
Problema DreptPal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <cstdio>
 
const int MAX_N = 1000;
int matr[MAX_N][MAX_N];
int pal[MAX_N][MAX_N];
 
void manacher(int *v, int *d, int n) {
  int st, dr, cent;
  st = dr = cent = 0;
  for(int i = 1; i < n; ++i) {
    if(i > dr)
      st = cent = dr = i;
    else {
      d[i] = d[2 * cent - i];
      if(i + d[i] >= dr) {
        d[i] = dr - i;
        cent = i;
        st = cent - d[i];
      }
    }
    while(st - 1 >= 0 && dr + 1 < n && v[st - 1] == v[dr + 1]) {
      ++d[cent];
      --st;
      ++dr;
    }
  }
}

int rez;
int top;
int st[MAX_N];
int w[MAX_N];

void baga(int x) {
  int h = 0;
  while(top > 0 && x <= st[top - 1]) {
    h += w[top - 1];
    if(h * st[top - 1] > rez)
      rez = h * st[top - 1];
    --top;
  }
  st[top] = x;
  w[top++] = h + 1;
}

int main() {
  int n, m;
  FILE *fin = fopen("dreptpal.in", "r");
  fscanf(fin, "%d%d", &n, &m);
  for(int l = 0; l < n; ++l) {
    for(int c = 0; c < m; ++c)
      fscanf(fin, "%d", &matr[l][c]);
    manacher(matr[l], pal[l], m);
  }
  fclose(fin);
 
  for(int c = 0; c < m; ++c) {
    top = 0;
    for(int l = 0; l < n; ++l)
      baga(2 * pal[l][c] + 1);
    baga(0);
  }
 
  FILE *fout = fopen("dreptpal.out", "w");
  fprintf(fout, "%d", rez);
  fclose(fout);
  return 0;
}