Pagini recente » Cod sursa (job #38129) | Cod sursa (job #2493299) | Cod sursa (job #545854) | Cod sursa (job #168750) | Cod sursa (job #1212820)
#include <cstdio>
#include <algorithm>
#define Nmax 1005
using namespace std;
int N,M,a[Nmax][Nmax],Z[Nmax][Nmax],sol,l[Nmax],r[Nmax],st[Nmax];
inline void Manacher(int lin)
{
int L,Mij,R=0,i,t;
Z[lin][1]=0;
for(i=2;i<=M;++i)
if(i>R)
{
Mij=i;
for(R=i+1;R<=M && a[lin][R]==a[lin][2*Mij-R];++R);
--R;
Z[lin][i]=R-Mij;
}
else
{
t=2*Mij-i; L=2*Mij-R;
if(Z[lin][t]<t-L)
Z[lin][i]=Z[lin][t];
else
{
Mij=i;
for(++R;R<=M && a[lin][R]==a[lin][2*Mij-R];++R);
--R;
Z[lin][i]=R-Mij;
}
}
}
inline void Stiva(int col)
{
int top=0,i;
for(i=1;i<=N;++i)
r[i]=l[i]=0;
for(i=1;i<=N;++i)
{
while(top && Z[st[top]][col]>Z[i][col])
{
r[st[top]]=i;
--top;
}
st[++top]=i;
}
for(i=1;i<=N;++i)
if(!r[i])
r[i]=N+1;
top=0;
for(i=N;i;--i)
{
while(top && Z[st[top]][col]>Z[i][col])
{
l[st[top]]=i;
--top;
}
st[++top]=i;
}
}
int main()
{
int i,j;
freopen ("dreptpal.in","r",stdin);
freopen ("dreptpal.out","w",stdout);
scanf("%d%d", &N,&M);
for(i=1;i<=N;++i)
for(j=1;j<=M;++j)
scanf("%d", &a[i][j]);
for(i=1;i<=N;++i)
Manacher(i);
sol=M;
for(i=2;i<=M;++i)
{
Stiva(i);
for(j=1;j<=N;++j)
sol=max(sol,(r[j]-l[j]-1)*(2*Z[j][i]+1));
}
printf("%d\n", sol);
return 0;
}