E
0.9 seconds, 32 MB “ 于是乎，你至少证明了你智商比金天成高。也就说你证明了你不是低智儿童，不错不错。 然而这次， 我貌似也卡住了，你给我打下手吧。勇敢的少年啊快去创造奇迹！”
——-By Doctor Z 貌似 Z 博士正在解析 Zvangelion 初号机的一些问题。 中间遇到了困难。 Zvangelion 初号机有一块 R*S 的电路模块被某种 UMA 感染了。 为了方便我们用整数 描写叙述每一个单元的零件， 即用一个整数矩阵来表示该模块。 这样的 UMA 的习性是，假设一块 N*M 的模块 S 被感染了(N,M>1)。 那么它必定会让第 (1,1)(N,1)(1,M)和(N,M)上的元件保持（ 意味着假设该电路被各种修改，都会满足） 以 下关系：（ UMA 仅仅会感染至少 2 行且至少 2 列的电路模块） a[1][1] + a[N][M] ≤a[1][M] + a[N][1] (注:a[i][j]表示矩阵中第 i 行第 j 列的数值) 然而， 谁说的一块电路不会被反复感染？ 当一块电路被反复感染到，随意一个子电路模 块（即矩阵的一个子矩阵所表示的电路）都被感染了。那么这块电路就会发生可怕的事情， 对的， 就是异变！（ 正确讲法应该是使徒化） Z 博士须要知道， 这个 R*S 的电路模块中， 面积最大的有异变（ 使徒化） 嫌疑的子电 路模块的面积是多少？ 【 输入】 第一行两个正整数 R 和 S(2≤R,S≤1000)。表示 Zvangelion 的电路模块大小。 下接一个 R 行 S 列的矩阵， 用整数来描写叙述电路模块内 R*S 个电路单元上的元件。描写叙述所用
的整数分布在[-1000000,1000000]内。【 输出】 面积最大的有异变（使徒化）嫌疑的子电路模块的面积。
假设没有则请输出 0.
【 測试例子】 Input 3 3 1 4 10 5 2 6 11 1 3 Output 9 Input 3 3 1 3 1 2 1 2 1 1 1 Output 4 Input 5 6 1 1 4 0 3 3 4 4 9 7 11 13 -3 -1 4 2 8 11 1 5 9 5 9 10 4 8 10 5 8 8 Output 15 着重解释第二个測试例子。假设整个电路模块都有变异嫌疑，那么要求的是 3*3 的矩 阵 1 个。 2*2 的矩阵共 4 个都满足被感染的条件。然而观察发现左下角和右上角的 2*2 矩
阵并不满足要求。所以最大的面积既不可能是 9（ 3*3），也不可能是 6（ 2*3 或 3*2）， 然 后左上角的 2*2 矩阵有变异嫌疑。故最大面积为 4（ 2*2）。第三个測试例子的变异模块为
从(3,2)開始一直到（ 5,6）结束的子模块。 測试数据范围： 有 60%的数据满足 R、 S≤350对于感染的条件，我们能够发现一个性质：
a b c d e f 假设1.a+e<=b+d => a-b<=d-e 2.b+f<=c+e => b-c<=e-f 能够推出a-c<=d-f =>a+f<=c+d 这样一来这道题就能简化成一个求最大全零矩阵的问题。 对于1到r-1，1到s-1的点假设以它为左上方点的2*2矩阵为符合要求。就把这个点标记为0。否则就为1。然后就生成了长r-1，宽s-1的矩阵，答案就是最大的全0矩阵。#include#include #define maxl 1001int r,s,ans=0;int a[maxl][maxl];int f[maxl][maxl],h[maxl],l[maxl],rr[maxl];void prework(){ freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); scanf("%d%d",&r,&s); for(int i=1;i<=r;i++) for(int j=1;j<=s;j++) scanf("%d",&a[i][j]);}void mainwork(){ for(int i=1;i<=r-1;i++) for(int j=1;j<=s-1;j++) if(a[i][j]+a[i+1][j+1]<=a[i+1][j]+a[i][j+1]) f[i][j]=0; else f[i][j]=1; for(int i=1;i<=r-1;i++) { for(int j=1;j<=s-1;j++) //h[j]表示第i行第j列向上有多少个连续的0 ，以下枚举的矩阵就是以h[j]为高度 { if(f[i][j]==0) h[j]++; else h[j]=0; //这一个是1就不能往下延续长度了 } for(int j=1;j<=s-1;j++) { l[j]=j; //先假设这个高度为h[j]矩阵的左的边就是j while(l[j]>1 && h[j]<=h[l[j]-1])//假设h[j]是小于h[l[j]-1],l[j]直接拓展到 l[l[j]-1] l[j]=l[l[j]-1]; //由于l[l[j]-1]是已经拓展过的对l[j]-1来说最左边的边，肯定是已经符合了要求的 } for(int j=s-1;j>=1;j--) //和拓展左区间一样的做法 { rr[j]=j; while(rr[j]