这是榜上第二名的做法，时间复杂度为 $O(nm)$（假如去掉不必要的 set 和排序）。

这份做法爆标了 std（复杂度为 $O(nm \sqrt{nm})$），但是我认为它是有问题的，但是很难将其 hack 掉。

它与其他做法不同的地方，在于 两行+两列的情况。

它首先枚举了 $i,j$ 两行。

然后，令 $s_i$ 表示第 $i$ 行的总和。

令 $f_{i,k}$ 表示 $s_i - a_{i,k}$。

它只分别考虑使得 $f_{i,k}$ 最大的两个 $k$，以及 $f_{j,k}$ 最大的两个 $k$（总共 $4$ 个可能的 $k$），然后从中选择两个，作为选择的两列。

我认为这个部分是错误的，并且构造了 Hack：

3 6
1 1 100 100 20 20 
0 0 0 0 30 30 
100 100 1 1 20 20

答案是 544.

按照这份代码的想法，它会选择 $1,3$ 两行，以及在 $1,2,3,4$ 列中选择两列。

但是最优答案实际上是 $1,3$ 两行加上 $5,6$ 两行。

我输出了中间值，确定成功 Hack 了本情况。

但是，这份做法的其他情况（比如说，选择一行三列，三行一列，四行）又求出了全局最优解。

我又尝试修改 hack，仍然无法完成 hack。

求助大佬们。

如果这份代码是正确的，那么求证明。

/bx/bx/bx/bx/bx

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n, m;
vector<vector<ll>> a;
vector<pair<ll,ll>>cols,rows;
vector<ll>col,row;
vector<vector<pair<ll,ll>>>bsc,bsr;
ll ans, tmp[5];

int main() {
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
#endif
	cin >> n >> m;
	rows.resize(n);
	cols.resize(m);

	row.resize(n);
	col.resize(m);
	for(int j = 0; j < m; ++j) cols[j] = {0,j};
	for(int j = 0; j < m; ++j) col[j] = 0;
	for(int i = 0; i < n; ++i) {
		a.push_back({});
		rows[i] = {0,i};
		row[i]=0;
		for(int j = 0; j < m; ++j) {
			int tmp;
			scanf("%d", &tmp);
			cols[j].first += tmp;
			rows[i].first += tmp;
			a[i].push_back(tmp);
			col[j]+=tmp;
			row[i]+=tmp;
		}
	}
	if(n <= 4 || m <= 4){
		for(int i = 0; i < n; ++i)
			for(int j = 0; j < m; ++j)
				ans += a[i][j];
		cout << ans;
		return 0;
	}
	bsr.resize(n);
	bsc.resize(m);
	for(int i = 0; i < n; ++i)bsr[i].resize(m);
	for(int j = 0; j < m; ++j)bsc[j].resize(n);
	for(int i = 0; i < n; ++i)
		for(int j = 0; j < m; ++j){
			bsr[i][j]={rows[i].first+cols[j].first-a[i][j],j};
			bsc[j][i]={rows[i].first+cols[j].first-a[i][j],i};
		}
	for(int i = 0; i < n; ++i)sort(bsr[i].rbegin(),bsr[i].rend());
	for(int j = 0 ; j < m; ++j)sort(bsc[j].rbegin(),bsc[j].rend());
	sort(col.rbegin(), col.rend());
	sort(row.rbegin(), row.rend());
	for(int i = 0; i < 4; ++i)tmp[0]+=col[i],tmp[4]+=row[i];
	ans = max(ans, tmp[0]);
	ans = max(ans, tmp[4]);
	for(int i = 0; i < n; ++i) {
		tmp[1] = -rows[i].first*2;
		for(int j = 0; j < 3;++j)tmp[1]+=bsr[i][j].first;
		ans = max(ans, tmp[1]);
	}
	for(int i = 0; i < m; ++i) {
		tmp[3] = -cols[i].first*2;
		for(int j = 0; j < 3;++j)tmp[3]+=bsc[i][j].first;
		ans = max(ans, tmp[3]);
	}
	if(n < m) {
		for(int i = 0; i < n; ++i)
			for(int j = i + 1; j < n; ++j) {
				int cnd[4];
				for(int k = 0; k < 2; ++k){
					cnd[k]=bsr[i][k].second;
					cnd[k+2]=bsr[j][k].second;
				}
				set<int>e,q;
				for(int k = 0; k < 4; ++k)e.insert(cnd[k]);

				for(int k:e){
					q.insert(a[i][k]+a[j][k]-cols[k].first);
				}
				ll tmpp=rows[i].first+rows[j].first-*q.begin();
				q.erase(q.begin());
				tmpp-=*q.begin();
				tmp[2]=max(tmp[2],tmpp);
			}
	}
	else {
		for(int i = 0; i < m; ++i)
			for(int j = i + 1; j < m; ++j) {
				int cnd[4];
				for(int k = 0; k < 2; ++k){
					cnd[k]=bsc[i][k].second;
					cnd[k+2]=bsc[j][k].second;
				}
				set<int>e,q;
				for(int k = 0; k < 4; ++k)e.insert(cnd[k]);

				for(int k:e){
					q.insert(a[k][i]+a[k][j]-rows[k].first);
				}
				ll tmpp=cols[i].first+cols[j].first-*q.begin();
				q.erase(q.begin());
				tmpp-=*q.begin();
				tmp[2]=max(tmp[2],tmpp);
			}
	}
	ans = max(ans, tmp[2]);
	cout << ans;
}