#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=3005 ;
ll a[N][N];
ll r[N],c[N];
ll b[N*N];
int main() {
	int n,m,k;
	cin>>n>>m>>k;
	for(int i=0; i<n; i++)
		for(int j=0; j<m; j++)
			cin>>a[i][j];
	for(int i=0; i<n; i++)
		for(int j=0; j<m; j++) {
			r[i]+=a[i][j];
			c[j]+=a[i][j];
		}
	int cnt=0;
	for(int i=0; i<n; i++)
		for(int j=0; j<m; j++)
			b[cnt++]=r[i]+c[j]-a[i][j];
	sort(b, b+cnt, greater<ll>());
	ll res=0;
	for(int i=0; i<k; i++)
		res+=max(b[i],0ll);
	cout<<res<<endl;
	return 0;
}

思路

预处理出每行数的和 $r$，每列数的和 $c$，之后把每个十字架形的和存储在一个数组中（$sum=r_i+c_j-a_{i,j}$），最后把前 $k$ 大且大于 $0$ 的加起来即可得到答案。

代码

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

typedef long long ll;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const int N = 3e3 + 10;
ll a[N][N], r[N], c[N], sum[1000010];
int n, m, k, cnt;

int main() {
	scanf("%d%d%d", &n, &m, &k);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			scanf("%lld", &a[i][j]);
			r[i] += a[i][j];
			c[j] += a[i][j];
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			ll now = r[i] + c[j] - a[i][j];
			if (now >= 0) sum[++cnt] = now;
		}
	}
	sort(sum + 1, sum + cnt + 1);
	ll ans = 0;
	for (int i = cnt; i >= max(1, cnt - k + 1); i--) {
		if (sum[i] >= 0) {
			ans += sum[i];
		}
	}
	printf("%lld", ans);
    return 0;
}