/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
AtCoder 公園の敷地は東西南北に広がる N\times N のマス目からなっており、北から i 番目かつ西から j 番目のマスの高さは A_{i,j} で与えられます。
公園の管理者である高橋君はここに K \times K の区画の池を作る事にしました。
池を作るにあたって、高橋君は AtCoder 公園の敷地内に完全に含まれる 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}
出力
答えを出力せよ。
入力例 1
3 2 1 7 0 5 8 11 10 4 2
出力例 1
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)\} の 4 つです。
K=2 のとき、各区画に含まれるマスの高さの中央値は各区画に含まれるマスのうち \left\lfloor\frac{2^2}{2}\right\rfloor+1=3 番目に高いマスの高さとなるので、それぞれの区画の中央値は 5, 7, 5, 4 であり、このうち最小である 4 を出力します。
入力例 2
3 3 1 2 3 4 5 6 7 8 9
出力例 2
5
Score : 400 points
Problem Statement
The land of a park AtCoder is an N\times N grid with east-west rows and north-south columns. The height of the square at the i-th row from the north and j-th column from the west is given as A_{i,j}.
Takahashi, the manager, has decided to build a square pond occupying K \times K squares in this park.
To do this, he wants to choose a square section of K \times K squares completely within the park whose median of the heights of the squares is the lowest. Find the median of the heights of the squares in such a section.
Here, the median of the heights of the squares in a K \times K section is the height of the (\left\lfloor\frac{K^2}{2}\right\rfloor +1)-th highest square among the K^2 squares in the section, where \lfloor x\rfloor is the greatest integer not exceeding x.
Constraints
- 1 \leq K \leq N \leq 800
- 0 \leq A_{i,j} \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
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}
Output
Print the answer.
Sample Input 1
3 2 1 7 0 5 8 11 10 4 2
Sample Output 1
4
Let (i,j) denote the square at the i-th row from the north and j-th column from the west.
We have four candidates for the 2 \times 2 section occupied by the pond: \{(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)\}.
When K=2, since \left\lfloor\frac{2^2}{2}\right\rfloor+1=3, the median of the heights of the squares in a section is the height of the 3-rd highest square, which is 5, 7, 5, 4 for the candidates above, respectively. We should print the lowest of these: 4.
Sample Input 2
3 3 1 2 3 4 5 6 7 8 9
Sample Output 2
5