1464. 最小中位数子矩阵

给定一个 n \times n 的矩阵 a,在该矩阵中找到一个 k \times k 的子矩阵,使该子矩阵所有元素的中位数(也就是第 \left\lfloor\frac{k^2}{2}\right\rfloor +1 大的元素的值)在所有 k \times k 子矩阵中最小。输出该中位数的值。

输入

第一行两个整数 n,k \ (1 \leq k \leq n \leq 800)

接下来 n 行每行 n 个整数,表示矩阵 a \ (0 \leq a_{i,j} \leq 10^9)

输出

输出一个整数,表示答案。

样例

标准输入 复制文本
3 2
1 7 0
5 8 11
10 4 2
标准输出 复制文本
4

提示

有四个 k \times k(也就是 2 \times 2)的子矩阵,这四个子矩阵的中位数(也就是第 \left\lfloor\frac{2^2}{2}\right\rfloor +1=3 大的元素)分别是 5,7,5,4,所以最小值为 4

登录以提交代码。
单点时限 1 秒
内存限制 256 MB
提交 10
通过 5