Pagini recente » Cod sursa (job #2901992) | Cod sursa (job #2455956) | Cod sursa (job #1383115) | Cod sursa (job #1326534) | Cod sursa (job #637484)
Cod sursa(job #637484)
#include<stdio.h>
#include<assert.h>
#include<algorithm>
using namespace std;
int n,m,sol,st1[1002],st2[1002],li[1002],ri[1002],p[1011][1020],a[1051][1051];
void read()
{
assert(freopen("dreptpal.in","r",stdin)!=NULL);
scanf("%d%d",&n,&m);
int i,j;
for(i=1;i<=n;++i)
for(j=1;j<=m;++j)
scanf("%d",&a[i][j]);
for(i=1;i<=n;++i)
{
a[i][0]=2000000000;
a[i][m+1]=2000000001;
}
}
void do_smen()
{
int st,dr,i,j,lim,last,lc;
lim=2*m-1;
for(i=1;i<=n;++i)
{
for(j=1;j<=lim;++j)
{
if(j==1)
{
p[i][j]=1;
lc=1;
last=1;
}
else
{
if(j%2==0)
{
if(last*2-2<=j)
p[i][j]=p[i][lc*2-j];
st=j/2-p[i][j]/2;
dr=j/2+1+p[i][j]/2;
while(st>0 && dr<=m && a[i][st]==a[i][dr])
{
p[i][j]+=2;
st--;
dr++;
}
st++;
dr--;
if(dr>last)
{
last=dr;
lc=j;
}
}
else
{
p[i][j]=1;
if(last*2-1<=j)
p[i][j]=max(p[i][lc*2-j],1);
st=j/2-(p[i][j]+1)/2;
dr=j/2+(p[i][j]+1)/2;
while(st>0 && dr<=m && a[i][st]==a[i][dr])
{
p[i][j]+=2;
st--;
dr++;
}
dr--;
st++;
if(dr>last)
{
last=dr;
lc=j;
}
}
}
}
}
}
void solve()
{
do_smen();
//printf("\n");
int i,j;
for(i=1;i<=m;++i)
{
for(j=1;j<=n;++j)
{
while(st1[0] && p[st1[st1[0]]][i*2-1]>=p[j][i*2-1])
{
st1[st1[0]]=0;
--st1[0];
}
li[j]=j-st1[st1[0]];
st1[++st1[0]]=j;
}
for(j=n;j>0;--j)
{
while(st2[0] && p[st2[st2[0]]][i*2-1]>=p[j][i*2-1])
{
st2[st2[0]]=0;
--st2[0];
}
if(st2[0]==0)
ri[j]=n-j+1;
else
ri[j]=st2[st2[0]]-j;
st2[++st2[0]]=j;
}
for(j=1;j<=n;++j)
{
sol=max(sol,p[j][i*2-1]*(ri[j]+li[j]-1));
//printf("%d ",li[j]);
}
//printf("\n");
//for(j=1;j<=n;++j)
//{
// printf("%d ",ri[j]);
// }
//printf("\n\n");
while(st2[0])
{
st2[st2[0]]=0;
--st2[0];
}
while(st1[0])
{
st1[st1[0]]=0;
--st1[0];
}
}
}
void write()
{
assert(freopen("dreptpal.out","w",stdout)!=NULL);
printf("%d",sol);
}
int main()
{
//assert(freopen("dreptpal.out","w",stdout)!=NULL);
read();
solve();
write();
return 0;
}