Cod sursa(job #826971)

Utilizator dariusdariusMarian Darius dariusdarius Data 1 decembrie 2012 14:48:09
Problema BMatrix Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.26 kb
#include<stdio.h>
#include<string.h>
int n,m,max,a[205][205],d1[205],d2[205],c[205][205],st[205];
int maxim(int a,int b) {return a>b?a:b;}
void rotate ()
{
	int i,j,aa;
	int aux[205][205];
	for ( i=1; i<=n; i++ )
		for ( j=1; j<=m; j++ )
		{
			aux[j][n-i+1]=a[i][j];
			a[i][j]=0;
		}
	aa=n;n=m;m=aa;
	for(i=1;i<=n;i++)
		for ( j=1; j<=m; j++ )
			a[i][j]=aux[i][j];
}
void update1(int i)
{
	int j,u,p;
	u=0;memset(st,0,sizeof(st));
	for(j=1;j<=m;j++)
	{
		p=1;
		while(u>=1 && st[u]>c[i][j]) {if(st[p]*(u-p+1)>d1[i]) d1[i]=st[p]*(u-p+1);  u--;}
		st[++u]=c[i][j];
		for(p=1;p<=u;p++)
			if(st[p]*(u-p+1)>d1[i]) d1[i]=st[p]*(u-p+1);
	}
	u=0;memset(st,0,sizeof(st));
	for(j=m;j>=1;j--)
	{
		p=1;
		while(u>=1 && st[u]>c[i][j]) {if(st[p]*(u-p+1)>d1[i]) d1[i]=st[p]*(u-p+1);  u--;}
		st[++u]=c[i][j];
		for(p=1;p<=u;p++)
			if(st[p]*(u-p+1)>d1[i]) d1[i]=st[p]*(u-p+1);
	}
	d1[i]=maxim(d1[i],d1[i-1]);
}
void update2(int i)
{
	int j,u,p;
	u=0;memset(st,0,sizeof(st));
	for(j=1;j<=m;j++)
	{
		p=1;
		while(u>=1 && st[u]>c[i][j]) {if(st[p]*(u-p+1)>d2[i]) d2[i]=st[p]*(u-p+1);u--;}
		st[++u]=c[i][j];
		for(p=1;p<=u;p++)
			if(st[p]*(u-p+1)>d2[i]) d2[i]=st[p]*(u-p+1);
	}
	u=0;memset(st,0,sizeof(st));
	for(j=m;j>=1;j--)
	{
		p=1;
		while(u>=1 && st[u]>c[i][j]) {if(st[p]*(u-p+1)>d2[i]) d2[i]=st[p]*(u-p+1);u--;}
		st[++u]=c[i][j];
		for(p=1;p<=u;p++)
			if(st[p]*(u-p+1)>d2[i]) d2[i]=st[p]*(u-p+1);
	}
	d2[i]=maxim(d2[i],d2[i+1]);
}
void solve()
{
    int i,j;
	memset(d1,0,sizeof(d1));
	memset(d2,0,sizeof(d2));
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            c[i][j]=(a[i][j]==0)?(c[i-1][j]+1):0;
    for(i=1;i<=n;i++)
		update1(i);
    for(i=n;i>=1;i--)
        for(j=1;j<=m;j++)
            c[i][j]=(a[i][j]==0)?(c[i+1][j]+1):0;
    for(i=n;i>=1;i--)
		update2(i);
    for(i=0;i<=n;i++)
        if(d1[i]!=0 && d2[i+1]!=0 && d1[i]+d2[i+1]>max)
            max=d1[i]+d2[i+1];
}
int main()
{
    freopen("bmatrix.in","r",stdin);
    freopen("bmatrix.out","w",stdout);
    int i,j;char x;
    scanf("%d %d\n",&n,&m);
    for(i=1;i<=n;i++,scanf("%c",&x))
        for(j=1;j<=m;j++)
            {scanf("%c",&x);a[i][j]=x-'0';}
    solve();
    rotate();
    solve();
    printf("%d\n",max);
    return 0;
}