시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 256 MB 56 33 19 57.576%

문제

Alberta 시에서는 도시가 직사각형 격자모양의 블록으로 설계되어 있다. 블록은 가장 북쪽 0번부터 가장 남쪽 R-1번까지(행의 번호), 가장 서쪽 번부터 가장 동쪽 C-1번까지로(열의 번호) 나누어져 있다.

각 블록에서 삶의 질은 1에서 R×C 사이의 유일한 수로 표현되며, 이를 quality rank라 한다. 1로 표현된 삶의 질이 가장 좋은 quality rank이고, R×C은 가장 나쁜 quality rank이다.

홍준이는 H×W (1 ≤ H ≤ R, 1 ≤ W ≤ C)의 영역에서 quality rank의 중간값 중 가장 질이 높은(수의 크기는 가장 작은) 값을 찾으려고 한다. H와 W는 홀수이고 각각은 R과 C를 초과하지 않는다. 홀수개의 quality rank들 중에서 중간값 m은 m보다 더 좋은 랭크의 수와 m보다 더 나쁜 랭크의 수가 같은 것으로 정의한다.

홍준이를 도와 H×W의 크기를 가지는 영역들 중에서 quality rank의 중간값 중 가장 질이 높은 값을 찾는 프로그램을 작성하시오.

입력

첫째 줄에 4개의 정수 R, C, H, W 가 주어진다. R과 C는 각각 도시의 행과 열의 크기를 나타내고, H와 W는 각각 홍준이가 정한 영역에서의 행과 열의 크기이다. 그 다음 R개의 줄에 각각 C개의 quality rank를 나타내는 정수가 주어진다. (1 ≤ R, C ≤ 3000)

출력

첫째 줄에 quality rank의 중간값 중 가장 질이 높은 값을 찾을 출력한다.

예제 입력

5 5 3 3
5 11 12 16 25
17 18 2 7 10
4 23 20 3 1
24 21 19 14 9
6 22 8 13 15

예제 출력

9

힌트

출처

Olympiad > International Olympiad in Informatics > IOI 2010 3번

  • 문제를 번역한 사람: appa
  • 잘못된 데이터를 찾은 사람: namnamseo