问题 D: 中位数
内存限制:1024 MB
时间限制:2.000 S
评测方式:文本比较
命题人:
提交:29
解决:7
题目描述
有一个$N \times N$的正方形网格,每个格子都有高度$A_{i,j}$。
现在要从中选择$K \times K$的正方形部分,使它的高度的中位数最小, 输出最小的中位数高度。
中位数高度定义为方格中第$\left\lfloor \frac{K^2}{2} \right\rfloor + 1$高的高度。
现在要从中选择$K \times K$的正方形部分,使它的高度的中位数最小, 输出最小的中位数高度。
中位数高度定义为方格中第$\left\lfloor \frac{K^2}{2} \right\rfloor + 1$高的高度。
输入
$N$ $K$
$A_{1,1}$ $A_{1,2}$ $A_{1,3}$
$A_{2,1}$ $A_{2,2}$ $A_{2,2}$
...
$A_{N,1}$ $A_{N,2}$ $A_{N,3}$
数据范围
$1 \leq K \leq N \leq 800$
$0 \leq A_{i,j} \leq 10^9$
输入全是整数
$A_{1,1}$ $A_{1,2}$ $A_{1,3}$
$A_{2,1}$ $A_{2,2}$ $A_{2,2}$
...
$A_{N,1}$ $A_{N,2}$ $A_{N,3}$
数据范围
$1 \leq K \leq N \leq 800$
$0 \leq A_{i,j} \leq 10^9$
输入全是整数
样例输入 复制
3 2
1 7 0
5 8 11
10 4 2
样例输出 复制
4