[CF446B] DZY Loves Modification

[CF446B] DZY Loves Modification - 堆

Description

(N imes M (N,M le 10^3)) 的矩阵，你需要进行恰好 (K (le 10^6)) 次操作。每次操作你可以选择其中一行或者其中一列，将其中的元素全部累加得分。然后把选中的这些数全部减去 (P)。求最大得分。

Solution

枚举选 (x,y) 次行、列操作，那么答案就是行列分别操作 (x,y) 次单独贡献的最大值的和减去 (pxy)

单独计算的时候用堆维护一下即可

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

#define int long long

int n, m, k, p;

int a[1005][1005];

priority_queue<int> que_row, que_col;
vector<int> f_row, f_col;

signed main()
{
    ios::sync_with_stdio(false);

    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++)
    {
        int sum = 0;
        for (int j = 1; j <= m; j++)
            sum += a[i][j];
        que_row.push(sum);
    }

    for (int j = 1; j <= m; j++)
    {
        int sum = 0;
        for (int i = 1; i <= n; i++)
            sum += a[i][j];
        que_col.push(sum);
    }

    f_row.push_back(0);
    f_col.push_back(0);

    for (int i = 1; i <= k; i++)
    {
        int tmp = que_row.top();
        que_row.pop();
        f_row.push_back(tmp);
        tmp -= m * p;
        que_row.push(tmp);
    }

    for (int i = 1; i <= k; i++)
    {
        int tmp = que_col.top();
        que_col.pop();
        f_col.push_back(tmp);
        tmp -= n * p;
        que_col.push(tmp);
    }

    for (int i = 1; i < f_row.size(); i++)
        f_row[i] += f_row[i - 1];
    for (int i = 1; i < f_col.size(); i++)
        f_col[i] += f_col[i - 1];

    int ans = -1e18;
    for (int i = 0; i <= k; i++)
    {
        int x = i, y = k - i;
        if (x >= f_row.size())
            continue;
        if (y >= f_col.size())
            continue;
        ans = max(ans, f_row[x] + f_col[y] - x * y * p);
    }

    cout << ans << endl;
}