아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

삶의 질

면접 대비

시간 제한5초메모리 제한256 MB

요약
R행 C열 격자에 적힌 1부터 R×C까지 수에서 H행 W열 부분 직사각형들의 중앙값 중 가장 작은 값을 구합니다.
난이도

보통10점 중 6점

유형
이분 탐색, 누적 합, 행렬
정답자
아직 제출이 없습니다

문제

Alberta 시는 직사각형 격자 모양의 블록으로 설계되어 있다. 행 번호는 가장 북쪽 00번부터 가장 남쪽 R−1R-1번까지, 열 번호는 가장 서쪽 00번부터 가장 동쪽 C−1C-1번까지 붙는다.

각 블록의 삶의 질은 11부터 R×CR \times C까지의 서로 다른 수 하나로 나타내고, 이 수를 quality rank라고 한다. quality rank가 11인 블록의 삶의 질이 가장 좋고, R×CR \times C인 블록이 가장 나쁘다.

홍준이는 격자 안에 완전히 들어가는 H×WH \times W 영역만 살펴본다. HH와 WW는 홀수이고, 1≤H≤R1 \le H \le R, 1≤W≤C1 \le W \le C를 만족한다. 홀수 개의 quality rank 중에서 중간값 mm은 mm보다 좋은 랭크의 개수와 mm보다 나쁜 랭크의 개수가 같은 값으로 정의한다.

H×WH \times W 영역마다 quality rank의 중간값이 하나씩 정해진다. 그 중간값 중에서 삶의 질이 가장 좋은 값, 즉 가장 작은 값을 찾는 프로그램을 작성하시오.

입력

첫째 줄에 정수 RR, CC, HH, WW가 공백으로 구분되어 주어진다. RR과 CC는 도시의 행과 열의 개수이고, HH와 WW는 홍준이가 정한 영역의 행과 열의 개수이다. HH와 WW는 홀수이며 1≤H≤R1 \le H \le R, 1≤W≤C1 \le W \le C이다.

다음 RR개의 줄에는 각각 CC개의 정수가 주어진다. ii번째 줄의 jj번째 수는 행 번호 i−1i-1, 열 번호 j−1j-1인 블록의 quality rank이다. 격자에 적힌 R×CR \times C개의 수는 11부터 R×CR \times C까지의 정수가 한 번씩 나타난 것이다.

출력

첫째 줄에 H×WH \times W 영역의 중간값 중 가장 작은 값을 출력한다.

예제4

  1. 예제 1

    입력
    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

  2. 예제 2

    입력
    1 1 1 1
1
    예상 출력
    1

  3. 예제 3

    입력
    3 3 3 3
7 2 3
9 1 8
4 5 6
    예상 출력
    5

  4. 예제 4

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