Cod sursa(job #357324)

Utilizator Mishu91Andrei Misarca Mishu91 Data 18 octombrie 2009 20:42:07
Problema BMatrix Scor 100
Compilator cpp Status done
Runda porc_e Marime 2.08 kb
#include <cstdio>

#define MAX_N 205

int N, M;
char A[MAX_N][MAX_N];
int Ln_sus[MAX_N], Ln_jos[MAX_N], Col_st[MAX_N], Col_dr[MAX_N];

inline int max(const int &A, const int &B) {return ((A) > (B))? (A) : (B);}
inline int min(const int &A, const int &B) {return ((A) < (B))? (A) : (B);}

void citire()
{
	scanf("%d %d\n",&N, &M);

	for(int i = 1; i <= N; ++i)
		fgets(A[i]+1, MAX_N, stdin);
}

void solve()
{
	int B[MAX_N][MAX_N];
	for(int i = 1; i <= N; ++i)
		for(int j = 1; j <= M; ++j)
			B[i][j] = (A[i][j] == '0')? B[i][j-1]+1 : 0;

	for(int i = 1; i <= N; ++i)
		for(int j = 1; j <= M; ++j)
		{
			Ln_sus[i] = max(Ln_sus[i], B[i][j]);
			int act = B[i][j];

			for(int k = i-1; k; --k)
			{
				act = min(act, B[k][j]);
				Ln_sus[i] = max(Ln_sus[i], act*(i - k + 1));
			}
		
			Ln_jos[i] = max(Ln_jos[i], B[i][j]);
			act = B[i][j];

			for(int k = i+1; k <= N; ++k)
			{
				act = min(act, B[k][j]);
				Ln_jos[i] = max(Ln_jos[i], act*(k - i + 1));
			}
		}

	for(int i = 1; i <= N; ++i)
		for(int j = 1; j <= M; ++j)
			B[i][j] = (A[i][j] == '0')? B[i-1][j]+1 : 0;

	for(int i = 1; i <= N; ++i)
		for(int j = 1; j <= M; ++j)
		{
			Col_st[j] = max(Col_st[j], B[i][j]);
			int act = B[i][j];

			for(int k = j-1; k; --k)
			{
				act = min(act, B[i][k]);
				Col_st[j] = max(Col_st[j], act*(j-k+1));
			}

			Col_dr[j] = max(Col_dr[j], B[i][j]);
			act = B[i][j];

			for(int k = j+1; k <= M; ++k)
			{
				act = min(act, B[i][k]);
				Col_dr[j] = max(Col_dr[j], act*(k-j+1));
			}	
		}

	int Sol = 0;

	for(int i = 1; i <= N; ++i) Ln_sus[i] = max(Ln_sus[i], Ln_sus[i-1]);
	for(int i = 1; i <= N; ++i) Ln_sus[i] = max(Ln_sus[i], Ln_sus[i-1]);
	for(int i = N; i; --i)		Ln_jos[i] = max(Ln_jos[i], Ln_jos[i+1]);
	for(int j = 1; j <= M; ++j) Col_st[j] = max(Col_st[j], Col_st[j-1]);
	for(int j = M; j; --j)		Col_dr[j] = max(Col_dr[j], Col_dr[j+1]);

	for(int i = 1; i <= N; ++i) Sol = max(Sol, Ln_sus[i] + Ln_jos[i+1]);
	for(int j = 1; j <= M; ++j) Sol = max(Sol, Col_st[j] + Col_dr[j+1]);

	printf("%d\n",Sol);
}

int main()
{
	freopen("bmatrix.in","rt",stdin);
	freopen("bmatrix.out","wt",stdout);

	citire();
	solve();
}