Cod sursa(job #479726)

Utilizator eudanipEugenie Daniel Posdarascu eudanip Data 24 august 2010 23:29:15
Problema DreptPal Scor Ascuns
Compilator cpp Status done
Runda Marime 1.87 kb
#include<stdio.h>

#define maxim(a,b) (a>b ? a : b)
#define minim(a,b) (a<b ? a : b)

int n,m,a[1005][1005];
int d[1005][1005],sol;
int sv[1005],sf,l,r;
int rt[1005],lf[1005];

int main ()
{
    int i,j,st,dr,c;
    freopen("dreptpal.in","r",stdin);
    freopen("dreptpal.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            scanf("%d",&a[i][j]);
    for(j=1;j<=n;j++)
    {
        l=r=1;d[j][1]=1;
        for(i=2;i<=m;i++)
            if(i>r)
            {
                d[j][i]=1;st=i-1;dr=i+1;
                while(a[j][st]==a[j][dr] && st && dr<=m)
                {
                    d[j][i]++;
                    st--;
                    dr++;
                }
                l=st+1;r=dr-1;
            }
            else
            {
                c=(l+r)/2;
                if(d[j][2*c-i]<=r-i)
                {
                    d[j][i]=minim(d[j][2*c-i],n-i);
                    continue;
                }
                d[j][i]=r-i+1;
                st=i-d[j][i];dr=i+d[j][i];
                while(a[j][st]==a[j][dr] && st && dr<=m)
                {
                    d[j][i]++;
                    st--;
                    dr++;
                }
                l=st+1;r=dr-1;
            }
    }
    for(j=1;j<=m;j++)
    {
        sv[0]=0;sf=0;
        for(i=1;i<=n;i++)
        {
            while(sf && d[i][j]<=d[sv[sf]][j])
                sf--;
            rt[i]=sv[sf];
            sv[++sf]=i;
        }
        sv[0]=n+1;sf=0;
        for(i=n;i>=1;i--)
        {
            while(sf && d[i][j]<=d[sv[sf]][j])
                sf--;
            lf[i]=sv[sf];
            sv[++sf]=i;
        }
        for(i=1;i<=n;i++)
            sol=maxim(sol,(lf[i]-rt[i]-1)*(2*d[i][j]-1));
    }
    printf("%d\n",sol);
    return 0;
}