Cod sursa(job #1312529)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 9 ianuarie 2015 17:32:40
Problema DreptPal Scor 90
Compilator c Status done
Runda Arhiva de probleme Marime 1.64 kb
//manarcher's: http://leetcode.com/2011/11/longest-palindromic-substring-part-ii.html
#include <stdio.h>
#define MAXN 1000
int p[MAXN][2*MAXN+2], stiva[MAXN+1], st[MAXN], t[2*MAXN+3];
int max, n, m, k;
FILE *fin;
inline void update(int a){
    if(max<a){
        max=a;
    }
}
inline void manacher(int l){
    int c, r, i, j;
    t[0]=-2;
    m=1;
    for(i=0; i<k; i++){
        t[m++]=-1;
        fscanf(fin, "%d", &t[m++]);
    }
    t[m]=-1;
    t[m+1]=-3;
    c=0;
    r=0;
    for(i=1; i<=m; i++){
        j=2*c-i;
        if(r>i){
            if(p[l][j]<=r-i){
                p[l][i]=p[l][j];
            }else{
                p[l][i]=r-i;
            }
        }
        while(t[i+p[l][i]+1]==t[i-p[l][i]-1]){
            p[l][i]++;
        }
        if(i+p[l][i]>r){
            c=i;
            r=i+p[l][i];
        }
    }
}
inline void skyline(int c){
    int e, i;
    stiva[0]=-1;
    e=1;
    for(i=0; i<n; i++){
        while((e>1)&&(p[stiva[e-1]][c]>=p[i][c])){
            e--;
        }
        st[i]=stiva[e-1];
        stiva[e++]=i;
    }
    stiva[0]=n+1;
    e=1;
    for(i=n-1; i>=0; i--){
        while((e>1)&&(p[stiva[e-1]][c]>=p[i][c])){
            e--;
        }
        update(p[i][c]*(stiva[e-1]-st[i]-1));
        stiva[e++]=i;
    }
}
int main(){
    int i;
    FILE *fout;
    fin=fopen("dreptpal.in", "r");
    fout=fopen("dreptpal.out", "w");
    fscanf(fin, "%d%d ", &n, &k);
    for(i=0; i<n; i++){
        manacher(i);
    }
    for(i=1; i<=m; i++){
        skyline(i);
    }
    fprintf(fout, "%d\n", max);
    fclose(fin);
    fclose(fout);
    return 0;
}