DZY Loves Modification

题面

给出一个 $n\times m$ 的矩阵，并进行 $k$ 次操作，每次操作将矩阵的一行或一列的所有元素的值减 $p$ ，得到的分数为这次修改之前这一列 / 一行的元素和，求分数最大值。

$n,m\le 10^3$ , $a_{i,j}\le10^3$ , $k\le 10^6$ , $p\le 100$

题解

以减去一行为例，减去一行相当于这一行的和减去 $m\times p$ ，所有列减去 $p$ 。既然所有列都减了，那相当于行和列的操作是独立的。贪心即可。

代码

const int N = 1e3 + 5, M = 1e6 + 5;

inline ll Read() {
    ll x = 0, f = 1;
    char c = getchar();
    while (c != '-' && (c < '0' || c > '9')) c = getchar();
    if (c == '-')
        f = -f, c = getchar();
    while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
    return x * f;
}

namespace Main {
int n, m, k, p;
ll a[N][N], r[N], c[N];
priority_queue<ll> row, col;
ll ans = -(1ll << 60), rs[M], cs[M];
int main() {
    n = Read(), m = Read(), k = Read(), p = Read();
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) r[i] += (a[i][j] = Read());
        row.push(r[i]);
    }
    for (int j = 1; j <= m; j++) {
        for (int i = 1; i <= n; i++) c[j] += a[i][j];
        col.push(c[j]);
    }
    for (int i = 1; i <= k; i++) {
        int v = row.top();
        row.pop();
        rs[i] = rs[i - 1] + v;
        row.push(v - p * m);

        v = col.top();
        col.pop();
        cs[i] = cs[i - 1] + v;
        col.push(v - p * n);
    }
    for (ll i = 0; i <= k; i++) {
        ans = max(ans, rs[i] + cs[k - i] - (k - i) * i * p);
    }
    printf("%lld\n", ans);
    return 0;
}
}  // namespace Main

int main() {
    freopen("matrix.in", "r", stdin);
    freopen("matrix.out", "w", stdout);
    Main::main();
    return 0;
}