分数: 400 点
问题陈述
公园的土地 AtCoder 是一个 N\times N 具有东西行和南北列的网格。正方形的高在 i从北数第 行, j从西数第 列给出为 A_{i,j}.
经理高桥决定建造一个方形池塘,占据 K \times K 这个公园里的广场。
为此,他想选择一个正方形截面 K \times K 完全位于公园内的广场,其 中位数 方块高度的 是最低的。求该部分中正方形高度的中位数。
在这里, 中位数 方块高度的 中正方形的高度 K \times K 部分是高度 (\left\lfloor\frac{K^2}{2}\right\rfloor +1)- 第一个最高的方块 K^2 部分中的方块,其中 \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}
输出
打印答案。
示例输入 1
3 2 1 7 0 5 8 11 10 4 2
示例输出 1
4
让 (i,j) 表示 i从北数第 行, j从西数第 3 列。
我们有四位候选人 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-rd 最高方格,即 5, 7, 5, 4 分别针对上述候选人。我们应该打印其中最低的一个: 4.
示例输入 2
3 3 1 2 3 4 5 6 7 8 9
示例输出 2
5