原题：
取数游戏
描述

现在你的面前有一个 N*M 的矩阵，你需要进行恰好 K 次操作。每次 操作你可以选择其中一行或者其中一列，将其中的元素全部累加到 ans 里 去，然后把选中的这些数全部减去 P。问 ans 最大是多少。

输入
第一行一共四个数，分别为: N,M,K,P .

接下来给出一个 N 行 M 列的矩阵 Ai,j。

N,M ≤ 1000,K ≤ 100000 , 0 ≤ P ≤ 100 , 1 ≤ Ai,j ≤ 1000。

输出
一共一行，一个整数表示 ans_max .

输入样例 1

2 2 2 2
1 3
2 4
输出样例 1

11

思路题解：
标签 模拟
这道题很多人应该和我一样是模拟出来了的，我一开始的代码是每次用sort排序，然后取某行或某列和的最大值，再将该行或该列的值减去P，然后反复做，结果发现时间差不多在2s左右，题目要求是1s，问题来了就是如何优化。

数据结构——优先队列
在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。
默认优先级：从大到小排序。（故本题不需要改动，直接拿来用即可）
头文件在queue中
定义方式：priority_quue<数据类型>队列名;

q.push(x) 把x放入优先队列q中
q.pop(x) 把x弹出优先队列q中
q.top() 优先队列q队头（队列中优先级最高的元素）
q.empty() 判断队列是否为空，若为空返回true，返之flase

#include <queue>
priority_queue<ll>q;//定义名为q类型为ll的优先队列

//优先队列
for(int i=1;i<=m;i++) q.push(list[i]);//将各列的和放入优先队列中
    for(int i=1;i<=k;i++)
    {
        ll tmp=q.top();q.pop();
        y[i]=y[i-1]+tmp;
        tmp-=1ll*n*p;
        q.push(tmp);
    }
    while(!q.empty()) q.pop();
    for(int i=1;i<=n;i++) q.push(line[i]);
    for(int i=1;i<=k;i++)
    {
        ll tmp=q.top();q.pop();
        x[i]=x[i-1]+tmp;
        tmp-=1ll*m*p;
        q.push(tmp);
    }

##核心：
打破数据行和列的区别
先对行和列在1到k的范围内分别求解，然后求出一个满足i和k-i的最大值，
注意1：结果会减去反复计算的，数据会爆int，这里用long long。
注意2：横向与纵向操作会有相交的部分，每相交一次就减去p ，总共减去 i∗(k−i)∗p 。
注意3：因为可能最终答案为一个很小的负数，ans初值要足够小，取-1e18。

AC代码

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;

typedef long long ll;

int n,m,k,p;
ll a[1005][1005];//虽然1 ≤ Ai,j ≤ 1000，但后面会减去足够多次的p，会爆int，所也用long long
ll line[1005],list[1005]; 
ll ans=-1e18;//ans足够小 防止答案为很小的负数（倘若不够小 则无法取max取到答案 而取ans的初值
ll x[1000005],y[1000005];
priority_queue<ll>q;

int main(){
	scanf("%d%d%d%d",&n,&m,&k,&p);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			scanf("%lld",&a[i][j]);
		}
	}
	//求各行各列的和
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
		    line[i]+=a[i][j];
		    list[j]+=a[i][j];
		}		
	}
    
    for(int i=1;i<=m;i++) q.push(list[i]);
    for(int i=1;i<=k;i++)
    {
        ll tmp=q.top();q.pop();
        y[i]=y[i-1]+tmp;
        tmp-=1ll*n*p;
        q.push(tmp);
    }
    while(!q.empty()) q.pop();
    for(int i=1;i<=n;i++) q.push(line[i]);
    for(int i=1;i<=k;i++)
    {
        ll tmp=q.top();q.pop();
        x[i]=x[i-1]+tmp;
        tmp-=1ll*m*p;
        q.push(tmp);
    }
	for(int i=0;i<=k;i++){//核心部分打破行与列的区别 上面将行和列分开取 下面将取不同行数和列数的最大值取出
		ans=max(ans,x[i]+y[k-i]-1ll*i*(k-i)*p);
	}	
	cout<<ans<<endl;	
	return 0;
}