Pagini recente » Cod sursa (job #1259393) | Cod sursa (job #7970) | Cod sursa (job #2987319) | Cod sursa (job #967418) | Cod sursa (job #2582470)
#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int mat[N][N];
int p[N][N];
void manacher(int v[],int p[],int n){
int c,r=0;
v[0]=-5;
v[n+1]=-10;
for(int i=1;i<=n;i++){
int rad=0;
if(i<=r){
rad=min(p[2*c-i],r-i);
}
while(v[i+rad+1]==v[i-rad-1])
rad++;
p[i]=rad;
if(i+p[i]>r){
c=i;
r=i+p[i];
}
}
}
int stv[N];
int st[N];
int main()
{
FILE*fin,*fout;
fin=fopen("dreptpal.in","r");
fout=fopen("dreptpal.out","w");
int n,m;
fscanf(fin,"%d%d",&n,&m);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
fscanf(fin,"%d",&mat[i][j]);
}
manacher(mat[i],p[i],m);
}
int amax=0;
for(int j=1;j<=m;j++){
int vf=0;
stv[vf]=0;
p[0][j]=-1;
for(int i=1;i<=n;i++){
while(vf>0 && p[stv[vf]][j]>=p[i][j])
vf--;
st[i]=stv[vf];
stv[++vf]=i;
}
vf=0;
stv[vf]=n+1;
p[n+1][j]=-1;
for(int i=n;i>=1;i--){
while(vf>0 && p[stv[vf]][j]>=p[i][j])
vf--;
int dr=stv[vf];
if((dr-st[i]-1)*(2*p[i][j]+1)>amax){
amax=(dr-st[i]-1)*(2*p[i][j]+1);
}
stv[++vf]=i;
}
}
fprintf(fout,"%d",amax);
return 0;
}