#N. Pond

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z [ \ ] ^ _ ` a b c d e f g h i j k l
    Type: RemoteJudge 2000ms 256MiB

Pond

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题面翻译

题目大意

给定一个 n×nn\times n 的矩阵 AA，再给定一个数 kk，求矩阵中所有大小为 k×kk\times k 的子矩阵的中位数的最小值。

一个 k×kk\times k 的矩阵的中位数被定义为将矩阵中的所有数从大到小排序后的第 ⌊k22⌋+1\lfloor\frac{k^2}{2}\rfloor+1 个数。

输入格式

第一行两个正整数 n,kn,k。

接下来 nn 行，每行 nn 个数，描述了一个矩阵。

输出格式

输出一行一个数，表示中位数的最小值。

说明/提示

1≤k≤n≤800,0≤Ai,j≤1091\le k\le n\le 800,0\le A_{i,j}\le 10^9。

Translated by _Ponder_

题目描述

AtCoder 公園の敷地は東西南北に広がる N× N N\times\ N のマス目からなっており、北から i i 番目かつ西から j j 番目のマスの高さは Ai,j A_{i,j} で与えられます。

公園の管理者である高橋君はここに K × K K\ \times\ K の区画の池を作る事にしました。

池を作るにあたって、高橋君は AtCoder 公園の敷地内に完全に含まれる K × K K\ \times\ K の区画であってその区画に含まれるマスの高さの中央値が最も低いようなものを選ぼうと考えました。そのような区画のマスの高さの中央値を求めてください。

ここで、 K × K K\ \times\ K の区画に含まれるマスの高さの中央値とはその区画に含まれる K2 K^2 個のマスのうち ⌊K22⌋ +1 \left\lfloor\frac{K^2}{2}\right\rfloor\ +1 番目に高いマスの高さを指します。また、⌊ x⌋ \lfloor\ x\rfloor は x x 以下の最大の整数を表します。

输入格式

入力は以下の形式で標準入力から与えられる。

N N K K A1,1 A_{1,1} A1,2 A_{1,2} … \ldots A1,N A_{1,N} A2,1 A_{2,1} A2,2 A_{2,2} … \ldots A2,N A_{2,N} : : AN,1 A_{N,1} AN,2 A_{N,2} … \ldots AN,N A_{N,N}

输出格式

答えを出力せよ。

样例 #1

样例输入 #1

3 2
1 7 0
5 8 11
10 4 2

样例输出 #1

4

样例 #2

样例输入 #2

3 3
1 2 3
4 5 6
7 8 9

样例输出 #2

5

提示

制約

  • 1 ≤ K ≤ N ≤ 800 1\ \leq\ K\ \leq\ N\ \leq\ 800
  • 0 ≤ Ai,j ≤ 109 0\ \leq\ A_{i,j}\ \leq\ 10^9
  • 入力は全て整数である。

Sample Explanation 1

北から i i 番目で西から j j 番目のマスを (i,j) (i,j) で表すとして、 池の候補となる 2× 2 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)} \{(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 4 つです。 K=2 K=2 のとき、各区画に含まれるマスの高さの中央値は各区画に含まれるマスのうち ⌊222⌋+1=3 \left\lfloor\frac{2^2}{2}\right\rfloor+1=3 番目に高いマスの高さとなるので、それぞれの区画の中央値は 5 5 , 7 7 , 5 5 , 4 4 であり、このうち最小である 4 4 を出力します。

北辰OI提高组第2周序列问题课后练习题👍

Not Attended
Status
Done
Rule
IOI
Problem
44
Start at
2024-1-7 16:00
End at
2024-2-18 8:00
Duration
1000 hour(s)
Host
Partic.
15
  1. About
  2. Contact Us
  3. Privacy
  4. Terms of Service
  5. Copyright Complaint
  6. Language
  7. Legacy mode
  8. Theme
  2. text

  4. 鲁公网安备 37079402001599号

  • 鲁ICP备2022025036号-1
  • Worker 0, 29ms
  • Powered by Hydro v4.9.27 Community