Pagini recente » Cod sursa (job #2214890) | Cod sursa (job #372803) | Cod sursa (job #1060302) | Cod sursa (job #1228068) | Cod sursa (job #637416)
Cod sursa(job #637416)
Utilizator |
L Greg Lgreg |
Data |
20 noiembrie 2011 14:21:20 |
Problema |
DreptPal |
Scor |
100 |
Compilator |
cpp |
Status |
done |
Runda |
.com 2011 |
Marime |
1.87 kb |
#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+1;++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);
}