D. DZY Loves Modification

2024-09-02 18:38
文章标签 loves dzy modification

本文主要是介绍D. DZY Loves Modification,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

D. DZY Loves Modification
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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:

  1. 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.
  2. 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 test(s)
input
2 2 2 2
1 3
2 4
output
11
input
2 2 5 2
1 3
2 4
output
11
Note

For the first sample test, we can modify: column 2, row 2. After that the matrix becomes:

1 1
0 0

For the second sample test, we can modify: column 2, row 2, row 1, column 1, column 2. After that the matrix becomes:

-3 -3
-2 -2

文章大意是给你一个n * m的矩阵,你可以进行k次操作.

操作1:把一行的每个元素都减去p,你可以获得该行所有元素和(操作之前)的pleasure

操作2:把一列的每个元素都减去p,你可以获得该列所有元素和(操作之前)的pleasure

问你最大可以获得的pleasure是多少

思路:枚举操作1所进行的次数,每次取能获得最大的行,用优先队列维护,要注意预处理,否则会超时

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
typedef long long LL;
using namespace std;
int A[1005][1005];
LL R[1005],C[1005];
LL s1[1000005],s2[1000005];
void get_C(int n,int i,int (*A) [1005])
{LL s=0;for(int j=1;j<=n;j++)s+=A[j][i];C[i]=s;
}
void get_R(int m,int i,int (*A)[1005])
{LL s=0;for(int j=1;j<=m;j++)s+=A[i][j];R[i]=s;
}
int main()
{int n,m,k,p;while(scanf("%d%d%d%d",&n,&m,&k,&p)==4){LL s=0;s1[0]=s2[0]=0;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%d",&A[i][j]);LL sum=-1000000000000009;priority_queue<LL>q1;priority_queue<LL>q2;for(int i=1;i<=n;i++){get_R(m,i,A);q1.push(R[i]);}for(int i=1;i<=m;i++){get_C(n,i,A);q2.push(C[i]);}for(int j=1;j<=k;j++){LL temp=q1.top();q1.pop();s1[j]=s1[j-1]+temp;temp-=p*m;q1.push(temp);}for(int j=1;j<=k;j++){LL temp=q2.top();q2.pop();s2[j]=s2[j-1]+temp;temp-=p*n;q2.push(temp);}for(int i=0;i<=k;i++){s=s1[i]+s2[k-i];sum=max(sum,s-LL(i)*p*(k-i));}printf("%I64d\n",sum);}return 0;
}


这篇关于D. DZY Loves Modification的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1130752

相关文章

【HDU】4876 ZCC loves cards 暴力

传送门:【HDU】4876 ZCC loves cards 题目分析: 这题无力吐嘈。。。。能想到的优化都用上吧。。。 代码如下: #include <cstdio>#include <cstring>#include <algorithm>using namespace std ;#define REP( i , n ) for ( int i =

【HDU】4873 ZCC Loves Intersection 数学

传送门:【HDU】4873 ZCC Loves Intersection 题目大意:给你一个D维的空间,每个维度都有一条线段平行与该维度属于的轴(如X,Y,Z轴),且线段的端点坐标取值范围0~N-1,保证左端点严格小于右端点(除该维度,其他维度的值两端点均相等)。现在告诉你每条线段的左右端点的坐标都是随机的,0~N-1随机到的概率是完全相等的!现在如果两条线段如果相交于一点,你可以获得一点

【HDU】5197 DZY Loves Orzing 【FFT启发式合并】

传送门:【HDU】5197 DZY Loves Orzing 题目分析: 首先申明,我不会 dp dp方程= =……这个东西给队友找出来了,然后我就是套这个方程做题的Qrz…… 对于这题,因为 n2 n^2个数互不相同,所以每一列都可以单独考虑。设 dpni dp_ni表示长度为 n n的排列,能恰好看见ii个人的方案数,根据队友的发现, dpni dp_ni就等于 |sni| |s_ni|

Codeforces Round #FF (Div. 2/C)/Codeforces446A_DZY Loves Sequences(DP)

DZY Loves Sequences time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output DZY has a sequence a, consisting of n integers. We'

Codeforces Round #FF (Div. 2/A)/Codeforces447A_DZY Loves Hash(哈希)

A. DZY Loves Hash time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output DZY has a hash table with p buckets, numbered from

File `Makefile' has modification time 1.8e+06 s in the future这种警告的原因分析及解决方法

移植uboot时,一般都会先在windows下修改,然后在LInux环境下编译,往往在Linux下使用命令行对目标板进行配置时: $make wqh2440_config 会出现如下错误信息: make: Warning: File `Makefile' has modification time 1.8e+06 s in the future 通过这个错误提示信息我们可以知道,Make

hdu5274 Dylans loves tree

官方题解 题目里有一个很神奇的性质:路径上最多只有一个数出现奇数次。这应该马上想到异或。因为异或两次和没异或是等价的。此外异或满足区间减性质。因为有修改,我们很自然地想到用数据结构维护。最无脑的就是直接上树链剖分或是Splay维护区间xor值即可。仔细想一想,发现可以利用LCA消去“树上路径”,转化为根到x路径上求xor值。我们可以很经典地直接使用线段树或树状数组维护dfs序。(然而

hdu5196 DZY Loves Inversions 思路,计数

题意:一个数列,给出一些区间,计算这个区间有多少子区间逆序对数为k。 分析:直接计算k不好算,把问题转化为<=k的子区间数减去<k的子区间数。首先由两个指针可以求出每一个点的满足<=k或<k的最右边界。得到r1和r2数组。    最后所求即为sum(min(r1i,r)-l+1) (i>=l&&i<=r),r数组单调递增,二分即可。 #include<iostream>#include

codeforces#FF DIV2C题DZY Loves Sequences(DP)

题目地址:http://codeforces.com/contest/447/problem/C C. DZY Loves Sequences time limit per test 1 second memory limit per test 256 megabytes input standard input output standard outpu

Codeforces Round #FF (Div. 1) C. DZY Loves Fibonacci Numbers

用线段树维护 记录三个值,一个是区间和,一个是该区间 1 , 2 位置的斐波那契数列前两项大小(因为两个斐波那契数列相加得到的还是一个斐波那契数列,且该数列只与两个首项和项数有关,另外斐波那契数列前N 项和  与  该斐波那契数列第N+2减去第二项  的值 相同) 该线段树的pushdown有一些改变,直接利用已有的update函数将懒标记下传,下传时改变的区间是传入pushdown的区间大