Pagini recente » Cod sursa (job #1932746) | Cod sursa (job #1230974) | Cod sursa (job #402486) | Cod sursa (job #130141) | Cod sursa (job #712926)
Cod sursa(job #712926)
# include <fstream>
# include <iostream>
# define DIM 1003
# define min(a,b) (a<b?a:b)
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 s[DIM], p[DIM], dr, st, q;
for(int j=1;j<=m;++j)
{
st=dr=1;
s[dr]=d[1][j];
p[dr]=1;
for(int i=2;i<=n;++i)
{
q=d[i][j];
while (dr && q<s[dr])--dr;
if (q!=s[dr])s[++dr]=q,p[dr]=i;
if (st>dr)st=dr;
while (st<dr && (i-p[st]+1)*s[st]<(i-p[st+1]+1)*s[st+1])++st;
sol=max((i-p[st]+1)*s[st],sol);
}
}
}
int main ()
{
read ();
solve ();
ofstream fout ("dreptpal.out");
fout<<sol;
return 0;
}