시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 256 MB 130 55 36 38.298%

문제

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의 중간값 중 가장 질이 높은 값을 찾을 출력한다.

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

예제 출력 1

9
W3sicHJvYmxlbV9pZCI6IjEwMjI3IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjMGI2XHVjNzU4IFx1YzljOCIsImRlc2NyaXB0aW9uIjoiPHA+QWxiZXJ0YSBcdWMyZGNcdWM1ZDBcdWMxMWNcdWIyOTQgXHViM2M0XHVjMmRjXHVhYzAwIFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNSBcdWFjYTlcdWM3OTBcdWJhYThcdWM1OTFcdWM3NTggXHViZTE0XHViODVkXHVjNzNjXHViODVjIFx1YzEyNFx1YWNjNFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyZTQuIFx1YmUxNFx1Yjg1ZFx1Yzc0MCBcdWFjMDBcdWM3YTUgXHViZDgxXHVjYWJkIDBcdWJjODhcdWJkODBcdWQxMzAgXHVhYzAwXHVjN2E1IFx1YjBhOFx1Y2FiZCBSLTFcdWJjODhcdWFlNGNcdWM5YzAoXHVkNTg5XHVjNzU4IFx1YmM4OFx1ZDYzOCksIFx1YWMwMFx1YzdhNSBcdWMxMWNcdWNhYmQgXHViYzg4XHViZDgwXHVkMTMwIFx1YWMwMFx1YzdhNSBcdWIzZDlcdWNhYmQgQy0xXHViYzg4XHVhZTRjXHVjOWMwXHViODVjKFx1YzVmNFx1Yzc1OCBcdWJjODhcdWQ2MzgpIFx1YjA5OFx1YjIwNFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWJlMTRcdWI4NWRcdWM1ZDBcdWMxMWMgXHVjMGI2XHVjNzU4IFx1YzljOFx1Yzc0MCAxXHVjNWQwXHVjMTFjIFImdGltZXM7QyBcdWMwYWNcdWM3NzRcdWM3NTggXHVjNzIwXHVjNzdjXHVkNTVjIFx1YzIxOFx1Yjg1YyBcdWQ0NWNcdWQ2MDRcdWI0MThcdWJhNzAsIFx1Yzc3NFx1Yjk3YyBxdWFsaXR5IHJhbmtcdWI3N2MgXHVkNTVjXHViMmU0LiAxXHViODVjIFx1ZDQ1Y1x1ZDYwNFx1YjQxYyBcdWMwYjZcdWM3NTggXHVjOWM4XHVjNzc0IFx1YWMwMFx1YzdhNSBcdWM4OGJcdWM3NDAgcXVhbGl0eSByYW5rXHVjNzc0XHVhY2UwLCBSJnRpbWVzO0NcdWM3NDAgXHVhYzAwXHVjN2E1IFx1YjA5OFx1YzA1YyBxdWFsaXR5IHJhbmtcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDY0ZFx1YzkwMFx1Yzc3NFx1YjI5NCBIJnRpbWVzO1cgKDEgJmxlOyBIICZsZTsgUiwgMSAmbGU7IFcgJmxlOyBDKVx1Yzc1OCBcdWM2MDFcdWM1ZWRcdWM1ZDBcdWMxMWMgcXVhbGl0eSByYW5rXHVjNzU4IFx1YzkxMVx1YWMwNFx1YWMxMiBcdWM5MTEgXHVhYzAwXHVjN2E1IFx1YzljOFx1Yzc3NCBcdWIxOTJcdWM3NDAoXHVjMjE4XHVjNzU4IFx1ZDA2Y1x1YWUzMFx1YjI5NCBcdWFjMDBcdWM3YTUgXHVjNzkxXHVjNzQwKSBcdWFjMTJcdWM3NDQgXHVjYzNlXHVjNzNjXHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gSFx1YzY0MCBXXHViMjk0IFx1ZDY0MFx1YzIxOFx1Yzc3NFx1YWNlMCBcdWFjMDFcdWFjMDFcdWM3NDAgUlx1YWNmYyBDXHViOTdjIFx1Y2QwOFx1YWNmY1x1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuIFx1ZDY0MFx1YzIxOFx1YWMxY1x1Yzc1OCBxdWFsaXR5IHJhbmtcdWI0ZTQgXHVjOTExXHVjNWQwXHVjMTFjIFx1YzkxMVx1YWMwNFx1YWMxMiBtXHVjNzQwIG1cdWJjZjRcdWIyZTQgXHViMzU0IFx1Yzg4Ylx1Yzc0MCBcdWI3YWRcdWQwNmNcdWM3NTggXHVjMjE4XHVjNjQwIG1cdWJjZjRcdWIyZTQgXHViMzU0IFx1YjA5OFx1YzA1YyBcdWI3YWRcdWQwNmNcdWM3NTggXHVjMjE4XHVhYzAwIFx1YWMxOVx1Yzc0MCBcdWFjODNcdWM3M2NcdWI4NWMgXHVjODE1XHVjNzU4XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQ2NGRcdWM5MDBcdWM3NzRcdWI5N2MgXHViM2M0XHVjNjQwIEgmdGltZXM7V1x1Yzc1OCBcdWQwNmNcdWFlMzBcdWI5N2MgXHVhYzAwXHVjOWMwXHViMjk0IFx1YzYwMVx1YzVlZFx1YjRlNCBcdWM5MTFcdWM1ZDBcdWMxMWMgcXVhbGl0eSByYW5rXHVjNzU4IFx1YzkxMVx1YWMwNFx1YWMxMiBcdWM5MTEgXHVhYzAwXHVjN2E1IFx1YzljOFx1Yzc3NCBcdWIxOTJcdWM3NDAgXHVhYzEyXHVjNzQ0IFx1Y2MzZVx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCA0XHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOCBSLCBDLCBILCBXIFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFJcdWFjZmMgQ1x1YjI5NCBcdWFjMDFcdWFjMDEgXHViM2M0XHVjMmRjXHVjNzU4IFx1ZDU4OVx1YWNmYyBcdWM1ZjRcdWM3NTggXHVkMDZjXHVhZTMwXHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YWNlMCwgSFx1YzY0MCBXXHViMjk0IFx1YWMwMVx1YWMwMSBcdWQ2NGRcdWM5MDBcdWM3NzRcdWFjMDAgXHVjODE1XHVkNTVjIFx1YzYwMVx1YzVlZFx1YzVkMFx1YzExY1x1Yzc1OCBcdWQ1ODlcdWFjZmMgXHVjNWY0XHVjNzU4IFx1ZDA2Y1x1YWUzMFx1Yzc3NFx1YjJlNC4gXHVhZGY4IFx1YjJlNFx1Yzc0YyBSXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBcdWFjMDFcdWFjMDEgQ1x1YWMxY1x1Yzc1OCBxdWFsaXR5IHJhbmtcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1YzgxNVx1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgUiwgQyAmbGU7IDMwMDApPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBxdWFsaXR5IHJhbmtcdWM3NTggXHVjOTExXHVhYzA0XHVhYzEyIFx1YzkxMSBcdWFjMDBcdWM3YTUgXHVjOWM4XHVjNzc0IFx1YjE5Mlx1Yzc0MCBcdWFjMTJcdWM3NDQgXHVjYzNlXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxMDIyNyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlF1YWxpdHkgb2YgTGl2aW5nIiwiZGVzY3JpcHRpb24iOiI8cD5DaXRpZXMgaW4gQWxiZXJ0YSB0ZW5kIHRvIGJlIGxhaWQgb3V0IGFzIHJlY3Rhbmd1bGFyIGdyaWRzIG9mIGJsb2Nrcy4gQmxvY2tzIGFyZSBsYWJlbGVkIHdpdGggY29vcmRpbmF0ZXMgMCB0byBSJm1pbnVzOzEgZnJvbSBub3J0aCB0byBzb3V0aCBhbmQgMCB0byBDJm1pbnVzOzEgZnJvbSB3ZXN0IHRvIGVhc3QuPFwvcD5cclxuXHJcbjxwPlRoZSBxdWFsaXR5IG9mIGxpdmluZyBpbiBlYWNoIHBhcnRpY3VsYXIgYmxvY2sgaGFzIGJlZW4gcmFua2VkIGJ5IGEgZGlzdGluY3QgbnVtYmVyLCBjYWxsZWQgcXVhbGl0eSByYW5rLCBiZXR3ZWVuIDEgYW5kIFIqQywgd2hlcmUgMSBpcyB0aGUgYmVzdCBhbmQgUipDIGlzIHRoZSB3b3JzdC48XC9wPlxyXG5cclxuPHA+VGhlIGNpdHkgcGxhbm5pbmcgZGVwYXJ0bWVudCB3aXNoZXMgdG8gaWRlbnRpZnkgYSByZWN0YW5ndWxhciBzZXQgb2YgYmxvY2tzIHdpdGggZGltZW5zaW9ucyBIIGZyb20gbm9ydGggdG8gc291dGggYW5kIFcgZnJvbSB3ZXN0IHRvIGVhc3QsIHN1Y2ggdGhhdCB0aGUgbWVkaWFuIHF1YWxpdHkgcmFuayBhbW9uZyBhbGwgYmxvY2tzIGluIHRoZSByZWN0YW5nbGUgaXMgdGhlIGJlc3QuPFwvcD5cclxuXHJcbjxwPkggYW5kIFcgYXJlIG9kZCBudW1iZXJzIG5vdCBleGNlZWRpbmcgUiBhbmQgQyByZXNwZWN0aXZlbHkuIFRoZSBtZWRpYW4gcXVhbGl0eSByYW5rIGFtb25nIGFuIG9kZCBudW1iZXIgb2YgcXVhbGl0eSByYW5rcyBpcyBkZWZpbmVkIHRvIGJlIHRoZSBxdWFsaXR5IHJhbmsgbSBpbiB0aGUgc2V0IHN1Y2ggdGhhdCB0aGUgbnVtYmVyIG9mIHF1YWxpdHkgcmFua3MgYmV0dGVyIHRoYW4gbSBlcXVhbHMgdGhlIG51bWJlciBvZiBxdWFsaXR5IHJhbmtzIHdvcnNlIHRoYW4gbS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IHdpbGwgY29udGFpbiB0aGUgZm91ciBpbnRlZ2VycyBSIEMgSCBXLCB3aGVyZSBSIGFuZCBDIHJlcHJlc2VudCB0aGUgdG90YWwgc2l6ZSBvZiB0aGUgY2l0eSwgYW5kIEggYW5kIFcgcmVwcmVzZW50IHRoZSBkaW1lbnNpb25zIG9mIHRoZSBzZXQgb2YgYmxvY2tzLjxcL3A+XHJcblxyXG48cD5UaGUgbmV4dCBSIGxpbmVzIGVhY2ggY29udGFpbiBDIGludGVnZXJzLCBkZW5vdGluZyBhbiBhcnJheSBRIHdoZXJlIFFbYV1bYl0gaXMgdGhlIHF1YWxpdHkgcmFuayBmb3IgdGhlIGJsb2NrIGxhYmVsZWQgYSBmcm9tIG5vcnRoIHRvIHNvdXRoIGFuZCBiIGZyb20gd2VzdCB0byBlYXN0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkEgc2luZ2xlIGludGVnZXIsIHRoZSBiZXN0IChudW1lcmljYWxseSBzbWFsbGVzdCkgcG9zc2libGUgbWVkaWFuIHF1YWxpdHkgcmFuayBvZiBhbiBIIGJ5IFcgcmVjdGFuZ2xlIG9mIGJsb2Nrcy48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

Olympiad > International Olympiad in Informatics > IOI 2010 3번

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