Pagini recente » Cod sursa (job #623968) | Monitorul de evaluare | Cod sursa (job #452287) | Cod sursa (job #394471) | Cod sursa (job #712911)
Cod sursa(job #712911)
#include <cstdio>
#include <fstream>
#include <algorithm>
using namespace std;
#define N 1024
int a[N][N],bst[N][N],n,m,sol,x[N],y[N],z[N];
void read ()
{
ifstream in ("dreptpal.in");
in>>n>>m;
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
in>>a[i][j];
}
void solve ()
{
for(int i=1;i<=n;++i)
{
int lf=1,rt=1;
bst[i][1]=1;
for(int j=2;j<=m;++j)
if(j>rt)
{
bst[i][j]=1;
int ft=j-1,bk=j+1;
for(;a[i][ft]==a[i][bk]&&ft&&bk<=m;++bk)
{
++bst[i][j];
--ft;
}
lf=ft+1;
rt=bk-1;
}
else
{
int mid=(lf+rt)>>1;
if(bst[i][2*mid-j]<=rt-j)
bst[i][j]=min(bst[i][2*mid-j],n-j);
else
{
bst[i][j]=rt-j+1;
int ft=j-bst[i][j],bk=j+bst[i][j];
for(;a[i][ft]==a[i][bk]&&ft&&bk<=m;++bk)
{
++bst[i][j];
--ft;
}
lf=ft+1;
rt=bk-1;
}
}
}
for(int j=1;j<=m;++j)
{
x[0]=0;
int ft=0;
for(int i=1;i<=n;++i)
{
for(;ft&&bst[i][j]<=bst[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&&bst[i][j]<=bst[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)*(2*bst[i][j]-1));
}
}
void out ()
{
freopen ("dreptpal.out","w",stdout);
printf("%d",sol);
}
int main ()
{
read ();
solve ();
out ();
return 0;
}