Cod sursa(job #636761)

Utilizator sodamngoodSo Damn Good sodamngood Data 19 noiembrie 2011 23:24:59
Problema DreptPal Scor 100
Compilator cpp Status done
Runda .com 2011 Marime 1.71 kb
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
#define maxn 1024

int N, M, sol;
int A[maxn][maxn], D[maxn][maxn];
int V[maxn], ST[maxn], DR[maxn];

void calc_pal(int lin) {
    int i, mxx;
    D[lin][1] = 0; mxx = 1;
    for(i=2; i<=M; i++) {
         if(i < mxx + D[lin][mxx]) {
              D[lin][i] = min(D[lin][mxx - (i - mxx)], mxx + D[lin][mxx] - i);
         }

         if(mxx + D[lin][mxx] <= i + D[lin][i]) {
              mxx = i;
              while(1 <= i - D[lin][i] - 1 && i + D[lin][i] + 1 <= M && A[lin][i + D[lin][i] + 1] == A[lin][i - D[lin][i] - 1]) {
                   D[lin][i]++;
              }
         }
    }
}

int main() {
     FILE *f1=fopen("dreptpal.in", "r"), *f2=fopen("dreptpal.out", "w");
     int i, j, p;

     fscanf(f1, "%d %d\n", &N, &M);
     for(i=1; i<=N; i++) {
          for(j=1; j<=M; j++) {
               fscanf(f1, "%d", &A[i][j]);
          }
     }

     for(i=1; i<=N; i++) {
          calc_pal(i);
     }

     for(i=2; i<M; i++) {
          for(j=1; j<=N; j++) {
               V[j] = D[j][i];
          }

          V[0] = -1; ST[1] = 1;
          for(j=2; j<=N; j++) {
              p = j;
              while(V[j] <= V[p-1]) {
                   p = ST[p-1];
              }
              ST[j] = p;
         }

         V[N+1] = -1; DR[N] = N;
         for(j=N-1; j>=1; j--) {
              p = j;
              while(V[j] <= V[p+1]) {
                   p = DR[p+1];
              }
              DR[j] = p;
         }

         for(j=1; j<=N; j++) {
              sol = max(sol, (2*V[j] + 1)*(DR[j] - ST[j] + 1));
         }

     }

     fprintf(f2, "%d\n", sol);

     fclose(f1); fclose(f2);
     return 0;
}