Cod sursa(job #496996)

Utilizator dushmiMihai-Alexandru Dusmanu dushmi Data 1 noiembrie 2010 11:18:32
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.04 kb
#include<cstdio>
const int N=1<<8;
int sol,n,m,g[N],h[N],a[N][N],st[N][N],jo[N][N],djo[N][N],dst[N][N];
void read()
{
    freopen("bmatrix.in","r",stdin);
    freopen("bmatrix.out","w",stdout);
    scanf("%d%d\n",&n,&m);
    char s[N];
    for(int i=1;i<=n;i++)
    {
        gets(s);
        for(int j=1;j<=m;j++)
            a[i][j]=s[j-1]-'0';
    }
}
void init()
{
    int i,j;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            if(a[i][j]==0)
                st[i][j]=st[i][j-1]+1;
	for(i=1;i<=n;i++)
		for(j=m;j>=1;j--)
            if(a[i][j]==0)
				jo[i][j]=jo[i][j+1]+1;
}
int min(int x,int y)
{
    return x<y?x:y;
}
int max(int x,int y)
{
    return x>y?x:y;
}
void getmat1()
{
    int x;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            x=st[i][j];
            dst[i][j]=x;
            for(int k=i-1;k>=1;k--)
            {
                x=min(x,st[k][j]);
                if(!x)
                    break;
                dst[i][j]=max(dst[i][j],(i-k+1)*x);
            }
        }
}
void getmat2()
{
    int y;
	for(int i=n;i>=1;i--)
		for(int j=1;j<=m;j++)
		{
			y=jo[i][j];
			djo[i][j]=y;
			for(int k=i+1;k<=n;k++)
			{
				y=min(y,jo[k][j]);
				if(!y)
					break ;
				djo[i][j]=max(djo[i][j],(k-i+1)*y);
			}
		}
}
void solveor()
{
	int bs=0;
	for(int i=2;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
			bs=max(bs,dst[i-1][j]);
		g[i]=bs;
	}
	bs=0;
	for(int i=n-1;i>=1;i--)
	{
		for(int j=1;j<=m;j++)
			bs=max(bs,djo[i+1][j]);
		h[i]=bs;
	}
	for(int i=2;i<=n;i++)
		sol=max(sol,g[i]+h[i-1]);
}
void solveve()
{
    int bs;
	bs=0;
	for(int j=2;j<=m;j++)
	{
		for(int i=1;i<=n;i++)
			bs=max(bs,dst[i][j-1]);
		g[j]=bs;
	}
	bs=0;
	for(int j=m-1;j>=1;j--)
	{
		for(int i=1;i<=n;i++)
			bs=max(bs,djo[i][j+1]);
		h[j]=bs;
	}
	for(int i=2;i<=m;i++)
		sol=max(sol,g[i]+h[i-1]);
}
int main()
{
    read();
    init();
    getmat1();
    getmat2();
    solveor();
    solveve();
    printf("%d",sol);
    return 0;
}