시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 256 MB 278 135 79 44.633%

문제

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를 나타내는 정수가 주어진다. (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+QWxiZXJ0YSBcdWMyZGNcdWM1ZDBcdWMxMWNcdWIyOTQgXHViM2M0XHVjMmRjXHVhYzAwIFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNSBcdWFjYTlcdWM3OTBcdWJhYThcdWM1OTFcdWM3NTggXHViZTE0XHViODVkXHVjNzNjXHViODVjIFx1YzEyNFx1YWNjNFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyZTQuIFx1YmUxNFx1Yjg1ZFx1Yzc0MCBcdWFjMDBcdWM3YTUgXHViZDgxXHVjYWJkIDBcdWJjODhcdWJkODBcdWQxMzAgXHVhYzAwXHVjN2E1IFx1YjBhOFx1Y2FiZCBSLTFcdWJjODhcdWFlNGNcdWM5YzAoXHVkNTg5XHVjNzU4IFx1YmM4OFx1ZDYzOCksIFx1YWMwMFx1YzdhNSBcdWMxMWNcdWNhYmQgMFx1YmM4OFx1YmQ4MFx1ZDEzMCBcdWFjMDBcdWM3YTUgXHViM2Q5XHVjYWJkIEMtMVx1YmM4OFx1YWU0Y1x1YzljMFx1Yjg1YyhcdWM1ZjRcdWM3NTggXHViYzg4XHVkNjM4KSBcdWIwOThcdWIyMDRcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHViZTE0XHViODVkXHVjNWQwXHVjMTFjIFx1YzBiNlx1Yzc1OCBcdWM5YzhcdWM3NDAgMVx1YzVkMFx1YzExYyBSJnRpbWVzO0MgXHVjMGFjXHVjNzc0XHVjNzU4IFx1YzcyMFx1Yzc3Y1x1ZDU1YyBcdWMyMThcdWI4NWMgXHVkNDVjXHVkNjA0XHViNDE4XHViYTcwLCBcdWM3NzRcdWI5N2MgcXVhbGl0eSByYW5rXHViNzdjIFx1ZDU1Y1x1YjJlNC4gMVx1Yjg1YyBcdWQ0NWNcdWQ2MDRcdWI0MWMgXHVjMGI2XHVjNzU4IFx1YzljOFx1Yzc3NCBcdWFjMDBcdWM3YTUgXHVjODhiXHVjNzQwIHF1YWxpdHkgcmFua1x1Yzc3NFx1YWNlMCwgUiZ0aW1lcztDXHVjNzQwIFx1YWMwMFx1YzdhNSBcdWIwOThcdWMwNWMgcXVhbGl0eSByYW5rXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQ2NGRcdWM5MDBcdWM3NzRcdWIyOTQgSCZ0aW1lcztXICgxICZsZTsgSCAmbGU7IFIsIDEgJmxlOyBXICZsZTsgQylcdWM3NTggXHVjNjAxXHVjNWVkXHVjNWQwXHVjMTFjIHF1YWxpdHkgcmFua1x1Yzc1OCBcdWM5MTFcdWFjMDRcdWFjMTIgXHVjOTExIFx1YWMwMFx1YzdhNSBcdWM5YzhcdWM3NzQgXHViMTkyXHVjNzQwKFx1YzIxOFx1Yzc1OCBcdWQwNmNcdWFlMzBcdWIyOTQgXHVhYzAwXHVjN2E1IFx1Yzc5MVx1Yzc0MCkgXHVhYzEyXHVjNzQ0IFx1Y2MzZVx1YzczY1x1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIEhcdWM2NDAgV1x1YjI5NCBcdWQ2NDBcdWMyMThcdWM3NzRcdWFjZTAgXHVhYzAxXHVhYzAxXHVjNzQwIFJcdWFjZmMgQ1x1Yjk3YyBcdWNkMDhcdWFjZmNcdWQ1NThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LiBcdWQ2NDBcdWMyMThcdWFjMWNcdWM3NTggcXVhbGl0eSByYW5rXHViNGU0IFx1YzkxMVx1YzVkMFx1YzExYyBcdWM5MTFcdWFjMDRcdWFjMTIgbVx1Yzc0MCBtXHViY2Y0XHViMmU0IFx1YjM1NCBcdWM4OGJcdWM3NDAgXHViN2FkXHVkMDZjXHVjNzU4IFx1YzIxOFx1YzY0MCBtXHViY2Y0XHViMmU0IFx1YjM1NCBcdWIwOThcdWMwNWMgXHViN2FkXHVkMDZjXHVjNzU4IFx1YzIxOFx1YWMwMCBcdWFjMTlcdWM3NDAgXHVhYzgzXHVjNzNjXHViODVjIFx1YzgxNVx1Yzc1OFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNjRkXHVjOTAwXHVjNzc0XHViOTdjIFx1YjNjNFx1YzY0MCBIJnRpbWVzO1dcdWM3NTggXHVkMDZjXHVhZTMwXHViOTdjIFx1YWMwMFx1YzljMFx1YjI5NCBcdWM2MDFcdWM1ZWRcdWI0ZTQgXHVjOTExXHVjNWQwXHVjMTFjIHF1YWxpdHkgcmFua1x1Yzc1OCBcdWM5MTFcdWFjMDRcdWFjMTIgXHVjOTExIFx1YWMwMFx1YzdhNSBcdWM5YzhcdWM3NzQgXHViMTkyXHVjNzQwIFx1YWMxMlx1Yzc0NCBcdWNjM2VcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgNFx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMTggUiwgQywgSCwgVyBcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBSXHVhY2ZjIENcdWIyOTQgXHVhYzAxXHVhYzAxIFx1YjNjNFx1YzJkY1x1Yzc1OCBcdWQ1ODlcdWFjZmMgXHVjNWY0XHVjNzU4IFx1ZDA2Y1x1YWUzMFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWFjZTAsIEhcdWM2NDAgV1x1YjI5NCBcdWFjMDFcdWFjMDEgXHVkNjRkXHVjOTAwXHVjNzc0XHVhYzAwIFx1YzgxNVx1ZDU1YyBcdWM2MDFcdWM1ZWRcdWM1ZDBcdWMxMWNcdWM3NTggXHVkNTg5XHVhY2ZjIFx1YzVmNFx1Yzc1OCBcdWQwNmNcdWFlMzBcdWM3NzRcdWIyZTQuIFx1YWRmOCBcdWIyZTRcdWM3NGMgUlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVhYzAxXHVhYzAxIENcdWFjMWNcdWM3NTggcXVhbGl0eSByYW5rXHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWM4MTVcdWMyMThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IFIsIEMgJmxlOyAzMDAwKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgcXVhbGl0eSByYW5rXHVjNzU4IFx1YzkxMVx1YWMwNFx1YWMxMiBcdWM5MTEgXHVhYzAwXHVjN2E1IFx1YzljOFx1Yzc3NCBcdWIxOTJcdWM3NDAgXHVhYzEyXHVjNzQ0Jm5ic3A7XHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjEwMjI3IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUXVhbGl0eSBvZiBMaXZpbmciLCJkZXNjcmlwdGlvbiI6IjxwPkNpdGllcyBpbiBBbGJlcnRhIHRlbmQgdG8gYmUgbGFpZCBvdXQgYXMgcmVjdGFuZ3VsYXIgZ3JpZHMgb2YgYmxvY2tzLiBCbG9ja3MgYXJlIGxhYmVsZWQgd2l0aCBjb29yZGluYXRlcyAwIHRvIFImbWludXM7MSBmcm9tIG5vcnRoIHRvIHNvdXRoIGFuZCAwIHRvIEMmbWludXM7MSBmcm9tIHdlc3QgdG8gZWFzdC48XC9wPlxyXG5cclxuPHA+VGhlIHF1YWxpdHkgb2YgbGl2aW5nIGluIGVhY2ggcGFydGljdWxhciBibG9jayBoYXMgYmVlbiByYW5rZWQgYnkgYSBkaXN0aW5jdCBudW1iZXIsIGNhbGxlZCBxdWFsaXR5IHJhbmssIGJldHdlZW4gMSBhbmQgUipDLCB3aGVyZSAxIGlzIHRoZSBiZXN0IGFuZCBSKkMgaXMgdGhlIHdvcnN0LjxcL3A+XHJcblxyXG48cD5UaGUgY2l0eSBwbGFubmluZyBkZXBhcnRtZW50IHdpc2hlcyB0byBpZGVudGlmeSBhIHJlY3Rhbmd1bGFyIHNldCBvZiBibG9ja3Mgd2l0aCBkaW1lbnNpb25zIEggZnJvbSBub3J0aCB0byBzb3V0aCBhbmQgVyBmcm9tIHdlc3QgdG8gZWFzdCwgc3VjaCB0aGF0IHRoZSBtZWRpYW4gcXVhbGl0eSByYW5rIGFtb25nIGFsbCBibG9ja3MgaW4gdGhlIHJlY3RhbmdsZSBpcyB0aGUgYmVzdC48XC9wPlxyXG5cclxuPHA+SCBhbmQgVyBhcmUgb2RkIG51bWJlcnMgbm90IGV4Y2VlZGluZyBSIGFuZCBDIHJlc3BlY3RpdmVseS4gVGhlIG1lZGlhbiBxdWFsaXR5IHJhbmsgYW1vbmcgYW4gb2RkIG51bWJlciBvZiBxdWFsaXR5IHJhbmtzIGlzIGRlZmluZWQgdG8gYmUgdGhlIHF1YWxpdHkgcmFuayBtIGluIHRoZSBzZXQgc3VjaCB0aGF0IHRoZSBudW1iZXIgb2YgcXVhbGl0eSByYW5rcyBiZXR0ZXIgdGhhbiBtIGVxdWFscyB0aGUgbnVtYmVyIG9mIHF1YWxpdHkgcmFua3Mgd29yc2UgdGhhbiBtLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgd2lsbCBjb250YWluIHRoZSBmb3VyIGludGVnZXJzIFIgQyBIIFcsIHdoZXJlIFIgYW5kIEMgcmVwcmVzZW50IHRoZSB0b3RhbCBzaXplIG9mIHRoZSBjaXR5LCBhbmQgSCBhbmQgVyByZXByZXNlbnQgdGhlIGRpbWVuc2lvbnMgb2YgdGhlIHNldCBvZiBibG9ja3MuPFwvcD5cclxuXHJcbjxwPlRoZSBuZXh0IFIgbGluZXMgZWFjaCBjb250YWluIEMgaW50ZWdlcnMsIGRlbm90aW5nIGFuIGFycmF5IFEgd2hlcmUgUVthXVtiXSBpcyB0aGUgcXVhbGl0eSByYW5rIGZvciB0aGUgYmxvY2sgbGFiZWxlZCBhIGZyb20gbm9ydGggdG8gc291dGggYW5kIGIgZnJvbSB3ZXN0IHRvIGVhc3QuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+QSBzaW5nbGUgaW50ZWdlciwgdGhlIGJlc3QgKG51bWVyaWNhbGx5IHNtYWxsZXN0KSBwb3NzaWJsZSBtZWRpYW4gcXVhbGl0eSByYW5rIG9mIGFuIEggYnkgVyByZWN0YW5nbGUgb2YgYmxvY2tzLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

Olympiad > International Olympiad in Informatics > IOI 2010 3번

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