Pagini recente » Cod sursa (job #252765) | Cod sursa (job #160351) | Cod sursa (job #3156021) | Cod sursa (job #3208813) | Cod sursa (job #479726)
Cod sursa(job #479726)
#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;
}