## 题目描述

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.

## 题意概述

给定一个$n \times m$的矩阵，每次可以从这个矩阵中选取一行或一列，将这一行或一列的数字之和加到你的分数上，再将这一行或一列上的每个数字减去$p$。共进行$k$次操作，求分数的最大值。

数据范围：$1 \le n, m \le 1000, \; 1 \le k \le 10^6, \; 1 \le p \le 100$。

## 算法分析

可以发现交换操作顺序对答案没有影响。因此，可以先计算出只取$i$行可以得到的最大值以及只取$j$列可以得到的最大值，根据贪心策略，可以用优先队列维护一行或一列的数字之和。接着枚举取了$i$行，那么也就取了$(k-i)$列，减去重复部分，取最大值，即可得到答案。

## 代码

#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; }