Rectangular skating rink
Limits: 3 sec., 256 MiB
This statement was translated automatically from Ukrainian.
The next day, Zenik and Marichka decided to go ice skating.
At the resort, there is a rectangular skating rink of size \(n \times m\). Each of the \(n \times m\) sections of the skating rink has its own danger level \(d_{i j}\).
The skating rink is very large, so the couple does not want to skate over its entire area, but rather choose a square of size \(k \times k\) with sides parallel to the sides of the rink and skate on it.
The danger level of a square is the maximum danger level among all the sections that belong to it.
Marichka asks you to find out what minimum danger level a \(k \times k\) square can have.
Input
The first line contains three integers \(n\), \(m\), and \(k\) — the sizes of the skating rink and the square. The next \(n\) lines each contain \(m\) integers \(d_{i j}\) — the danger level at the corresponding section of the skating rink.
Output
In a single line, output an integer — the minimum danger level of a \(k \times k\) square.
Constraints
\(1 \le n, m \le 1500\), \(1 \le k \le min\{n, m\}\),
\(1 \le d_{i j} \le 10^9\).
10 points: \(n, m \le 100\);
10 points: \(n, m \le 700\);
5 points: no additional constraints.
Samples
| Input (stdin) | Output (stdout) |
|---|---|
| 3 3 2 2 5 4 4 1 3 3 2 1 | 3 |
Notes
In the example, the possible ways to choose a \(2 \times 2\) square are:
\(\begin{matrix} 2 & 5 \\ 4 & 1 \end{matrix}\) with a danger level of 5,
\(\begin{matrix} 5 & 4 \\ 1 & 3 \end{matrix}\) with a danger level of 5,
\(\begin{matrix} 4 & 1 \\ 3 & 2 \end{matrix}\) with a danger level of 4,
\(\begin{matrix} 1 & 3 \\ 2 & 1 \end{matrix}\) with a danger level of 3.
Submit a solution
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|
Rectangular skating rink - Editorial
Let’s check whether there is a \(k \times k\) square whose elements are all at most \(x\).
Make a new array with \(a_{i j} = 0\) if \(d_{i j} \le x\) and \(a_{i j} = 1\) otherwise. Then, having computed prefix sums, we can find the sum over any \(k \times k\) square in \(O(1)\).
We go over all squares, and if at least one of them has sum \(0\), this square has no elements greater than \(x\).
Now we can use binary search to find the minimum value of \(x\) for which there is a \(k \times k\) square with all elements at most \(x\). This value is the answer.
Solution code in Python (scores 10 points)
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|