Cod sursa(job #1210315)

Utilizator mihaimusatMihai Musat mihaimusat Data 19 iulie 2014 16:49:16
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.86 kb
#include<fstream>
#include <cstring>
#include <algorithm>

using namespace std;

int N, M;
char A[202][202], B[202][202];
int up[202][202];
int D[202], lft[202], rgh[202];
int maxp1[202], maxp2[202], mx1[202], mx2[202];
int result;

void compute_max(int* best, int* inc)
{
	for (int i = 1; i <= N; ++i)
		for (int j = 1; j <= M; ++j)
			if (A[i][j] == '0')
				up[i][j] = up[i - 1][j] + 1;
			else
				up[i][j] = 0;

	memset(best, 0, sizeof(maxp1));
	for (int i = 1; i <= N; ++i)
	{
		D[0] = 0;
		for (int j = 1; j <= M; ++j)
		{
			while (D[0] && up[i][D[D[0]]] >= up[i][j])
				--D[0];
			if (D[0] == 0) lft[j] = j;
			else           lft[j] = j - D[D[0]];
			D[++D[0]] = j;
		}
		D[0] = 0;
		for (int j = M; j >= 1; --j)
		{
			while (D[0] && up[i][D[D[0]]] >= up[i][j])
				--D[0];
			if (D[0] == 0) rgh[j] = M - j + 1;
			else           rgh[j] = D[D[0]] - j;
			D[++D[0]] = j;
		}

		for (int j = 1; j <= M; ++j)
			if (up[i][j] * (lft[j] + rgh[j] - 1) > best[i])
				best[i] = up[i][j] * (lft[j] + rgh[j] - 1);
	}

	inc[1] = best[1];
	for (int i = 2; i <= N; ++i)
		inc[i] = max(inc[i - 1], best[i]);
}
void do_best()
{
	compute_max(maxp1, mx1);
	for (int i = 1; i <= N / 2; ++i)
		for (int j = 1; j <= M; ++j)
			swap(A[i][j], A[N - i + 1][j]);
	compute_max(maxp2, mx2);
	for (int i = 1; i <= N / 2; ++i)
		for (int j = 1; j <= M; ++j)
			swap(A[i][j], A[N - i + 1][j]);
	for (int i = 1; i <= N; ++i)
		if (mx1[i] > 0 && mx2[N - i] > 0)
			result = max(result, mx1[i] + mx2[N - i]);
}

int main()
{
	ifstream fin("bmatrix.in");
	ofstream fout("bmatrix.out");

	fin >> N >> M;
	for (int i = 1; i <= N; ++i)
		fin >> (A[i] + 1);
	memcpy(B, A, sizeof(B));

	do_best();
	for (int i = 1; i <= M; ++i)
		for (int j = 1; j <= N; ++j)
			A[i][j] = B[j][i];
	swap(N, M);
	do_best();

	fout << result << '\n';

	return 0;
}