Pagini recente » Cod sursa (job #2955487) | Cod sursa (job #1518529) | Cod sursa (job #2773313) | Cod sursa (job #51630) | Cod sursa (job #712951)
Cod sursa(job #712951)
# include <fstream>
# include <iostream>
# define DIM 1003
using namespace std;
int n, m, a[DIM][DIM], d[DIM][DIM], sol;
void read ()
{
ifstream fin ("dreptpal.in");
fin>>n>>m;
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
fin>>a[i][j];
}
void solve ()
{
int crt, center, last;
for(int i=1;i<=n;++i)
{
d[i][1]=1;
last=1;
center=1;
for(int j=2;j<=m;++j)
{
crt=0;
if (last<=j)
d[i][j]=1;
else
{
d[i][j]=min(d[i][center-(j-center)],2*(last-j)+1);
crt=d[i][j]/2;
}
while (j-(crt+1)>0 && j+(crt+1)<=m && a[i][j-(crt+1)]==a[i][j+(crt+1)])
++crt, d[i][j]+=2;
if (j+crt>last)
{
last=j+crt;
center=j;
}
}
}
int x[DIM], y[DIM], z[DIM];
for(int j=1;j<=m;++j)
{
x[0]=0;
int ft=0;
for(int i=1;i<=n;++i)
{
for(;ft&&d[i][j]<=d[x[ft]][j];--ft);
y[i]=x[ft];
x[++ft]=i;
}
x[0]=n+1;
ft=0;
for(int i=n;i;--i)
{
for(;ft&&d[i][j]<=d[x[ft]][j];--ft);
z[i]=x[ft];
x[++ft]=i;
}
for(int i=1;i<=n;++i)
sol=max(sol,(z[i]-y[i]-1)*(d[i][j]));
}
/*
int v[DIM], s[DIM], dr;
for(int j=1;j<=m;++j)
{
dr=1;
s[dr]=1;
v[1]=1;
for(int i=2;i<=n;++i)
{
while (dr && d[i][j]<d[s[dr]][j])--dr;
if (d[s[dr]][j]!=d[i][j])s[++dr]=i;
v[i]=i-s[dr]+1;
}
dr=n;
s[dr]=n;
for(int i=n;i;--i)
{
while (dr && d[i][j]<d[s[dr]][j])--dr;
if (d[s[dr]][j]!=d[i][j])s[++dr]=i;
v[i]+=s[dr]-i;
sol=max(sol,v[i]*d[i][j]);
}
}*/
}
int main ()
{
read ();
solve ();
ofstream fout ("dreptpal.out");
fout<<sol;
return 0;
}