Pagini recente » Cod sursa (job #82448) | Cod sursa (job #2447466) | Cod sursa (job #3126779) | Cod sursa (job #1276083) | Cod sursa (job #637412)
Cod sursa(job #637412)
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int lung[101010];
int v[101010],N,st,dr,q;
int mat[1010][1010];
int globj;
int make_pal()
{
for(int i=1;i<=N;++i)
lung[i]=0;
lung[1]=0;
st=1;
dr=1;
for(int i=2;i<=N;++i)
{
// printf("%d",v[i]);
if(i<=dr)
{
int q=st+dr-i;
lung[i]=min(lung[q],dr-i);
if(i+lung[i]==dr)
{
st=i-lung[i];
dr=i+lung[i];
while(dr<N&&st>1&&v[i-lung[i]-1]==v[i+lung[i]+1])
{
++lung[i];
--st;
++dr;
}
}
}
else
{
st=dr=i;
lung[i]=0;
while(st>1&&dr<N&&v[i-lung[i]-1]==v[i+lung[i]+1])
{
--st;
++dr;
++lung[i];
}
}
}
for(int i=1;i<=N;++i)
{
mat[i][globj]=lung[i];
}
//printf("\n");
}
int stiv[1010];
int nrs[1010];
int k=0;
int rez=0;
int M;
int main()
{
freopen("dreptpal.in","r",stdin);
freopen("dreptpal.out","w",stdout);
scanf("%d%d",&M,&N);
for(int j=1;j<=M;++j)
{globj=j;
for(int i=1;i<=N;++i)
{
scanf("%d",&v[i]);
}
make_pal();
}
for(int i=1;i<=N;++i)
{
k=0;
for(int j=1;j<=M;++j)
{int number=0;
while(stiv[k]>=mat[i][j]&&k!=0)
{
number+=nrs[k];
rez=max(rez,(stiv[k]*2+1)*number);
--k;
}
stiv[++k]=mat[i][j];
nrs[k]=number+1;
}
//printf("\n");
}
printf("%d\n",rez);
}