P5910 [CTSC2007] Matrix Matrix [Seeking SPJ].

Given an integer $D$ and a real matrix $A$ with $n$ rows and $m$ columns, the element in row $i$ and column $j$ is $a_{ij}$, and $0 \le a_{ij} \le D$ ($1 \le i \le n$, $1 \le j \le m$). You are asked to provide an $n \times m$ $01$ matrix $B$, whose element in row $i$ and column $j$ is $b_{ij}$ ($1 \le i \le n$, $1 \le j \le m$), where $b_{ij}$ is either $0$ or $1$. For the given matrix $A$ and your matrix $B$, we can compute: $$p_1=\max \begin{cases}\max\limits_{ 1 \le j \le m} \{ |\sum_{i=1}^n (b_{ij}-\frac{a_{ij}}{D})|\}\\\max\limits_{1 \le i \le n} \{ |\sum_{j=1}^m (b_{ij}-\frac{a_{ij}}{D})|\}\end{cases}$$ $$p_2=\max_{1 \le i \le n,1 \le j \le m} \{|b_{i,j}+b_{i-1,j}+b_{i,j-1}+b_{i-1,j-1}-\frac{a_{i,j}+a_{i-1,j}+a_{i,j-1}+a_{i-1,j-1}}{D}|\}$$ For different test cases, we hope that the matrix $B$ you provide can make $p_1$ or $p_2$ as small as possible.

The first line contains an integer $c$, which has two possible values: $c=1$ means our minimization target is $p_1$, and $c=2$ means we want $p_2$ to be as small as possible. The second line contains three integers $D$, $n$, and $m$, separated by a single space. The meaning of $D$ is as described above, and $n$ and $m$ are the number of rows and columns of matrix $A$, respectively. Then follow $n$ lines, each containing $m$ real numbers describing matrix $A$. The real number in row $i$ and column $j$ is $a_{ij}$, and adjacent numbers are separated by a single space.

Output only an $n \times m$ $01$ matrix $B$, representing the answer you found that makes $p_c$ as small as possible. The number in row $i$ and column $j$ is $b_{ij}$. Adjacent integers are separated by a single space.

For $40\%$ of the testdata, $c=1$. For $60\%$ of the testdata, $c=2$. For $100\%$ of the testdata, Constraints: $2 \le n ,m \le 700$, $1 \le D \le 10^9$. Translated by ChatGPT 5