3084687_ac_1906ms_15920k.cc

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <string.h>

int array[2001][2001], len[2001], left[2001], right[2001];

int main()
{
	int i, j, m, n, k;
	int tmp, ans;

	while(scanf("%d%d",&n,&m)==2)
	{
		for(i = 0; i < n; i++)
		{
			for(j = 0; j < m; j++)
			{
				scanf("%d",&array[i][j]);
			}
		}
		memset(len,0,sizeof(len));
		ans = 0;
		for(i = 0; i < n; i++)
		{
			for(j = 0; j < m; j++)
			{
				if(array[i][j]==0)
					len[j] = 0;
				else
					len[j]++;
			}
			left[0] = -1;
			for(j =	1; j < m; j++)
			{
				k = j-1;
				while(k!=-1&&len[k]>=len[j])
					k = left[k];
				left[j] = k;
			}
			right[m-1] = m;
			for(j = m-2; j >= 0; j--)
			{
				k = j+1;
				while(k!=m&&len[k]>=len[j])
					k = right[k];
				right[j] = k;
			}
			for(j = 0; j < m; j++)
			{
				tmp = len[j]*(right[j]-left[j]-1);
				if(tmp > ans)
					ans = tmp;
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}