Background

PA 2024 5A1
(Missing SPJ).

Problem Description

This problem is translated from PA 2024 Round 5 Autostrada 2.

After many years of meaningless war, Byteotia and Bitotia finally signed a peace treaty. As a symbol of the final agreement, a highway was built between the capitals of the two countries. You have been appointed as the administrator of this highway in the direction from Byteotia to Bitotia (as for the direction from Bitotia to Byteotia, you are not interested in it; it is managed by an administrator from an unfriendly country).

There are currently $m$ toll booths on the highway, numbered from $1$ to $m$. At different times of the day, the cost of passing a toll booth may be different. A day is divided into $n$ hours, numbered from $1$ to $n$. Currently, the cost of passing toll booth $j$ during hour $i$ is $c_{i,j}$ bytealerts. Some of these costs may be $0$ (then the toll booth is free), or even negative (then the driver receives $-c_{i,j}$ bytealerts for passing).

The whole highway is very short and can be completed within one hour. Of course, you do not have to be in such a hurry; you may stop anywhere along the way. However, you cannot stay on the highway overnight, so you must pass all toll booths within the same day.

Naturally, drivers want to pass the highway with the lowest possible total cost. For $1 \le i \le j \le n$, let $f(i,j)$ denote the minimum possible total cost for a driver who passes the first toll booth during hour $i$ and the last toll booth during hour $j$. All values $f(i,j)$ are fixed in advance by the peace treaty of the two governments, and as the highway administrator you cannot change them.

However, as long as the first and the last toll booth are kept, all values $f(i,j)$ remain unchanged, and all set costs are integers (multiples of $1$ bytealert), you may freely modify the costs of passing each toll booth, and you may even remove some toll booths.

To minimize the cost of maintaining the highway, you want to remove as many toll booths as possible. Determine the minimum number of toll booths that must be kept in order to satisfy the treaty.

The toll plan restructuring project will be carried out in two phases. In the first phase, the preliminary design phase, it is enough to find the optimal number of toll booths. In the second phase, the implementation phase, you also need to provide a complete new toll price table.

Input Format

The first line contains three integers $n,m,q\ (2\le n,m\le 30\,000,n\cdot m\le 300\,000,q\in \{0,1\})$, denoting the number of hours in a day, the number of toll booths, and a flag describing the project phase. $q=0$ means the project is in phase 1 (preliminary design), and $q=1$ means the project is in phase 2 (implementation).

The next $n$ lines describe the current tolls. The $i$-th line contains $m$ integers $c_{i,1},c_{i,2},\ldots,c_{i,m}\ (-10^6\le c_{i,j}\le 10^6)$, with the meaning as described above.

Output Format

Output a single integer $k\ (2\le k\le m)$ in the first line, the minimum number of toll booths that must be kept so that no $f(i,j)$ changes. If $q=0$, the output contains only this one line.

If $q=1$, then output $n$ more lines, describing an optimal new price plan that satisfies the conditions. The $i$-th line should contain $k$ integers $d_{i,1},d_{i,2},\ldots,d_{i,k}\ (-10^{12}\le d_{i,j}\le 10^{12})$. Here $d_{i,j}$ is the new cost of passing the $j$-th toll booth during hour $i$.

From the constraints, it can be shown that it is always possible to find a plan with all costs being integers and with absolute values not exceeding $10^{12}$.

3 6 1
-1 0 4 0 -3 0
-4 1 5 2 -5 2
-5 2 3 0 -2 2

3
0 0 0
0 1 0
0 0 0

5 7 0
0 0 0 8 0 0 0
0 7 6 5 9 7 0
0 0 0 5 9 6 0
9 4 0 4 4 7 0
0 0 0 9 8 6 0

3

Hint

In the first sample, $f(i,j)$ is as follows:

It is impossible to achieve the same costs with only two toll booths. Note that the first and the last toll booth cannot be removed, even though according to the output costs $d_{i,j}$ these two toll booths are free.

In the second sample, since the toll plan restructuring draft is only in the preliminary phase, the output does not include the new price table plan.

Constraints and Notes

• Half of the subtasks satisfy $q=0$.
• The other half of the subtasks satisfy $q=1$.

Translated by ChatGPT 5