long

題目描述

AP神牛準(zhǔn)備給自己蓋一座很華麗的宮殿。于是，他看中了一塊N*M的矩形空地?？盏刂忻總€(gè)格子都有自己的海拔高度。AP想讓他的宮殿的平均海拔在海平面之上（假設(shè)海平面的高度是0，平均數(shù)都會(huì)算吧？）。而且，AP希望他的宮殿盡量大，能夠容納更多的人來膜拜他。請問AP的宮殿最后會(huì)有多大？

輸入輸出

輸入
第一行為N和M。之后N行，每行M個(gè)數(shù)，描述的空地的海拔。
輸出
輸出一行,表示宮殿最大面積。

樣例

樣例輸入

3 2
4 0
-10 8
-2 -2

樣例輸出

4

說明

數(shù)據(jù)范圍
對于30%的數(shù)據(jù)，N,M≤50;
對于100%的數(shù)據(jù)，N,M≤200；

思路

1. 用前綴和a[i][j]表示第i行1~j列的和
2. 開一個(gè)單調(diào)棧，存海拔之和
3. a[k][j]-a[k][q]代表第k行第q列到第j列的海拔高度和
4. 當(dāng)s<0時(shí)，設(shè)s=p (p<0),在棧中尋找p所對應(yīng)的f[p],
5. 用當(dāng)前行數(shù)k減去f[p]，即可得到一段平均海拔在海平面之上的區(qū)間。

代碼

#include<cstdio>
#include<iostream>
using namespace std;
long long n,m,x,a[201][201],f[201],sta[201],size,ans;
inline long long erfen(long long u) {
    long long l=1,r=size,tot=-1;
    while(l<=r) {
        long long mid=(l+r)>>1;
        if(sta[mid]<u) {
            r=mid-1;
            tot=mid;
        } else l=mid+1;
    }
    return tot;
}
inline int read() {
    long long x=0,w=1;
    char ch=0;
    while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
    if(ch=='-') w=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-48,ch=getchar();
    return x*w;
}
int main() {
    freopen("long.in","r",stdin);
    freopen("long.out","w",stdout);
    n=read();
    m=read();
    for(long long i=1; i<=n; i++)
        for(long long j=1; j<=m; j++) {
            x=read();
            a[i][j]=a[i][j-1]+x;
        }
    for(long long i=1; i<=m; i++)
        for(long long j=1; j<=m; j++) {
            long long s=0;
            sta[0]=1e10;
            size=0;
            for(long long k=1; k<=n; k++) {
                s+=a[k][j]-a[k][i-1];
                if(s>0) ans=max(ans,k*(j-i+1));
                else {
                    int z=erfen(s);
                    if(z!=-1) ans=max(ans,(j-i+1)*(k-f[z]));
                }
                if(sta[size]>s) sta[++size]=s,f[size]=k;
            }
        }
    printf("%lld\n",ans);
    return 0;
}