시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 | 256 MB | 579 | 250 | 174 | 43.392% |
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는 각각 홍준이가 정한 영역에서의 행과 열의 크기이다. 그 다음 R개의 줄에 각각 C개의 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 ≤ 1 000 |
5 | 20 | 1 ≤ R, C ≤ 3 000 |
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