Cod sursa(job #1670)

Utilizator mariusdrgdragus marius mariusdrg Data 14 decembrie 2006 14:19:07
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.37 kb
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>

const int maxn = 203;

int cat,a[maxn][maxn];
int i,j,k,n,k1,m,l,max1[maxn][maxn];
char car;
int max2[maxn][maxn],max3[maxn][maxn];

using namespace std;

int maxim(int a,int b,int c)
{
	if (a>=b&& a>=c) return a;
        if (c>=b)return c;
	return b;

}


int main()
{
	freopen("bmatrix.in","r",stdin);
	freopen("bmatrix.out","w",stdout);
        scanf("%d %d\n",&n,&m);
	int max=0;
 	for(i=1;i<=n;i++)
                for(j=1;j<=m;j++)
		{
                        scanf(" %c ",&car);
                        a[i][j]=car-'0';
        	}
	for(i=1;i<=n;i++)
        	for(j=1;j<=m;j++)
		{
                        if (a[i][j]==0) max1[i][j]=max1[i-1][j]+1;
                }
        for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
                {
                	for(k=j;k>0;k--)
                                if (max1[i][j]>max1[i][k]) break;
                        k++;
			for(k1=j;k1<=m;k1++)
				if (max1[i][j]>max1[i][k1]) break;
                        if (i==5&&j==4)
			{
                        	i=5;
			}
			k1--;
                        max=(k1-k+1)*max1[i][j];
			max2[i][j]=maxim(max2[i-1][j],max2[i][j-1],max);

                }
        memset(max1,0,sizeof(max1));
        for(i=n;i>=1;i--)
		for(j=1;j<=m;j++)
                {
                        if (a[i][j]==0) max1[i][j]=max1[i+1][j]+1;
		}
        for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
		{
                        for(k=j;k>0;k--)
				if (max1[i][j]>max1[i][k]) break;
                        k++;
                        for(k1=j;k1<=m;k1++)
                                if (max1[i][j]>max1[i][k1]) break;
                        k1--;
                        max=(k1-k+1)*max1[i][j];
                        max3[i][j]=maxim(max3[i+1][j],max3[i][j-1],max);

		}
        int maxt=0;
	for(i=1;i<=n;i++)
                if (max2[i][m]+max3[i+1][m]>maxt)maxt=max2[i][m]+max3[i+1][m];
        memset(max2,0,sizeof(max2));
	memset(max3,0,sizeof(max3));
 	memset(max1,0,sizeof(max1));
        for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
                {
                        if (a[i][j]==0) max1[i][j]=max1[i][j-1]+1;
		}
        for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
		{
                        for(k=i;k>0;k--)
				if (max1[i][j]>max1[k][j]) break;
                        k++;
                        for(k1=i;k1<=n;k1++)
                                if (max1[i][j]>max1[k1][j]) break;
                        k1--;
                        max=(k1-k+1)*max1[i][j];
                        max2[i][j]=maxim(max2[i-1][j],max2[i][j-1],max);

		}
        memset(max1,0,sizeof(max1));
        for(i=1;i<=n;i++)
		for(j=m;j>=1;j--)
                {
                        if (a[i][j]==0) max1[i][j]=max1[i][j+1]+1;
		}
        for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
		{
                        for(k=i;k>0;k--)
				if (max1[i][j]>max1[k][j]) break;
                        k++;
                        for(k1=i;k1<=n;k1++)
                                if (max1[i][j]>max1[k1][j]) break;
                        k1--;
                        max=(k1-k+1)*max1[i][j];
                        max3[i][j]=maxim(max3[i-1][j],max3[i][j+1],max);

		}

        for(i=1;i<=m;i++)
                if (max2[n][i]+max3[n][i+1]>maxt)maxt=max2[n][i]+max3[n][i+1];
        printf("%d",maxt);


     	return 0;

}