문제
Alberta 시에서는 도시가 직사각형 격자 모양의 블록으로 설계되어 있다.
블록은 가장 북쪽 0번부터 가장 남쪽 R-1번까지(행의 번호), 가장 서쪽 0번부터 가장 동쪽 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는 각각 홍준이가 정한 영역에서의 행과 열의 크기이다.
H, W 는 모두 홀수다.
그 다음 R개의 줄에 각각 C개의 quality rank를 나타내는 정수가 주어진다. 모든 quality rank 끼리는 서로 다르다.
출력
첫째 줄에 quality rank의 중간값 중 가장 질이 높은 값 ( 숫자의 최솟값 )을 출력한다.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 20점 | 1 ≤ R, C ≤ 30 |
| #2 | 20점 | 1 ≤ R, C ≤ 100 |
| #3 | 20점 | 1 ≤ R, C ≤ 300 |
| #4 | 20점 | 1 ≤ R, C ≤ 1000 |
| #5 | 20점 | 1 ≤ R, C ≤ 3000 |
예제
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
로그인해야 코드를 작성할 수 있어요.