Cod sursa(job #827990)

Utilizator dariusdariusMarian Darius dariusdarius Data 2 decembrie 2012 21:11:17
Problema BMatrix Scor 36
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.82 kb
#include<stdio.h>
#include<string.h>
int n,m,max,a[205][205],d1[205],d2[205],c[205][205],st[205];
int rmq[205][205];
int lg[205];
int maxim(int a,int b) {return a>b?a:b;}
int minim(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 update(int ind,int d[205],int x)
{
	//trebuie sa gasesc i,j astfel incat (j-i+1)*rmq(i,j) maxim
	int rmqq,i,j,l,dif,s;
	for(j=1;j<=m;j++)
		rmq[0][j]=c[ind][j];
	for(i=1;(1<<i)<=m;i++)
		for(j=1;j<=m-(1<<i)+1;j++)
		{
		l=1<<(i-1);
		rmq[i][j]=minim(rmq[i-1][j],rmq[i-1][j+l]);
		}
	for(i=1;i<=m;i++)
		for(j=i;j<=m;j++)
		{
			dif=j-i+1;
			l=lg[dif];
			s=dif-(1<<l);
			rmqq=minim(rmq[l][i],rmq[l][i+s]);
			if(rmqq*dif>d[ind])
				d[ind]=rmqq*dif;
		}
	d[ind]=maxim(d[ind],d[ind+x]);
}
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++)
		update(i,d1,-1);
    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--)
		update(i,d2,1);
    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';}

	lg[1]=0;
	for(i=2;i<=m;i++)
		lg[i]=lg[i/2]+1;
	
    solve();
    rotate();
    solve();
    printf("%d\n",max);
    return 0;
}