题意简述

给定一个矩阵，求出和非负的最大子矩阵。

分析

据说本题正解为 $O(n^3 \log n)$ 的，二维前缀和+二分。
但是我太蒻了，怎么办呢？
那么我们就打 $O(n^4)$ 的暴力吧，看数据范围卡卡能A。

枚举时，我们要枚举左上角的坐标和右下角的坐标，显然时间复杂度已经来到了 $O(n^4)$。
那么，我们就要想一个 $O(1)$ 的方法判断某个子矩阵是否非负。

那么，我们就可以使用二维前缀和了。其实就是一维前缀和的升级版，还是很好理解的。可以去看这篇百科：前缀和 & 差分

于是，我们飞快地打出了这份代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
long long a[201][201], sum[201][201];

int main(){
	int n, m;
	cin >> n >> m;
	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			cin >> a[i][j];
		}
	}
	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			sum[i][j] = sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];
		}
	}
	long long ans=0;
	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			for(int k=1; k<=n; k++){
				for(int l=1; l<=m; l++){
					if(sum[i][j]-sum[i][l-1]-sum[k-1][j]+sum[k-1][l-1]>0&&(long long)(i-k+1)*(j-l+1)>=ans){
						ans = (long long)(i-k+1)*(j-l+1);
					}
				}
			}
		}
	}
	cout << ans;
	
	return 0;
}

先别急，这玩意T了。那么，我们就开始愉快（误）地卡一下常吧~
我们可以默认 $(i,j)$ 在右下角，$(k,l)$ 在左上角当然倒一倒也是可以的。无需判断 $(i,j)$ 在右上角，$(k,l)$ 在左下角之类的情况，这样每个矩形会且只会被判断一次。这样，我们大约卡了一个 $\frac{1}{4}$ 的常数，速度瞬间飞起。
AC Code（1.50s,1.03MB）：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
long long a[201][201], sum[201][201];

int main(){
	int n, m;
	cin >> n >> m;
	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			cin >> a[i][j];
		}
	}
	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			sum[i][j] = sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];
		}
	}
	long long ans=0;
	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			for(int k=1; k<=i; k++){
				for(int l=1; l<=j; l++){
					if(sum[i][j]-sum[i][l-1]-sum[k-1][j]+sum[k-1][l-1]>0&&(long long)(i-k+1)*(j-l+1)>=ans){
						ans = (long long)(i-k+1)*(j-l+1);
					}
				}
			}
		}
	}
	cout << ans;
	
	return 0;
}

vocal我刚才才发现一个厉害的事情，我这份代码在洛谷上的评测号是 R154314159，末6位是圆周率啊！！！我运气真好！！！