Cod sursa(job #70967)

Utilizator peanutzAndrei Homorodean peanutz Data 8 iulie 2007 19:03:28
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.57 kb
#include <stdio.h>
#include <memory.h>
#define NMAX 205

int a[NMAX][NMAX];
int b[NMAX][NMAX];
int cache[NMAX];
int n, m;
int max;

//#define cache (cache-1)

void read()
{
	int i, j;
	char c[NMAX];
	scanf("%d%d\n", &n, &m);
	for(i = 1; i <= n; ++i)
	{
		scanf("%s", c+1);

		for(j = 1; j <= m; ++j)
		{
			//scanf("%c", &c);
			if(c[j] == '0')
			a[i][j] = 0;
			else
			a[i][j] = 1;
		}
	}
}

int compute(int count)
{
  int stackHeight[NMAX];
  int stackPos[NMAX];
  int size = 0;

  cache[++count] = 0;

  /*  for (int j = 0; j < count; ++j) {
    cout << cache[j] << " ";
  }
  cout << endl;*/

  memset(stackHeight, 0, sizeof(stackHeight));
  memset(stackPos, 0, sizeof(stackPos));

  stackHeight[0] = 0;
  stackPos[0] = -1;
  size = 1;

  int result = 0;

  for (int j = 0; j <= count; ++j) {
    int cpos = j;
    while (size > 0 && stackHeight[size - 1] >= cache[j]) {
      cpos = stackPos[size - 1];
      int h = stackHeight[size - 1];
      int w = j - stackPos[size - 1];
      if (h * w > result) {
	result = h * w;
      }
      size--;
    }
    if (cache[j] > stackHeight[size - 1]) {
      stackHeight[size] = cache[j];
      stackPos[size] = cpos;
      size++;
    }
  }
  return result;
}


void solve()
{
	int i, j;
	int above[NMAX], below[NMAX];
	memset(above, 0, sizeof(above));
	memset(below, 0, sizeof(below));
	memset(cache, 0, sizeof(cache));

	for(i = 1; i <= n; ++i)
	{
		for(j = 1; j <= m; ++j)
			if(a[i][j])
				cache[j] = 0;
			else
				++cache[j];

		below[i] = compute(m);
		if(below[i-1] > below[i])
			below[i] = below[i-1];
	}
	memset(cache, 0, sizeof(cache));

	for(i = n; i; --i)
	{
		for(j = 1; j <= m; ++j)
			if(a[i][j])
				cache[j] = 0;
			else
				++cache[j];
		
		above[i] = compute(m);
		if(above[i+1] > above[i])
			above[i] = above[i+1];
	}
	for(i = 0; i <= n; ++i)
	       if(below[i] + above[i+1] > max)
			max = below[i] + above[i+1];
}

void invert()
{
	for(int i = 1; i <= n; ++i)
		for(int j = 1; j <= m; ++j)
			b[j][i] = a[i][j];


	memcpy(a, b, sizeof(b));
	int aux = n;
	n = m;
	m = aux;
}

void print()
{

	for(int i = 1; i <= n; ++i)
	{
		for(int j = 1; j <= m; ++j)
			printf("%d", a[i][j]);
		printf("\n");
	}
        printf("%d %d\n", n, m);
}

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

	read();

	solve();

	invert();

	//print();

	solve();

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

	return 0;
}