首页 > 代码库 > CodeForces 446B
CodeForces 446B
Description
As we know, DZY loves playing games. One day DZY decided to play with a n × m matrix. To be more precise, he decided to modify the matrix with exactly k operations.
Each modification is one of the following:
- Pick some row of the matrix and decrease each element of the row by p. This operation brings to DZY the value of pleasure equal to the sum of elements of the row before the decreasing.
- Pick some column of the matrix and decrease each element of the column by p. This operation brings to DZY the value of pleasure equal to the sum of elements of the column before the decreasing.
DZY wants to know: what is the largest total value of pleasure he could get after performing exactly k modifications? Please, help him to calculate this value.
Input
The first line contains four space-separated integers n, m, k and p(1 ≤ n, m ≤ 103; 1 ≤ k ≤ 106; 1 ≤ p ≤ 100).
Then n lines follow. Each of them contains m integers representing aij (1 ≤ aij ≤ 103) — the elements of the current row of the matrix.
Output
Output a single integer — the maximum possible total pleasure value DZY could get.
------------------------------------
Sample Input
2 2 2 2
1 3
2 4
11
2 2 5 2
1 3
2 4
11
题目意思：给一个n*m的矩阵，k次操作，每次操作可以是一行也可以是一列，把操作所在的行或列的数字相加，然后该行或列每个元素都减去p，问K次操作后总的sum为多少。
假设k次操作中对行操作a次，对列操作b次。 那么显而易见的是a和b操作顺序可以随意打乱，不影响结果，为使结果最大，每次操作都需要行最大的或列最大的。
预处理对行进行k次操作，对列进行k次操作分别放入两个数组h[]和l[]中，那么结果应为max(h[i]+l[k-i]-i*(k-i)*p) (0<=i<=k)。 因为i次行操作和k-i次列操作重复了i*(k-i)次，所以需要减去i*(k-i)*p.
代码：
1 #include <stdio.h> 2 #include <string.h> 3 #include <algorithm> 4 #include <iostream> 5 #include <queue> 6 #define inf 999999999 7 using namespace std; 8 9 priority_queue<__int64>qh, ql;10 __int64 h[1000005], l[1000005];11 __int64 map[1005][1005];12 __int64 n, m, k, p;13 14 main()15 {16 int i, j;17 while(scanf("%I64d %I64d %I64d %I64d",&n,&m,&k,&p)==4)18 {19 __int64 sum, ans, num;20 for(i=1;i<=n;i++)21 for(j=1;j<=m;j++)22 scanf("%d",&map[i][j]);23 24 while(!qh.empty())25 qh.pop();26 while(!ql.empty())27 ql.pop();28 sum=h[0]=l[0]=0;29 //hang30 for(i=1;i<=n;i++)31 {32 sum=0;33 for(j=1;j<=m;j++)34 {35 sum+=map[i][j];36 }37 qh.push(sum);38 }39 for(i=1;i<=k;i++)40 {41 num=qh.top();42 h[i]=h[i-1]+num;43 num-=p*m;44 qh.pop();45 qh.push(num);46 }47 //lie48 49 for(j=1;j<=m;j++)50 {51 sum=0;52 for(i=1;i<=n;i++)53 {54 sum+=map[i][j];55 }56 ql.push(sum);57 }58 for(i=1;i<=k;i++)59 {60 num=ql.top();61 l[i]=l[i-1]+num;62 num-=p*n;63 ql.pop();64 ql.push(num);65 }66 ans=inf;67 ans=-ans*ans;68 69 for(i=0;i<=k;i++)70 {71 ans=max(ans,h[i]+l[k-i]-i*(k-i)*p);72 }73 cout<<ans<<endl;74 }75 }