Cod sursa(job #1003523)

Utilizator assa98Andrei Stanciu assa98 Data 30 septembrie 2013 21:05:11
Problema DreptPal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.77 kb
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX_N=1010;


int a[MAX_N][MAX_N];
int d[MAX_N][MAX_N];

int S[MAX_N][MAX_N];
int J[MAX_N][MAX_N];

int n,m;

void extinde(int i,int v[MAX_N],int d[MAX_N]) {
    while(v[i+d[i]+1]==v[i-d[i]-1] && d[i]<i && i+d[i]<m) {
        d[i]++;
    }
}

void pscpld(int v[MAX_N],int d[MAX_N]) {
    int p=0;
    for(int i=1;i<=m;i++) {
        if(p+d[p]<i) {
            extinde(i,v,d);
        }
        else if( (p-(i-p))-d[p-(i-p)]<=p-d[p]) {
            d[i]=d[p]-(i-p);
            extinde(i,v,d);
        }
        else if( (p-(i-p))-d[p-(i-p)]>p-d[p]) {
            d[i]=d[p-(i-p)];
        }

        if(i+d[i]>p+d[p]) {
            p=i;
        }
    }
}

int st[MAX_N];

int main() {
    freopen("dreptpal.in","r",stdin);
    freopen("dreptpal.out","w",stdout);
    
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            scanf("%d",&a[i][j]);
        }
        a[i][0]=-1;
        a[i][m+1]=-2;
        pscpld(a[i],d[i]);
    }

    for(int j=1;j<=m;j++) {
        st[0]=0;
        for(int i=1;i<=n;i++) {
            while(st[0]&&d[st[st[0]]][j]>=d[i][j]) {
                st[0]--;
            }
            S[i][j]=st[st[0]]+1;
            st[++st[0]]=i;
        }
        st[0]=0;
        for(int i=n;i>=1;i--) {
            while(st[0]&&d[st[st[0]]][j]>=d[i][j]) {
                st[0]--;
            }
            
            if(st[0]) {
                J[i][j]=st[st[0]]-1;
            }
            else {
                J[i][j]=n;
            }
            st[++st[0]]=i;
        }
    }
    
    int sol=n;
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            sol=max(sol,(J[i][j]-S[i][j]+1)*(2*d[i][j]+1));
        }
    }
    
    printf("%d",sol);

    return 0;
}