Cod sursa(job #605643)

Utilizator crushackPopescu Silviu crushack Data 1 august 2011 14:59:20
Problema BMatrix Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <stdio.h>
#include <string.h>
//#include <algorithm>
#define NMax 210
#define INF 0x3f3f3f3f
using namespace std;

const char IN[]="bmatrix.in",OUT[]="bmatrix.out";

int N,M;
short Rez=0;
char a[NMax][NMax];
short T[NMax][NMax][NMax] , D[NMax][NMax];

short max(short a,short b){
	return a>b ? a : b;
}

short min(short a,short b){
	return a<b ? a : b;
}

void rotate(char a[][NMax])
{
	int i,j;
	static char b[NMax][NMax];
	for (i=1;i<=N;++i)
		for (j=1;j<=M;++j)
			b[M-j+1][i]=a[i][j];
	i=N;N=M;M=i;
	memcpy(a,b,sizeof(b));
}

void solve()
{
	short i,j,k, Min;
	for (i=1;i<=N;++i)
		for (j=1;j<=M;++j)
			D[i][j]= a[i][j]=='0' ? D[i][j-1]+1 : 0;
	for (i=1;i<=N;++i)
		for (j=1,Min=INF;j<=M;++j,Min=INF)
			for (k=1;i-k+1>0;++k)
			{
				Min=min(Min,D[i-k+1][j]);
				T[i][j][k]=max(max(max(Min*k,T[i][j][k-1]),T[i][j-1][k]),T[i-1][j][k-1]);
			}
	for (i=1;i<N;++i)
		Rez=max(Rez,T[i][M][i]+T[N][M][N-i]);
}

int main()
{
	int i;
	freopen(IN,"r",stdin);
	scanf("%d%d\n",&N,&M);
	for (i=1;i<=N;++i) fgets( a[i]+1 , NMax , stdin ),a[i][M+1]=0;
	fclose(stdin);
	
	solve();
	rotate(a);
	solve();
	
	freopen(OUT,"w",stdout);
	printf("%d\n",Rez);
	fclose(stdout);
	
	return 0;
}