RoAlgo PreOJI 2024 VII | partsum

Task

From a matrix $mat$ of size $N \times N$, three matrices $v_1$, $v_2$, $v_3$ are constructed with the following properties:
For each cell in the matrix $(i, j)$, where $1 \leq i, j \leq N$:

• $0 \leq v_{1(i, j)} < i$;
• $0 \leq v_{2(i, j)} < j$;
• $v_{3(i, j)}$ is the sum of the submatrix with the top-left corner at $(i-v_{1(i, j)}, j-v_{2(i, j)})$ and the bottom-right corner at $(i, j)$ from the matrix $mat$.

You are given $N$, $K$, and the matrices $v_1$, $v_2$, $v_3$. You need to display a way to change exactly $K$ values in the matrix $mat$, such that the sum of the values in $v_3$ is minimized. Additionally, you need to display the minimum sum. You can choose to keep the element in cell $(i, j)$ in the matrix $mat$ unchanged, in which case you will display $(i, j, element)$ of the matrix $mat$ at cell $(i, j)$.

Input data

The first line of the input file partsum.in contains two integers, $N$ and $K$. The next $N$ lines will contain $N$ values each, representing the values in $v_1$. The following $N$ lines will contain $N$ values each, representing the values in $v_2$. The next $N$ lines will contain $N$ values each, representing the values in $v_3$.

Note! In the tests, there are no empty lines between the matrices $v_1$, $v_2$, and $v_3$. They have been added only for clarification in the example!

Output data

The first $K$ lines of the output file partsum.out will contain three values $lin_i, col_i, x_i$, representing that the value in cell $(lin_i, col_i)$ will change to $x_i$. On the $(K+1)$-th line, the minimum sum formed will be displayed.

Note! If at least one value among $lin_i$ or $col_i$ is not within the interval $[1, N]$, the verdict will be Wrong Answer. Additionally, if at least one value $x_i$ is not within the interval $[0, 3 \times 10^6]$, the verdict will be Wrong Answer.

Constraints and clarifications

• $1 \leq N \leq 600$;
• $1 \leq K \leq N^2$;
• There may be multiple correct solutions, any of them will be accepted.
• If the $K$ changes do not lead to the sum of the values in $v_3$ being the sum displayed on the $(K+1)$-th line, you will receive $0$ points!
• It is guaranteed that the matrices $v_1$, $v_2$, and $v_3$ originate from a matrix $mat$.
• $0 \leq v_{3(i, j)} \leq 10^{12}$.
• It is guaranteed that the elements of the matrix $mat$ are natural numbers.

Example 1

partsum.in

2 1
0 0
0 0

0 1
0 0

2 5
3 3

partsum.out

1 1 0
9

Explanation

The matrix $mat$ from which $v_1$, $v_2$ and $v_3$ are derived is:

2 3
3 3

If we change the value $2$ to $0$ in cell $(1, 1)$, the sums on row $1$ will become $0 \ 3$, and the sum of the values in $v_3$ becomes $0 + 3 + 3 + 3 = 9$. This is the minimum sum that can be formed if we change at most one element.