D - 池塘

得分：$400$ 分

问题描述

AtCoder 公园的土地是一个 $N\times N$ 的网格，有东西方向的行和南北方向的列。第 $i$ 行从北边开始，第 $j$ 列从西边开始的正方形的高度为 $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$ 的最大整数。

约束

• $1 \leq K \leq N \leq 800$
• $0 \leq A_{i,j} \leq 10^9$
• 输入中的所有数均为整数。

输入

输入以以下格式从标准输入获得：

$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}$

输出

输出答案。

3 2
1 7 0
5 8 11
10 4 2

4

设 $(i,j)$ 表示北边第 $i$ 行、西边第 $j$ 列的方格。 对于 $2 \times 2$ 的方格，我们有四个候选池塘的位置： $\{(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)\}$。
当 $K=2$ 时，由于 $\left\lfloor\frac{2^2}{2}\right\rfloor+1=3$，方格高度的中位数即为第 $3$ 高的方格的高度，分别对应候选池塘的高度是 $5$，$7$，$5$，$4$。我们应该输出这些中的最低值：$4$。

3 3
1 2 3
4 5 6
7 8 9

5