记录编号	21819	评测结果	AAAAAAAAAA
题目名称	499.牛宫	最终得分	100
用户昵称	lc	是否通过	通过
代码语言	C++	运行时间	0.751 s
提交时间	2010-11-15 16:46:27	内存使用	0.78 MiB

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int maxn = 210;
int N,M,Ans;
int Map[maxn][maxn];
long long S[maxn][maxn];
long long res[maxn],Maxres[maxn];


void prep()
{
	scanf("%d%d",&N,&M);
	for (int i=1; i<=N; i++)
		for (int j=1; j<=M; j++)
			scanf("%d",&Map[i][j]);
	for (int i=1; i<=N; i++)
		for (int j=1; j<=M; j++)
			S[i][j] = S[i-1][j] + S[i][j-1] - S[i-1][j-1] + Map[i][j];
}

int find(int i,int j,int p)
{
	int L = 1,R = j;
	long long S1 = S[i][j] - S[p-1][j];
	if (S1 + Maxres[L-1] >0) return L;
	if (S1 + Maxres[R-1]<=0) return -1;
	
	while (R-L >1)
	{
		int Mid = (L + R)/2;
		if (S1 + Maxres[Mid-1] >0) R = Mid; else L = Mid;
	}
	return R;
}

void work()
{
	for (int i=1; i<=N; i++)
		for (int p=1; p<=i; p++)
		{
			for (int x=1; x<=M; x++) res[x] = S[p-1][x] - S[i][x];
			Maxres[0] = 0;
			for (int x=1; x<=M; x++) Maxres[x] = max(Maxres[x-1],res[x]);
			
			
			for (int j=1; j<=M; j++)
			{
				int q = find(i,j,p);
				//printf("%d %d %d %d\n",i,j,p,q);
				if (q==-1) continue;
				Ans = max(Ans , (i-p+1)*(j-q+1));
			}
		}
	
	printf("%d\n",Ans);
}


int main()
{
	freopen("long.in","r",stdin);
	freopen("long.out","w",stdout);
	prep();
	work();
	return 0;
}