Cod sursa(job #1323091)

Utilizator hrazvanHarsan Razvan hrazvan Data 20 ianuarie 2015 17:26:34
Problema DreptPal Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.66 kb
#include <stdio.h>
#define MAXN 1000
#define MAXM 1000
int rez[MAXN][2 * MAXM + 1];
int v[2 * MAXM + 1], st[2 * MAXM + 1], dr[2 * MAXM + 1];

inline void solve(int lin, int col){
  int i, dr = 0, st = 0, ci, j;
  for(i = 0; i <= col; i++){
    if(i <= dr){
      ci = st + dr - i;
      if(ci - rez[lin][ci] / 2 >= st)
        j = i + rez[lin][ci] / 2 + 1;
      else
        j = dr + 1;
    }
    else
      j = i + 1;
    while(i - (j - i) >= 0 && j <= col && v[j] == v[i - (j - i)])
      j++;
    j--;
    rez[lin][i] = 2 * (j - i) + 1;
    if(dr < j){
      dr = j;
      st = i - (j - i);
    }
  }
}

inline void parcurg(int *cp, int st, int dr, int pas, int col){
  int i, stiv[2 * MAXM + 1], k = 0;
  for(i = st; i != dr + pas; i += pas){
    while(k > 0 && rez[stiv[k - 1]][col] > rez[i][col]){
      cp[stiv[k - 1]] = i;
      k--;
    }
    stiv[k] = i;
    k++;
  }
  while(k > 0){
    cp[stiv[k - 1]] = dr + pas;
    k--;
  }
}

inline int skyline(int n, int col){
  parcurg(dr, 0, n, 1, col);
  parcurg(st, n, 0, -1, col);
  int i, max = 0, x;
  for(i = 0; i < n; i++){
    x = (dr[i] - st[i] - 1) * (rez[i][col] / 2);
    if(x > max)
      max = x;
  }
  return max;
}

int main(){
  FILE *in = fopen("dreptpal.in", "r");
  int n, m, i, j;
  fscanf(in, "%d%d", &n, &m);
  for(i = 0; i < n; i++){
    for(j = 0; j < m; j++){
      fscanf(in, "%d", &v[2 * j + 1]);
    }
    solve(i, 2 * m);
  }
  int max = 0, r;
  for(i = 0; i <= 2 * m; i++){
    r = skyline(n - 1, i);
    if(r > max)
      max = r;
  }
  FILE *out = fopen("dreptpal.out", "w");
  fprintf(out, "%d", max);
  fclose(out);
  return 0;
}