Cod sursa(job #539280)

Utilizator antoanelaAntoanela Siminiuc antoanela Data 22 februarie 2011 20:05:03
Problema BMatrix Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
#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);
}