Cod sursa(job #385643)

Utilizator FlorianFlorian Marcu Florian Data 23 ianuarie 2010 11:03:53
Problema BMatrix Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.81 kb
using namespace std;
#include<fstream>
int N,M;
char A[207][207];
int B[207][207];
int L_sus[207];
int L_jos[207];
int C_st[207], C_dr[207];
ifstream inp("bmatrix.in"); 
ofstream out("bmatrix.out");
int main()
{
	int i, j, sol = 0, tmp, p;
	inp>>N>>M;
	for(i=1;i<=N;++i)
	{		
		for(j=1;j<=M;++j)
			inp>>A[i][j];		
	}
	for(i = 1; i <= N; ++i)
		for(j = 1; j <= M; ++j)
			if(A[i][j] == '0') B[i][j] = B[i][j-1] + 1;
			else B[i][j] = 0;
	for(i = 1; i <= N; ++i)
		for(j = 1; j <= M; ++j)
		{
			L_sus[i] = max(L_sus[i], B[i][j]);
			L_jos[i] = max(L_jos[i], B[i][j]);
			tmp = B[i][j];
			for(p = i-1; p; --p)
			{
				tmp = min(tmp, B[p][j]);
				L_sus[i] = max(L_sus[i], tmp * (i-p+1));
			}
			tmp = B[i][j];
			for(p = i + 1; p <= N; ++p)
			{
				tmp = min(tmp, B[p][j]);
				L_jos[i] = max(L_jos[i], tmp * (p-i+1));
			}
		}
	for(i = 1; i <= N; ++i)
		for(j = 1; j <= M; ++j)
			if(A[i][j] == '0') B[i][j] = B[i-1][j] + 1;
			else B[i][j] = 0;
	for(i = 1; i <= N; ++i)
		for(j = 1; j <= M; ++j)
		{
			C_st[j] = max(C_st[j], B[i][j]);
			C_dr[j] = max(C_dr[j], B[i][j]);
			tmp = B[i][j];
			for(p = j-1; p; --p)
			{
				tmp = min(tmp, B[i][p]);
				C_st[j] = max(C_st[j], tmp * ( j - p + 1));
			}
			tmp = B[i][j];
			for(p = j + 1; p <= M; ++p)
			{
				tmp = min(tmp, B[i][p]);
				C_dr[j] = max(C_dr[j], tmp * (p - j +1));
			}
		}
	for(i = 2; i <= N; ++i) L_sus[i] = max(L_sus[i], L_sus[i-1]);
	for(i = N-1; i; --i) L_jos[i] = max(L_jos[i], L_jos[i+1]);
	for(j = 2; j <= M; ++j) C_st[j] = max(C_st[j], C_st[j-1]);
	for(j = M-1; j>0; --j) C_dr[j] = max(C_dr[j], C_dr[j+1]);
	
	// tai vertical
	for(i = 1; i <= M; ++i) sol = max(sol, C_st[i]+C_dr[i+1]);
	// tai orizontal
	for(i = 1; i <= N; ++i) sol = max(sol, L_sus[i]+L_jos[i+1]);
	out<<sol<<"\n";
	return 0;
}