Cod sursa(job #1005702)

Utilizator thewildnathNathan Wildenberg thewildnath Data 5 octombrie 2013 15:52:55
Problema DreptPal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 kb
#include<stdio.h>

int n,m,v[1002][1002],a[1002][1002],s[1002];
int x[1002][1002],y[1002][1002];

void ext(int i,int j)
{
    while(v[j-a[i][j]-1]==v[j+a[i][j]+1]&&a[i][j]<j)
        ++a[i][j];
}

inline int max(int a,int b)
{
    return a>b?a:b;
}

int main()
{
    freopen("dreptpal.in","r",stdin);
    freopen("dreptpal.out","w",stdout);
    int i,j,l,sol=0;
    scanf("%d%d",&n,&m);
    // PSCPLD
    for(i=1;i<=n;++i)
    {
        for(j=1;j<=n;++j)
            scanf("%d",&v[j]);
        v[i][0]=-1;
        v[i][m+1]=-1;
        /////////////////
        l=0;
        for(j=1;j<=m;++j)
        {
            if(l+a[i][l]<j)
                ext(i,j);
            else if(l-a[i][l]>=2*l-j-a[i][2*l-j])
            {
                a[i][j]=a[i][l]-j+l;
                ext(i,j);
            }
            else
                a[i][j]=a[i][2*l-j];
            if(j+a[i][j]>l+a[i][l])
                l=j;
        }
    }
    //////////////////////////////////
    for(j=1;j<=m;++j)
    {
        s[0]=0;
        for(i=1;i<=n;++i)
        {
            while(s[0]&&a[s[s[0]]][j]>=a[i][j])
                --s[0];
            x[i][j]=s[s[0]]+1;
            s[++s[0]]=i;
        }
        s[0]=0;
        for(i=n;i>=1;--i)
        {
            while(s[0]&&a[s[s[0]]][j]>=a[i][j])
                --s[0];
            if(s[0])
                y[i][j]=s[s[0]]-1;
            else
                y[i][j]=n;
            s[++s[0]]=i;
        }
    }
    for(i=1;i<=n;++i)
        for(j=1;j<=m;++j)
            sol=max(sol,(y[i][j]-x[i][j]+1)*(2*a[i][j]+1));
    printf("%d\n",sol);
    return 0;
}