Pagini recente » Cod sursa (job #2239602) | Cod sursa (job #1833707) | Cod sursa (job #1390611) | Cod sursa (job #468365) | Cod sursa (job #635384)
Cod sursa(job #635384)
#include <cstdio>
#define nmax 1010
int n, m, v[nmax][nmax], a[nmax][nmax], len[nmax], s[nmax], sol, right[nmax], left[nmax];
int min(int a, int b)
{
if (a>b) a=b;
return a;
}
void palindrom(int a[nmax])
{
int i, left, right;
for (i=1; i<=m; i++) len[i]=1;
left=right=0;
for (i=1; i<=m; i++)
{
if (right>i)
len[i]=min(len[left+right-i], right-i+1);
if (i+len[i]-1>=right)
{
right=i+len[i]-1;
left=i-len[i]+1;
while (a[left-1]==a[right+1] && right<m && left>1)
{
left--;
right++;
len[i]++;
}
}
}
}
int main()
{
freopen("dreptpal.in","r",stdin);
freopen("dreptpal.out","w",stdout);
scanf("%d %d", &n, &m);
int i, j, x, dr;
for (i=1; i<=n; i++)
for (j=1; j<=m; j++) scanf("%d", &a[i][j]);
for (i=1; i<=n; i++)
{
palindrom(a[i]);
for (j=1; j<=m; j++) v[i][j]=len[j];
}
for (j=1; j<=m; j++)
{
dr=0;
s[0]=0;
for (i=1; i<=n; i++)
{
while (v[i][j]<=v[s[dr]][j] && dr>0) dr--;
left[i]=i-s[dr];
s[++dr]=i;
}
dr=0;
s[0]=n+1;
for (i=n; i>0; i--)
{
while (v[i][j]<=v[s[dr]][j] && dr>0) dr--;
right[i]=s[dr]-i;
s[++dr]=i;
}
for (i=1; i<=n; i++)
{
x=left[i]+right[i]-1;
x*=(2*v[i][j]-1);
if (x>sol) sol=x;
}
}
printf("%d\n",sol);
}