给定一个n * mn∗m的矩阵，将对矩阵进行k次操作。每次可以进行如下某一种操作：
1.将某行的元素相加作为快乐值，然后将该行元素都减去p。
2.将某列的元素相加作为快乐值，然后将该列元素都减去p。
问k次之后快乐值总和的最大值是多少？
输入
第一行输入四个整数n, m, k, p (1 \le n, m \le 10^3, 1 \le k \le 10^6, 1 \le p \le 10^2)n,m,k,p(1≤n,m≤103,1≤k≤106,1≤p≤102)。
接下来n行，每行m个整数表示矩阵。
矩阵中的元素属于区间[1, 10^3][1,103]。
输出
输出最大快乐值总和。
样例
输入
复制
2 2 2 2
1 3
2 4 输出
复制
11 提示
先对第二列操作，然后对第二行操作
最后矩阵变成
1 1
0 0
子任务1，20分，2 \le n + m \le 10, 1 \le k \le 32≤n+m≤10,1≤k≤3。
子任务2， 80分，1 \le n, m \le 10^3, 1 \le k \le 10^61≤n,m≤103,1≤k≤106。
先找行还是先找列都是一样的，因为对行操作后，对列的和产生的影响是一样，反之也是如此，枚举所有的可能，找所有和的和最大的。
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <vector>
#include <algorithm>
#include <functional>
#define inf 0x3f3f3f3f
int main()
{
int n, m, d, k, p;
scanf("%d %d %d %d", &n, &m, &k, &p);
std::vector<int> rsum(n, 0);
std::vector<int> csum(m, 0);
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
scanf("%d", &d);
rsum[i] += d;
csum[j] += d;
}
}
std::vector<long long> sum(k + 1, 0);
std::priority_queue<long long, std::vector<long long>, std::less<long long>> qr, qc;
for (int i = 0; i < n; i++)
{
qr.push(rsum[i]);
}
for (int i = 0; i < m; i++)
{
qc.push(csum[i]);
}
long long ssumr = 0, ssumc = 0, temp;
for (int i = 1; i <= k; i++)
{
temp = qr.top();
qr.pop();
qr.push(temp - m * p);
ssumr += temp;
sum[i] += ssumr;
temp = qc.top();
qc.pop();
qc.push(temp - n * p);
ssumc += temp;
sum[k - i] += ssumc;
if (i * 2 <= k)
{
temp = (long long)i * (k - i) * p;
sum[i] -= temp;
if (i != k - i) sum[k - i] -= temp;
}
}
long long ans = sum[0];
for (int i = 1; i <= k; i++)
{
if (sum[i] > ans)
{
ans = sum[i];
}
}
printf("%lld", ans);
return 0;
}