Cod sursa(job #326021)

Utilizator ProtomanAndrei Purice Protoman Data 23 iunie 2009 13:57:19
Problema BMatrix Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.66 kb
#include <algorithm>
#include <stdio.h>

#define MAX 256

using namespace std;

int n, m, sol;
int arieSus[MAX];
int matSus[MAX][MAX], matJos[MAX][MAX];
char matConf[MAX][MAX];

inline void calc()
{
	memset(arieSus, 0, sizeof(arieSus));
	memset(matJos, 0, sizeof(matJos));
	memset(matSus, 0, sizeof(matSus));

	// Orizontala
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
			if (matConf[i][j] == '0')
				matSus[i][j] = matSus[i - 1][j] + 1;
			else matSus[i][j] = 0;

		int el = n + 1 - i;
		for (int j = 1; j <= m; j++)
			if (matConf[el][j] == '0')
				matJos[el][j] = matJos[n + 2 - i][j] + 1;
			else matJos[el][j] = 0;
	}

	// De sus
	for (int i = 1; i <= n; i++)
	{
		arieSus[i] = arieSus[i - 1];

		for (int stj = 1; stj <= m; stj++)
		{
			int minGs = MAX;

			for (int fnj = stj; fnj <= m; fnj++)
			{
				minGs = min(minGs, matSus[i][fnj]);

				arieSus[i] = max(arieSus[i], minGs * (fnj - stj + 1));
			}
		}
	}

	// De jos
	for (int i = n; i; i--)
		for (int stj = 1; stj <= m; stj++)
		{
			int minGs = MAX;

			for (int fnj = stj; fnj <= m; fnj++)
			{
				minGs = min(minGs, matJos[i][fnj]);

				sol = max(sol, arieSus[i - 1] + minGs * (fnj - stj + 1));
			}
		}
}

int main()
{
	freopen("bmatrix.in", "r", stdin);
	freopen("bmatrix.out", "w", stdout);

	scanf("%d %d\n", &n, &m);

	for (int i = 1; i <= n; i++)
		fgets(matConf[i] + 1, MAX, stdin);

	calc();

	// Interschimbare
	for (int i = 1; i < MAX; i++)
		for (int j = i + 1; j < MAX; j++)
			swap(matConf[i][j], matConf[j][i]);
	swap(n, m);

	calc();

	printf("%d\n", sol);

	fclose(stdin);
	fclose(stdout);
	return 0;
}