# DZY Loves Modification

## 题目描述

As we know, DZY loves playing games. One day DZY decided to play with a $n \times m$ matrix. To be more precise, he decided to modify the matrix with exactly $k$ operations.
Each modification is one of the following:

• Pick some row of the matrix and decrease each element of the row by $p$. This operation brings to DZY the value of pleasure equal to the sum of elements of the row before the decreasing.
• Pick some column of the matrix and decrease each element of the column by $p$. This operation brings to DZY the value of pleasure equal to the sum of elements of the column before the decreasing.

DZY wants to know: what is the largest total value of pleasure he could get after performing exactly $k$ modifications? Please, help him to calculate this value.

## 代码

#include <iostream>
#include <queue>
using namespace std;
priority_queue<long long> r, c;
long long n, m, k, p, s, t, ans = -1e18, a[1001][1001], rr[1000001], cc[1000001];
int main()
{
cin >> n >> m >> k >> p;
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) {
long long s = 0;
for (int j = 1; j <= m; ++j) s += a[i][j];
r.push(s);
}
for (int j = 1; j <= m; ++j) {
long long s = 0;
for (int i = 1; i <= n; ++i) s += a[i][j];
c.push(s);
}
for (int i = 1; i <= k; ++i) {
long long u = r.top(); r.pop();
rr[i] = rr[i - 1] + u;
r.push(u - p * m);
u = c.top(); c.pop();
cc[i] = cc[i - 1] + u;
c.push(u - p * n);
}
for (int i = 0; i <= k; ++i) ans = max(ans, rr[i] + cc[k - i] - p * i * (k - i));
cout << ans << endl;
return 0;
}


418 I'm a teapot