Pagini recente » Cod sursa (job #3239278) | Cod sursa (job #1355086) | Cod sursa (job #2204051) | Cod sursa (job #943866) | Cod sursa (job #637992)
Cod sursa(job #637992)
#include<stdio.h>
#include<assert.h>
#include<string.h>
#include<algorithm>
using namespace std;
int n,m,sol,meniu,st1[1012],st2[1012],li[1012],ri[1012],v[1010];
char pars[30000];
int p[1011][1020];
void do_smen(int x);
void read()
{
assert(freopen("dreptpal.in","r",stdin)!=NULL);
scanf("%d%d\n",&n,&m);
int i,j,u,h;
int d;
for(i=1;i<=n;++i)
{
j=1;
gets(pars);
u=strlen(pars);
h=0;
d=0;
while(h<u)
{
if(pars[h]==' ')
{
v[j]=d;
//assert(v[j]!=0);
++j;
d=0;
++h;
continue;
}
d*=10;
d+=pars[h]-'0';
++h;
}
v[j]=d;
do_smen(i);
}
/*for(i=1;i<=n;++i)
for(j=1;j<=m;++j)
scanf("%d",&a[i][j]);*/
}
/*inline short int maxx(short int x, short int y)
{
if(x>y)
return x;
return y;
}*/
void do_smen(int x)
{
int st,dr,j,last,lc;
for(j=1;j<=m;++j)
{
if(j==1)
{
p[x][j]=1;
lc=1;
last=1;
}
else
{
p[x][j]=1;
if(last>=j)
p[x][j]=max(1,p[x][lc*2-j]);
st=j-(p[x][j]+1)/2;
dr=j+(1+p[x][j])/2;
while(st>0 && dr<=m && v[st]==v[dr])
{
p[x][j]+=2;
++dr;
--st;
}
++st;
--dr;
if(dr>last)
{
lc=j;
last=dr;
}
}
}
}
/*
void do_smen(int x)
{
short int st,dr,j,lim,last,lc;
lim=2*m-1;
for(j=1;j<=lim;++j)
{
if(j==1)
{
p[j][x]=1;
lc=1;
last=1;
}
else
{
if(!(j&1))
{
if(last*2-2<=j)
p[i][j]=p[i][lc*2-j];
st=(j>>1)-(p[i][j]>>1);
dr=(j>>1)+1+(p[i][j]>>1);
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[j][x]=1;
if(last*2-1<=j)
p[j][x]=max(p[lc*2-j][x],1);
st=(j>>1)-((p[j][x]+1)>>1);
dr=(j>>1)+((p[j][x]+1)>>1);
while(st>0 && dr<=m && v[st]==v[dr])
{
p[j][x]+=2;
--st;
++dr;
}
--dr;
++st;
if(dr>last)
{
last=dr;
lc=j;
}
}
}
}
}*/
void solve()
{
int i,j;
for(i=1;i<=m;++i)
{
for(j=1;j<=n;++j)
{
while(st1[0] && p[st1[st1[0]]][i]>=p[j][i])
{
--st1[0];
}
li[j]=j-st1[st1[0]]-1;
st1[++st1[0]]=j;
}
for(j=n;j>0;--j)
{
while(st2[0] && p[st2[st2[0]]][i]>=p[j][i])
{
--st2[0];
}
if(st2[0]==0)
ri[j]=n-j;
else
ri[j]=st2[st2[0]]-j-1;
st2[++st2[0]]=j;
}
for(j=1;j<=n;++j)
sol=max(sol,p[j][i]*(ri[j]+li[j]+1));
st2[0]=0;
st1[0]=0;
}
meniu=sol;
if(meniu<n)
meniu=n;
}
/*void solve()
{
int i,j;
for(i=1;i<=m;++i)
{
for(j=1;j<=n;++j)
{
while(st1[0] && p[st1[st1[0]]][i]<=p[j][i])
st1[0]--;
if(st1[0]==0)
li[j]=j-1;
else
li[j]=j-st1[st1[0]]-1;
st1[++st1[0]]=j;
}
for(j=n;j>0;--j)
{
while(st2[0] && p[st2[st2[0]]][i]<=p[j][i])
st2[0]--;
if(st2[0]==0)
ri[j]=n-j;
else
ri[j]=st2[st2[0]]-j;
st2[++st2[0]]=j;
}
for(j=1;j<=n;++j)
sol=max(sol,p[j][i]*(ri[j]+li[j]+1));
st1[0]=0;
st2[0]=0;
}
meniu=sol;
}*/
void write()
{
assert(freopen("dreptpal.out","w",stdout)!=NULL);
printf("%d",meniu);
}
int main()
{
read();
solve();
write();
return 0;
}