codeforces#FF(div2) D DZY Loves Modification_html/css_WEB-ITnose

まず第一に、行と列を選択するときに順序は無関係であることを知っておく必要があります

2 つの配列 row[i] とcol[j] を使用して、行 i のみを選択して取得できる最大値と最大値を表します列 j のみを選択することで取得できる値

これは、行 (列) が選択されなかった後、行 (列) から対応する np (mp) を引いた合計が再び追加されます。キュー

選択された行が i 回列挙され、その列が選択されます。回数は k - i 回、ans = row[i] +col[k - i] - (k - i) * i * p;

順序は重要ではないので、最初に i 行を選択し、その後毎回列を選択するたびに、i * p を減算する必要があります k - i 列を選択します。つまり、減算 (k - i) * i * p

//#pragma comment(linker, "/STACK:102400000,102400000")//HEAD#include <cstdio>#include <cstring>#include <vector>#include <iostream>#include <algorithm>#include <queue>#include <string>#include <set>#include <stack>#include <map>#include <cmath>#include <cstdlib>using namespace std;//LOOP#define FE(i, a, b) for(int i = (a); i <= (b); ++i)#define FED(i, b, a) for(int i = (b); i>= (a); --i)#define REP(i, N) for(int i = 0; i < (N); ++i)#define CLR(A,value) memset(A,value,sizeof(A))//STL#define PB push_back//INPUT#define RI(n) scanf("%d", &n)#define RII(n, m) scanf("%d%d", &n, &m)#define RIII(n, m, k) scanf("%d%d%d", &n, &m, &k)#define RS(s) scanf("%s", s)#define FF(i, a, b) for(int i = (a); i < (b); ++i)#define FD(i, b, a) for(int i = (b) - 1; i >= (a); --i)#define CPY(a, b) memcpy(a, b, sizeof(a))#define FC(it, c) for(__typeof((c).begin()) it = (c).begin(); it != (c).end(); it++)#define EQ(a, b) (fabs((a) - (b)) <= 1e-10)#define ALL(c) (c).begin(), (c).end()#define SZ(V) (int)V.size()#define RIV(n, m, k, p) scanf("%d%d%d%d", &n, &m, &k, &p)#define RV(n, m, k, p, q) scanf("%d%d%d%d%d", &n, &m, &k, &p, &q)#define WI(n) printf("%d\n", n)#define WS(s) printf("%s\n", s)#define sqr(x) x * xtypedef vector <int> VI;typedef unsigned long long ULL;typedef long long LL;const int INF = 0x3f3f3f3f;const int maxn = 1010;const double eps = 1e-10;const LL MOD = 1e9 + 7;int ipt[maxn][maxn];LL row[maxn * maxn], col[maxn * maxn];LL rtol[maxn], ctol[maxn];int main(){    int n, m, k, p;    while (~RIV(n, m, k, p))    {        priority_queue<LL> r, c;        int radd = 0, cadd = 0;        CLR(rtol, 0), CLR(ctol, 0);        FE(i, 1, n)            FE(j, 1, m)            {                RI(ipt[i][j]);                rtol[i] += ipt[i][j];                ctol[j] += ipt[i][j];            }        FE(i, 1, n)            r.push(rtol[i]);        FE(j, 1, m)            c.push(ctol[j]);        row[0] = 0, col[0] = 0;        FE(i, 1, k)        {            LL x = r.top(), y = c.top();             r.pop(), c.pop();            r.push(x - m * p);            c.push(y - n * p);            row[i] = row[i - 1] + x;            col[i] = col[i - 1] + y;        }//        FE(i, 0, k)//            cout << row[i] + col[k - i] <<endl;        LL ans = -1e18;        FE(i, 0, k)            ans = max(ans, row[i] + col[k - i] - (LL)i * (k - i)* p);        cout << ans << endl;    }    return 0;}/*2 2 4 21 2 3 102 3 5 22 2 22 2 2*/