【codecomb2093】牛宫

2014年10月15日1,9130

Description

Hzgd神牛准备给自己盖一座很华丽的宫殿。于是,他看中了一块N*M的矩形空地。空地中每个格子都有自己的海拔高度。胡张想让他的宫殿的平均海拔在海平面之上(假设海平面的高度是0,平均数都会算吧?)。而且,胡张希望他的宫殿是个矩形且尽量大,能够容纳更多的人来膜拜他。请问胡张的宫殿最后会有多大?

Input Format

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

Output Format

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

Sample Output

Data Limit

对于30%的数据,N,M≤50;

对于100%的数据,N,M≤200;

题解

先n^2枚举矩形的左右两边l-r,然后在行上找最值

我们可以得到前i行l-r的总和。。记为si

如果si>sj且i>j则(i-j)*(r-l+1)可以更新答案

维护单调递减栈每次在其中二分找j

或者将si为关键字排序,然后扫描一遍边维护i的最小值边更新答案

复杂度都是n^3logn