Cod sursa(job #190001)

Utilizator scvalexAlexandru Scvortov scvalex Data 19 mai 2008 17:21:01
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.61 kb
#include <iostream>
#include <fstream>

using namespace std;

int N, M;
char A[203][203];
int H[203][203], M1[203][203], M2[203][203];

#define MAX(a, b) ((a > b) ? (a) : (b))

int main(int argc, char *argv[]) 
{
	FILE *fi = fopen("bmatrix.in", "r");
	fscanf(fi, "%d %d", &N, &M);
	for (int i(1); i <= N; ++i)
		fscanf(fi, "%s\n", A[i]+1);
	fclose(fi);

	for (int i(1); i <= N; ++i)
		for (int j(1); j <= M; ++j)
			if (A[i][j] == '0')
				H[i][j] = H[i-1][j] + 1;
			else
				H[i][j] = 0;

	for (int i(1); i <= N; ++i)
		for (int j(1); j <= M; ++j) {
			int max = 0;
			int hmin = 202;
			for (int k = j; k > 0; --k) {
				if (hmin > H[i][k])
					hmin = H[i][k];
				if (max < (j-k+1) * hmin)
					max = (j-k+1) * hmin;
			}
			M1[i][j] = max;
			M1[i][M+1] = MAX(M1[i][M+1], MAX(max, M1[i-1][M+1]));
			M1[N+1][j] = MAX(M1[N+1][j], MAX(max, M1[N+1][j-1]));
		}

	for (int i = N; i >= 1; --i)
		for (int j = 1; j <= M; ++j)
			if (A[i][j] == '0')
				H[i][j] = H[i+1][j] + 1;
			else
				H[i][j] = 0;

	for (int i = N; i >= 1; --i)
		for (int j = M; j >= 1; --j) {
			int max(0);
			int hmin = 202;
			for (int k = j; k <= M; ++k) {
				if (hmin > H[i][k])
					hmin = H[i][k];
				if (max < (k-j+1) * hmin)
					max = (k-j+1) * hmin;
			}
			M2[i][j] = max;
			M2[i][0] = MAX(M2[i][0], MAX(max, M2[i+1][0]));
			M2[0][j] = MAX(M2[0][j], MAX(max, M2[0][j+1]));
		}

	int R(0);
	for (int j(1); j < M; ++j)
		if (R < M1[N+1][j] + M2[0][j+1])
			R = M1[N+1][j] + M2[0][j+1];
	for (int i(1); i < N; ++i)
		if (R < M1[i][M+1] + M2[i+1][0])
			R = M1[i][M+1] + M2[i+1][0];

	ofstream fout("bmatrix.out");
	fout << R << endl;
	fout.close();

	return 0;
}