记录编号	331414	评测结果	AAAAAAAAAA
题目名称	牛宫	最终得分	100
用户昵称	残星誓言	是否通过	通过
代码语言	C++	运行时间	1.361 s
提交时间	2016-10-27 18:39:43	内存使用	0.79 MiB

#include<iostream>
#include<cstdio>
#include<stack>
#define Lint long long
using namespace std;
const Lint maxn=250;
Lint	sum[maxn];
Lint	rum[maxn][maxn];
Lint n,m;
Lint s[maxn];
Lint top;
Lint ans=0;
Lint find_j(Lint x)
{
	Lint tp=sum[x];
	Lint	l=1; Lint r=top;Lint re;
	if(sum[s[top]]>=tp) return -1;
	while(l<r)
	{
		Lint mid=(l+r)>>1;
		if(sum[s[mid]]<sum[x])
		{
			r=mid;
		}
		else
		{
			l=mid+1;
		}
	}
	//printf("cao %d cao",tp);
	return s[l];
}
void solve(Lint l,Lint r)
{
	sum[0]=0;
	s[++top]=0;
	for(Lint i=1;i<=n;i++)
	{
		/*printf("%d")
		for(Lint k=1;k<=top;k++)
		printf("%d ",sum[s[k]]);*/
		Lint tp=rum[i][r]-rum[i][l-1]; 
		sum[i]=sum[i-1]+tp;
		Lint j=find_j(i);
		if(j!=-1) ans=max(ans,(r-l+1)*(i-j));
		//printf("l=%d 	r=%d    sum[%d]=%d  sum[%d]=%d   ans=%d\n",l,r,i,sum[i],j,sum[j],ans);
		if(sum[i]<sum[s[top]])
		{
			top++;
			s[top]=i;
		}
		
	}
}
int main()
{
	freopen("long.in","r",stdin);
	freopen("long.out","w",stdout);
	scanf("%lld%lld",&n,&m);
	for(Lint i=1;i<=n;i++)
		{	rum[i][0]=0;
			for(Lint j=1;j<=m;j++)
			{
				scanf("%lld",&rum[i][j]);
				rum[i][j]+=rum[i][j-1];
			}
		}
	for(Lint i=1;i<=m;i++)
		for(Lint j=i;j<=m;j++)
		{
			top=0;
			solve(i,j);
		}
	printf("%lld",ans);
}