Cod sursa(job #17918)

Utilizator bogdan2412Bogdan-Cristian Tataroiu bogdan2412 Data 17 februarie 2007 13:41:15
Problema BMatrix Scor 36
Compilator c Status done
Runda Arhiva de probleme Marime 1.75 kb
#include <stdio.h>
#include <string.h>

#define MAXN 205

int N, M;
unsigned char x[MAXN][MAXN], up[MAXN][MAXN];
int best1[MAXN], best2[MAXN];

inline void rotate()
{
	int i, j, aux;
	for (i = 0; i < N; i++)
		for (j = i + 1; j < M; j++)
		{
			aux = x[i][j];
			x[i][j] = x[j][i];
			x[j][i] = aux;
		}
	aux = N;
	N = M;
	M = aux;
}

inline void horizontalflip()
{
	int i, l, r, aux;
	for (i = 0; i < M; i++)
		for (l = 0, r = N - 1; l < r; l++, r--)
		{
			aux = x[l][i];
			x[l][i] = x[r][i];
			x[r][i] = aux;
		}
}

void calculatebest( int best[MAXN] )
{
	memset(best, 0, sizeof(best));
	int i, j, k;
	for (i = 0; i < M; i++)
		up[0][i] = !x[0][i];
	for (i = 1; i < N; i++)
		for (j = 0; j < M; j++)
		{
			if (x[i][j] == 1)
				up[i][j] = 0;
			else
				up[i][j] = up[i - 1][j] + 1;
		}
	
	for (i = 0; i < N; i++)
	{
		int MAX = -0x3f3f3f3f;
		for (j = 0; j < M; j++)
		{
			int MIN = 0x3f3f3f3f;
			for (k = j; k < M && MIN; k++)
			{
				if (up[i][k] < MIN)
					MIN = up[i][k];

				if (MIN * (k - j + 1) > MAX)
					MAX = MIN * (k - j + 1);
			}
		}
		best[i] = MAX;
		if (i && best[i - 1] > best[i])
			best[i] = best[i - 1];
	}
}

inline int getbest()
{
	calculatebest( best1 );

	if (N == 1)
		return best1[0];

	horizontalflip();
	calculatebest( best2 );
	horizontalflip();


	int l = 0, r = N - 2, BEST = -0x3f3f3f3f;
	for (; l != N - 1; l++, r--)
		if (best1[l] + best2[r] > BEST)
			BEST = best1[l] + best2[r];
	return BEST;	
}

int main()
{
	freopen("bmatrix.in", "rt", stdin);
	freopen("bmatrix.out", "wt", stdout);
	scanf("%d %d", &N, &M);
	int i, j;
	for (i = 0; i < N; i++)
		for (j = 0; j < M; j++)
		{
			scanf(" %c ", x[i] + j);
			x[i][j] -= '0';
		}

	int NR1, NR2;
	NR1 = getbest();
	rotate();
	NR2 = getbest();

	printf("%d\n", (NR1 > NR2 ? NR1 : NR2));
	return 0;
}