Score : $400$ points

问题描述

AtCoder 公园的土地是一个 $N \times N$ 的网格，东西方向为行，南北方向为列。从西边数第 $j$ 列、从北边数第 $i$ 行的正方形高度记为 $A_{i,j}$。

作为公园经理的高桥决定在这个公园内建造一个占据 $K \times K$ 个方格的正方形池塘。

为了实现这个目标，他希望在公园内完全包含 $K \times K$ 个方格的正方形区域内选择一个部分，使得该区域中正方形高度的中位数尽可能低。请找出这样一个区域内正方形高度的中位数。

这里，一个 $K \times K$ 区域内正方形高度的中位数是指，在该区域内的 $K^2$ 个正方形中，按照高度从高到低排列后，第 $\left\lfloor\frac{K^2}{2}\right\rfloor +1$ 高的正方形的高度，其中 $\lfloor x\rfloor$ 表示不超过 $x$ 的最大整数。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

The land of a park AtCoder is an $N\times N$ grid with east-west rows and north-south columns. The height of the square at the $i$-th row from the north and $j$-th column from the west is given as $A_{i,j}$.

Takahashi, the manager, has decided to build a square pond occupying $K \times K$ squares in this park.

To do this, he wants to choose a square section of $K \times K$ squares completely within the park whose median of the heights of the squares is the lowest. Find the median of the heights of the squares in such a section.

Here, the median of the heights of the squares in a $K \times K$ section is the height of the $(\left\lfloor\frac{K^2}{2}\right\rfloor +1)$-th highest square among the $K^2$ squares in the section, where $\lfloor x\rfloor$ is the greatest integer not exceeding $x$.

Constraints

• $1 \leq K \leq N \leq 800$
• $0 \leq A_{i,j} \leq 10^9$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$ $K$

$A_{1,1}$ $A_{1,2}$ $\ldots$ $A_{1,N}$

$A_{2,1}$ $A_{2,2}$ $\ldots$ $A_{2,N}$

$:$

$A_{N,1}$ $A_{N,2}$ $\ldots$ $A_{N,N}$

Output

Print the answer.

Sample Input 1

3 2
1 7 0
5 8 11
10 4 2

Sample Output 1

4

Let $(i,j)$ denote the square at the $i$-th row from the north and $j$-th column from the west. We have four candidates for the $2 \times 2$ section occupied by the pond: $\{(1,1),(1,2),(2,1),(2,2)\}, \{(1,2),(1,3),(2,2),(2,3)\}, \{(2,1),(2,2),(3,1),(3,2)\}, \{(2,2),(2,3),(3,2),(3,3)\}$.
When $K=2$, since $\left\lfloor\frac{2^2}{2}\right\rfloor+1=3$, the median of the heights of the squares in a section is the height of the $3$-rd highest square, which is $5$, $7$, $5$, $4$ for the candidates above, respectively. We should print the lowest of these: $4$.

Sample Input 2

3 3
1 2 3
4 5 6
7 8 9

Sample Output 2

5

update @ 2024/3/10 09:15:59