题目描述

AP 神牛准备给自己盖一座很华丽的宫殿。于是，他看中了一块N*M 的矩形空地。

空地中每个格子都有自己的海拔高度。AP 想让他的宫殿的平均海拔在海平面之上（假设

海平面的高度是0，平均数都会算吧？）。而且，AP 希望他的宫殿尽量大，能够容纳更

多的人来膜拜他。请问AP 的宫殿最后会有多大？

输入输出格式

输入格式：

 

第一行为N 和M。之后N 行，每行M 个数，描述的空地的海拔。

 

输出格式：

 

输出一行,表示宫殿最大面积。

 

输入输出样例

输入样例#1：

3 24 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了一片

1 /*by SilverN*/ 2 #include
     
       3 #include
      
        4 #include
       
         5 #include
        
          6 #include
         
           7 #include
          
            8 #define LL long long 9 using namespace std;10 const int mxn=310;11 int read(){12 int x=0,f=1;char ch=getchar();13 while(ch<'0' || ch>'9'){ if(ch=='-')f=-1;ch=getchar();}14 while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}15 return x*f;16 }17 int a[mxn][mxn];18 LL smm[mxn][mxn];19 int n,m;20 int ans=0;21 int f[mxn];22 LL st[mxn];23 int top=0;24 int find(LL x){25 int l=1,r=top,w=-1;26 while(l<=r){27 int mid=(l+r)>>1;28 if(st[mid]
           
            0)ans=max(ans,(j-i+1)*k);49 else{50 int pos=find(tmp);51 if(pos!=-1)52 ans=max(ans,(k-f[pos])*(j-i+1));53 }54 if(tmp