2000.cpp

这是哈尔滨工业大学acmOJ的源代码

/* This Code is Submitted by wywcgs for Problem 2000 on 2007-06-01 at 12:53:57 */
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 128;

int main()
{
	int m[N][N], T;
	
	scanf("%d", &T);
	for(int t = 0; t < T; t++) {
		int r, c; scanf("%d %d", &r, &c);
		for(int i = 0; i < r; i++)
			for(int j = 0; j < c; j++)
				scanf("%d", &m[i][j]);
		int left[N], right[N], h[N] = { 0 };
		int res = 0;
		for(int i = 0; i < r; i++) {
			for(int j = 0; j < c; j++)
				if(m[i][j] == 0) h[j]++;
				else h[j] = 0;
			for(int j = 0, k; j < c; j++) {
				for(k = j-1; k >= 0 && h[k] >= h[j]; k = left[k]);
				left[j] = k;
			}
			for(int j = c-1, k; j >= 0; j--) {
				for(k = j+1; k < c && h[k] >= h[j]; k = right[k]);
				right[j] = k;
			}
			for(int j = 0; j < c; j++) res >?= (right[j]-left[j]-1)*h[j];
		}
		printf("%d\n", res);
	}
	return 0;
}