『MdOI R1』Decrease
题目描述
给定一个 $n \times n$ 的矩阵,你可以进行若干次操作。
每次操作,你可以将一个 $k \times k$ 的 **连续** 子矩阵里的所有数全都加上 $1$ 或者全都减去 $1$。
初始时,矩阵中有 $m$ 个位置上的数不为 $0$,其它位置上的数均为 $0$。
请你求出至少需要多少次操作,可以将矩形中所有数都变为 $0$。
输入输出格式
输入格式
第一行三个整数 $n,m,k$,分别表示矩阵大小,非 $0$ 格数和每次修改的连续子矩阵大小。
接下来 $m$ 行,每行三个整数 $x,y,z$,表示初始时矩阵的第 $x$ 行第 $y$ 列上的数为 $z$。
输出格式
一行一个整数,表示最少操作次数。
特别地,如果无法使矩阵中所有数都变为 $0$,输出 `-1`。
输入输出样例
输入样例 #1
4 14 3
1 1 1
1 2 1
1 3 1
2 1 1
2 2 3
2 3 3
2 4 2
3 1 1
3 2 3
3 3 3
3 4 2
4 2 2
4 3 2
4 4 2
输出样例 #1
3
输入样例 #2
3 1 2
1 1 1
输出样例 #2
-1
输入样例 #3
4 5 1
1 1 5
2 2 -3
2 3 -4
3 3 1
4 4 2
输出样例 #3
15
说明
【样例 1 解释】:
给出的矩阵为:
```plain
1 1 1 0
1 3 3 2
1 3 3 2
0 2 2 2
```
具体步骤:
先将以第一行第一列为左上角的连续子矩阵执行 **减 1 操作** 一次;
再将以第二行第二列为左上角的连续子矩阵执行 **减 1 操作** 两次。
总共三次。
```plain
1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0
1 3 3 2 0 2 2 2 0 1 1 1 0 0 0 0
1 3 3 2 0 2 2 2 0 1 1 1 0 0 0 0
0 2 2 2 0 2 2 2 0 1 1 1 0 0 0 0
```
【样例 2 解释】:
给出的矩阵为:
```plain
1 0 0
0 0 0
0 0 0
```
只通过 $2\times 2$ 的连续子矩阵操作不可能使得所有格子上的数都变为 $0$。
【数据范围】
**本题采用捆绑测试。**
| 子任务编号 | $n\leq$ | $k\leq$ | 分值 |
| :--------: | :------------: | :-----: | :--: |
| 1 | $10^3$ | $1$ | 11 |
| 2 | $20$ | $20$ | 14 |
| 3 | $100$ | $100$ | 17 |
| 4 | $10^3$ | $10^3$ | 34 |
| 5 | $5\times 10^3$ | $10^3$ | 24 |
对于所有数据,$1\leq n\leq 5\times 10^3$,$1\leq m\leq \min(n^2,5\times 10^5)$,$1\leq k\leq \min(n,10^3)$,$1\leq x,y\leq n$,每对 $(x,y)$ 至多出现一次,$1 \le |z| \leq 10^9$。
数据保证如果有解,答案不超过 $2^{63}-1$。
---
【提示】
本题读入量较大,建议使用较快的读入方式。