题目描述
AP 神牛准备给自己盖一座很华丽的宫殿。于是，他看中了一块N*M 的矩形空地。
空地中每个格子都有自己的海拔高度。AP 想让他的宫殿的平均海拔在海平面之上（假设
海平面的高度是0，平均数都会算吧？）。而且，AP 希望他的宫殿尽量大，能够容纳更
多的人来膜拜他。请问AP 的宫殿最后会有多大？
输入输出格式
输入格式：
第一行为N 和M。之后N 行，每行M 个数，描述的空地的海拔。
输出格式：
输出一行,表示宫殿最大面积。
输入输出样例
输入样例#1：
3 2
4 0
-10 8
-2 -2
输出样例#1：
4
单调栈+dp
O(n^2)枚举矩形左右范围，从上往下扫每一行，如果从1到k行的总和大于0，那么整块矩形可选；如果总和小于零，将其存入一个单调递减的单调栈，这样在之后的计算中，如果smm(1~k) - smm(1~x)>0,那么行x+1到行k这部分矩形可选。查询时候用二分查找比较快。
万万没想到这题需要开long long，wa了一片
/*by SilverN*/
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<vector>
#define LL long long
using namespace std;
const int mxn=;
int read(){
int x=,f=;char ch=getchar();
while(ch<'' || ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>='' && ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
int a[mxn][mxn];
LL smm[mxn][mxn];
int n,m;
int ans=;
int f[mxn];
LL st[mxn];
int top=;
int find(LL x){
int l=,r=top,w=-;
while(l<=r){
int mid=(l+r)>>;
if(st[mid]<x)r=mid-,w=mid;
else l=mid+;
}
return w;
}
int main(){
n=read();m=read();
int i,j;
for(i=;i<=n;i++)
for(j=;j<=m;j++){
a[i][j]=read();
smm[i][j]=smm[i][j-]+a[i][j];
}
st[]=1e10;
for(i=;i<=m;i++)//左边界
for(j=i;j<=m;j++){//右边界
LL tmp=;
top=;
for(int k=;k<=n;k++){
tmp+=smm[k][j]-smm[k][i-];
if(tmp>)ans=max(ans,(j-i+)*k);
else{
int pos=find(tmp);
if(pos!=-)
ans=max(ans,(k-f[pos])*(j-i+));
}
if(tmp<st[top]){
st[++top]=tmp;
f[top]=k;
}
}
}
printf("%d\n",ans);
return ;
}