← 返回题目列表

AtCoder · abc203_d

D. 池塘

中文机器翻译题面 查看原题

分数: 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