http://codeforces.com/problemset/problem/446/B

分别将每行的和与每列的和存入优先队列，计算操作n次的最大和，保存每一次结果。

枚举行和列操作的次数，注意要减去补偿的值。

#include
#include
#include
#include

using namespace std;
long long a[][],r[],c[];
long long rr[],cc[];
int main()
{

int n,m,k,p;  
scanf("%d%d%d%d",&n,&m,&k,&p);  
for(int i = ;i <= n;i++)  
{  
    for(int j = ;j <= m;j++)  
    {  
        scanf("%lld",&a\[i\]\[j\]);  
        r\[i\] += a\[i\]\[j\];  
        c\[j\] += a\[i\]\[j\];  
    }  
}  
priority\_queue<long long> q;  
for(int i = ;i <= n;i++)  
{  
    q.push(r\[i\]);  
}  
for(int i = ;i <= k;i++)  
{  
    long long temp = q.top();  
    q.pop();  
    rr\[i\] = rr\[i-\]+temp;  
    temp -= p\*m;  
    q.push(temp);  
}  
while(!q.empty())  
{  
    q.pop();  
}  
for(int i = ;i <= m;i++)  
{  
    q.push(c\[i\]);  
}  
for(int i = ;i <= k;i++)  
{  
    long long temp = q.top();  
    q.pop();  
    cc\[i\] = cc\[i-\]+temp;  
    temp -= p\*n;  
    q.push(temp);  
}  
long long sum = -1LL<<;  
for(int i = ;i <= k;i++)  
{  
    sum = max(sum,rr\[i\]+cc\[k-i\]-1LL\*p\*i\*(k-i));  
}  
cout << sum << endl;  
return ;  

}