# CF446B DZY Loves Modification(CF446B DZY Loves Modification)-其他

## CF446B DZY Loves Modification(CF446B DZY Loves Modification)

$$zyb$$ 有一个 $$n \times m$$ 的矩阵，他每次选某一行或者某一列，使自己的快乐值加上这一 行/列 的总和。之后这一 行/列 的所有数字大小减去 $$p$$ 。问 $$k$$ 次操作之后最大快乐值为多少。

$$O(k \log n)$$ 。

Code

————————

< strong > meaning of the question: < / strong >

$$ZYB$$ has a \ (n \ times m \) matrix. Each time he selects a row or column, he adds his happiness value to the sum of this row / column. After that, subtract \ (P \) from the size of all numbers in this row / column. Ask the maximum happiness value after \ (K \) operations.

< strong > solution: < / strong >

Since the change of one row will not affect the answers of other rows and the change of one column will not affect the answers of other columns, we consider rows and columns separately.

Let \ (sum_1 [i] \) represent the maximum happiness value that can be obtained by a single operation line \ (I \) times, and \ (sum_2 [i] \) represent the maximum happiness value that can be obtained by a single operation column \ (I \) times. So the answer is \ (\ Max \) {\ (sum_1 [i] + sum_2 [k-i] + P \ cdot I \ cdot (k-i) \)}.

The two pre-processing arrays \ (sum_1 \) and \ (sum_2 \) use priority queues. I won’t explain more.

As for subtraction \ (P \ cdot I \ cdot (k-i) \), it can be considered as the number of intersections of \ (I \) row lines and \ ((k – I) \) column lines. (this hand play sample can also be found)

< strong > time complexity: < / strong >

$$O(k \log n)$$ 。

Code