Pagini recente » Cod sursa (job #2192707) | Cod sursa (job #1358507) | Cod sursa (job #2208035) | Cod sursa (job #2385794) | Cod sursa (job #539280)
Cod sursa(job #539280)
#include <cstdio>
#define nmax 1002
int v[nmax][nmax], n, m, x, y;
short c[2*nmax][2*nmax], q[nmax], p[nmax], d[nmax];
char a[2*nmax][2*nmax];
short min(short a, short b)
{
if (a>b) a=b;
return a;
}
int main()
{
freopen("jmenoasa.in","r",stdin);
freopen("jmenoasa.out","w",stdout);
scanf("%d %d",&n, &m);
int i, j, h;
for (i=1; i<=n; i++)
for (j=1; j<=m; j++) scanf("%d",&v[i][j]);
for (i=1; i<=n; i++)
for (j=1; j<m; j++)
if (v[i][j]>=v[i][j+1]) a[2*i-1][2*j]=1;
for (j=1; j<=m; j++)
for (i=1; i<n; i++)
if (v[i][j]>=v[i+1][j]) a[2*i][2*j-1]=1;
m=2*m-1;
n=2*n-1;
for (i=1; i<=n; i++)
for (j=1; j<=m; j++)
if (!a[i][j]) c[i][j]=c[i-1][j]+1;
for (i=1; i<=n; i++)
{
h=0;
p[0]=0;
for (j=1; j<=m; j++)
{
while (h && c[i][j]<=q[h]) h--;
d[j]=j-p[h];
q[++h]=c[i][j];
p[h]=j;
}
h=0;
p[h]=m+1;
for (j=m; j>0; j--)
{
while (h && c[i][j]<=q[h]) h--;
d[j]+=p[h]-j-1;
q[++h]=c[i][j];
p[h]=j;
}
for (j=1; j<=m; j++)
{
if (c[i][j]*d[j]>x*y)
{
x=c[i][j];
y=d[j];
}
}
}
printf("%d\n",(x+1)*(y+1)/4);
}