Pagini recente » Cod sursa (job #488707) | Cod sursa (job #1302698) | Cod sursa (job #391487) | Cod sursa (job #226168) | Cod sursa (job #637555)
Cod sursa(job #637555)
#include<stdio.h>
#include<assert.h>
#include<string.h>
#include<algorithm>
using namespace std;
int n,m,sol,st1[1002],st2[1002],li[1002],ri[1002],a[1051][1051];
char pars[20000];
short int p[1011][1020];
void read()
{
assert(freopen("dreptpal.in","r",stdin)!=NULL);
scanf("%d%d\n",&n,&m);
int i,j,d=0,u,h;
for(i=1;i<=n;++i)
{
j=1;
gets(pars);
u=strlen(pars);
h=0;
while(h<u)
{
if(pars[h]==' ')
{
a[i][j]=d;
++j;
d=0;
++h;
continue;
}
d*=10;
d+=pars[h]-'0';
++h;
}
a[i][j]=d;
}
/*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;
}
}
inline short int max(short int x, short int y)
{
if(x>y)
return x;
return y;
}
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&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[i][j]=1;
if(last*2-1<=j)
p[i][j]=max(p[i][lc*2-j],1);
st=(j>>1)-((p[i][j]+1)>>1);
dr=(j>>1)+((p[i][j]+1)>>1);
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,aux;
for(i=1;i<=m;++i)
{
aux=i*2-1;
for(j=1;j<=n;++j)
{
while(st1[0] && p[st1[st1[0]]][aux]>=p[j][aux])
{
--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]]][aux]>=p[j][aux])
{
--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][aux]*(ri[j]+li[j]-1));
//printf("%d ",li[j]);
}
//printf("\n");
//for(j=1;j<=n;++j)
//{
// printf("%d ",ri[j]);
// }
//printf("\n\n");
st2[0]=0;
st1[0]=0;
//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;
}