D - Pond

Contest Duration: 2021-05-30(Sun) 12:00 - 2021-05-30(Sun) 13:40 (local time) (100 minutes) Back to Home

D - Pond Editorial

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}$

出力

答えを出力せよ。

入力例 1Copy

Copy

出力例 1Copy

Copy

北から $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$ を出力します。

入力例 2Copy

Copy

出力例 2Copy

Copy

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 1Copy

Copy

Sample Output 1Copy

Copy

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 2Copy

Copy

Sample Output 2Copy

Copy