Cod sursa(job #479651)

Utilizator eudanipEugenie Daniel Posdarascu eudanip Data 24 august 2010 18:22:49
Problema DreptPal Scor Ascuns
Compilator cpp Status done
Runda Marime 1.16 kb
#include<stdio.h>

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

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

int main ()
{
    int i,j,st,dr;
    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(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            for(st=j-1,dr=j+1;st>0 && dr<=m;st-- && dr++)
                if(a[i][st]==a[i][dr])
                    d[i][j]++;
                else
                    break;
    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;
}