codeforces 255#D. DZY Loves Modification

题意： 给n*m 的矩阵，每次操作为选取一行或者一列，val= sum{这些元素}，然后每个元素减p,,,,求K次操作的val最大；

明天要val 最大，每次选取 当前行或者列的和最大的那个；

如果一一枚举，显然 10^ 6 * 2*10^3 ，然后超时；所以先处理好第i 次操作行的最大值，及第i次操作列的最大值；

为什么选取行的和最大互不影响选取列的和最大呢？ 选取一行后，每一列的和都减去了p ，所以不影响最初的大小；只需要最后修改一下列的和；等于最初列的和 减去 i*(k-i) *p;

解释: 选取一行 对一列和的影响是 1*i*p; 

      选取i 行，对(k-i) 列的和的影响是 i*（k-i）*p;

for(i=0 ;i<=k ;i++)  ans=max（ans, row[i] + col[k-i] - i*(k-i) *p;

利用堆排序： make_heap(起始地址，终止地址)； pop_heap() 把堆的根放到 容器末尾； 用v.pop_ back（） 才可以真正的删除；

维护堆的时候，每插入一个元素，执行push_heap();

注意考虑范围： 如果最初a[i][j]=1，那么最大减去是 kmax/2  * kmanx/2  * pmax =5*10^5 * *5*10^5 *100 ~ = 10 ^13; 超过int ;

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<string>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<list>
#include<map>
#include<set>
using namespace std;
const int N=1010;
const int M=1000100;
int n,m,k,p;

int a[N][N];
long long DpRow[M];
long long DpCol[M];
vector<long long>row;
vector<long long>col;
void deal(){
     for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
           scanf("%d",&a[i][j]);
     row.clear();
     col.clear();

     long long tp;
     for(int i=0;i<n;i++){
        tp=0;
        for(int j=0;j<m;j++) tp+=a[i][j];
        row.push_back(tp);
     }
     make_heap(row.begin(),row.end());

     for(int j=0;j<m;j++){
        tp=0;
        for(int i=0;i<n;i++) tp+=a[i][j];
        col.push_back(tp);
     }
     make_heap(col.begin(),col.end());

     DpRow[0]=0;
     for(int i=1;i<=k;i++){
        tp=row[0];
        DpRow[i]=DpRow[i-1]+tp;
        pop_heap(row.begin(),row.end());
        *(row.end()-1)=tp-p*m;
        push_heap(row.begin(),row.end());
     }
     DpCol[0]=0;

     for(int i=1;i<=k;i++){
        tp=col[0];
        DpCol[i]=DpCol[i-1]+tp;
        pop_heap(col.begin(),col.end());
        *(col.end()-1)=tp-p*n;
        push_heap(col.begin(),col.end());
     }

     long long ans=-(1ll<<60);
     for(int i=0;i<=k;i++){
        ans=max(ans,DpRow[i]+DpCol[k-i]- (1ll*i)*(k-i)*p);
     }
     cout << ans << endl;

}
int main()
{

//     freopen("in.in","r",stdin);
     while(~scanf("%d%d%d%d",&n,&m,&k,&p)){
        deal();
     }
     return 0;
}