시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 55 21 17 44.737%

문제

화학이 싫어서 지구과학을 공부한 선영이가 기상예측을 하는 일을 맡게 되었다.

선영이가 기상예측을 해야 되는 지역은 N*M짜리 격자판이고 각각의 칸마다 기상예측을 하는데 걸리는 시간이 있다.

이때 선영이는 이 격자판을 적당히 나눠서 각각의 구간의 작업을 동시에 할 수 있는데 그러므로 나누어진 구간 중 작업시간의 합이 최대인 곳을 최소화 한다면 선영이의 작업량이 최소가 될 것이다. 이때 나누는 기준은 주어진 개수의 가로선과 세로선을 이용해서 나누면 된다.

가로로 나눌 수 있는 선의 개수가 주어지고 세로 역시 주어진다고 할 때 나누어진 구간의 합의 최대를 최소로 하는 나누는 방법을 구하라.

입력

첫줄에는 n, m, r, s(1<=r<n<=18, 1<=s<m<=18) 가 주어지는데 n, m은 지역의 가로, 세로크기, r, s는 가로로 나누는 수, 세로로 나누는 수를 의미한다. 그 뒤로는 각각의 칸을 예측하는데 걸리는 시간이 주어진다(2000000이하)

출력

선영이가 결과를 구하는데 걸리는 최소의 시간을 출력한다.

예제 입력 1

7 8 2 1
0 0 2 6 1 1 0 0
1 4 4 4 4 4 3 0
2 4 4 4 4 4 3 0
1 4 4 4 8 4 4 0
0 3 4 4 4 4 4 3
0 1 1 3 4 4 3 0
0 0 0 1 2 1 2 0

예제 출력 1

31
W3sicHJvYmxlbV9pZCI6IjEyMDAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFlMzBcdWMwYzFcdWM2MDhcdWNlMjEiLCJkZXNjcmlwdGlvbiI6IjxwPlx1ZDY1NFx1ZDU1OVx1Yzc3NCBcdWMyZWJcdWM1YjRcdWMxMWMgXHVjOWMwXHVhZDZjXHVhY2ZjXHVkNTU5XHVjNzQ0IFx1YWNmNVx1YmQ4MFx1ZDU1YyBcdWMxMjBcdWM2MDFcdWM3NzRcdWFjMDAgXHVhZTMwXHVjMGMxXHVjNjA4XHVjZTIxXHVjNzQ0IFx1ZDU1OFx1YjI5NCBcdWM3N2NcdWM3NDQgXHViOWUxXHVhYzhjIFx1YjQxOFx1YzVjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMTIwXHVjNjAxXHVjNzc0XHVhYzAwIFx1YWUzMFx1YzBjMVx1YzYwOFx1Y2UyMVx1Yzc0NCBcdWQ1NzRcdWM1N2MgXHViNDE4XHViMjk0IFx1YzljMFx1YzVlZFx1Yzc0MCBOKk1cdWM5ZGNcdWI5YWMgXHVhY2E5XHVjNzkwXHVkMzEwXHVjNzc0XHVhY2UwIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWNlNzhcdWI5YzhcdWIyZTQgXHVhZTMwXHVjMGMxXHVjNjA4XHVjZTIxXHVjNzQ0IFx1ZDU1OFx1YjI5NFx1YjM3MCBcdWFjNzhcdWI5YWNcdWIyOTQgXHVjMmRjXHVhYzA0XHVjNzc0IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0XHViNTRjIFx1YzEyMFx1YzYwMVx1Yzc3NFx1YjI5NCBcdWM3NzQgXHVhY2E5XHVjNzkwXHVkMzEwXHVjNzQ0IFx1YzgwMVx1YjJmOVx1ZDc4OCBcdWIwOThcdWIyMjBcdWMxMWMgXHVhYzAxXHVhYzAxXHVjNzU4IFx1YWQ2Y1x1YWMwNFx1Yzc1OCBcdWM3OTFcdWM1YzVcdWM3NDQgXHViM2Q5XHVjMmRjXHVjNWQwIFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0XHViMzcwIFx1YWRmOFx1YjdlY1x1YmJjMFx1Yjg1YyBcdWIwOThcdWIyMDRcdWM1YjRcdWM5YzQgXHVhZDZjXHVhYzA0IFx1YzkxMSBcdWM3OTFcdWM1YzVcdWMyZGNcdWFjMDRcdWM3NTggXHVkNTY5XHVjNzc0IFx1Y2Q1Y1x1YjMwMFx1Yzc3OCBcdWFjZjNcdWM3NDQgXHVjZDVjXHVjMThjXHVkNjU0IFx1ZDU1Y1x1YjJlNFx1YmE3NCBcdWMxMjBcdWM2MDFcdWM3NzRcdWM3NTggXHVjNzkxXHVjNWM1XHViN2M5XHVjNzc0IFx1Y2Q1Y1x1YzE4Y1x1YWMwMCBcdWI0MjAgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWM3NzRcdWI1NGMgXHViMDk4XHViMjA0XHViMjk0IFx1YWUzMFx1YzkwMFx1Yzc0MCBcdWM4ZmNcdWM1YjRcdWM5YzQgXHVhYzFjXHVjMjE4XHVjNzU4IFx1YWMwMFx1Yjg1Y1x1YzEyMFx1YWNmYyBcdWMxMzhcdWI4NWNcdWMxMjBcdWM3NDQgXHVjNzc0XHVjNmE5XHVkNTc0XHVjMTFjIFx1YjA5OFx1YjIwNFx1YmE3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMFx1Yjg1Y1x1Yjg1YyBcdWIwOThcdWIyMGMgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWMxMjBcdWM3NTggXHVhYzFjXHVjMjE4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljMFx1YWNlMCBcdWMxMzhcdWI4NWMgXHVjNWVkXHVjMmRjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNFx1YWNlMCBcdWQ1NjAgXHViNTRjIFx1YjA5OFx1YjIwNFx1YzViNFx1YzljNCBcdWFkNmNcdWFjMDRcdWM3NTggXHVkNTY5XHVjNzU4IFx1Y2Q1Y1x1YjMwMFx1Yjk3YyBcdWNkNWNcdWMxOGNcdWI4NWMgXHVkNTU4XHViMjk0IFx1YjA5OFx1YjIwNFx1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NDQgXHVhZDZjXHVkNTU4XHViNzdjLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOTA0XHVjNWQwXHViMjk0IG4sIG0sIHIsIHMoMSZsdDs9ciZsdDtuJmx0Oz0xOCwgMSZsdDs9cyZsdDttJmx0Oz0xOCkgXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NFx1YjM3MCBuLCBtXHVjNzQwIFx1YzljMFx1YzVlZFx1Yzc1OCBcdWFjMDBcdWI4NWMsIFx1YzEzOFx1Yjg1Y1x1ZDA2Y1x1YWUzMCwgciwgc1x1YjI5NCBcdWFjMDBcdWI4NWNcdWI4NWMgXHViMDk4XHViMjA0XHViMjk0IFx1YzIxOCwgXHVjMTM4XHViODVjXHViODVjIFx1YjA5OFx1YjIwNFx1YjI5NCBcdWMyMThcdWI5N2MgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0LiBcdWFkZjggXHViNGE0XHViODVjXHViMjk0IFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWNlNzhcdWM3NDQgXHVjNjA4XHVjZTIxXHVkNTU4XHViMjk0XHViMzcwIFx1YWM3OFx1YjlhY1x1YjI5NCBcdWMyZGNcdWFjMDRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0KDIwMDAwMDBcdWM3NzRcdWQ1NTgpPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjMTIwXHVjNjAxXHVjNzc0XHVhYzAwIFx1YWNiMFx1YWNmY1x1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTRcdWIzNzAgXHVhYzc4XHViOWFjXHViMjk0IFx1Y2Q1Y1x1YzE4Y1x1Yzc1OCBcdWMyZGNcdWFjMDRcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjEyMDAiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJHcmlkIiwiZGVzY3JpcHRpb24iOiI8cD5UaGUgbWFwIG9mIEJ5dGVsYW5kIGlzIGRyYXduIG9uIGEgZ3JpZCBvZiBzaXplIG4gJnRpbWVzOyBtIChuIGlzIHRoZSB2ZXJ0aWNhbCBkaW1lbnNpb24sIG0gaXMgdGhlIGhvcml6b250YWwgZGltZW5zaW9uKS4gVGhlIGhvcml6b250YWwgbGluZXMgbWFya2luZyB0aGUgZGl2aXNpb24gYXJlIGNhbGxlZCBwYXJhbGxlbHMsIGFuZCBhcmUgbnVtYmVyZWQgZnJvbSAwIHRvIG4sIHdoaWxlIHRoZSB2ZXJ0aWNhbCBsaW5lcyBvZiB0aGUgZGl2aXNpb24gYXJlIGNhbGxlZCBtZXJpZGlhbnMsIGFuZCBhcmUgbnVtYmVyZWQgZnJvbSAwIHRvIG0gKHNlZSBcdWZiMDFndXJlIG9uIHRoZSBuZXh0IHBhZ2UpLjxcL3A+XHJcblxyXG48cD5XZWF0aGVyIGZvcmVjYXN0aW5nIGlzIGEgc2VyaW91cyBpc3N1ZSBpbiBCeXRlbGFuZC4gRm9yIGVhY2ggdW5pdCBzcXVhcmUgb2YgdGhlIGdyaWQgYSBjZXJ0YWluIGFtb3VudCBvZiBjb21wdXRhdGlvbiB0aW1lIGlzIHJlcXVpcmVkIHRvIHByZXBhcmUgdGhlIGZvcmVjYXN0LiBEdWUgdG8gdGVycmFpbiBjb25kaXRpb25zIGFuZCBvdGhlciBmYWN0b3JzIHRoaXMgdGltZSBtYXkgdmFyeSBmcm9tIHNxdWFyZSB0byBzcXVhcmUuIFVudGlsIHZlcnkgcmVjZW50bHkgdGhlIGZvcmVjYXN0aW5nIHN5c3RlbSB3YXMgcHJvY2Vzc2luZyB0aGUgdW5pdCBzcXVhcmVzIG9uZSBhZnRlciBhbm90aGVyLCBzbyBpdCB0b29rIGFzIGxvbmcgYXMgdGhlIHN1bSBvZiBhbGwgdGhlIHVuaXQgdGltZXMgdG8gcHJlcGFyZSB0aGUgY29tcGxldGUgZm9yZWNhc3QuPFwvcD5cclxuXHJcbjxwPllvdSBoYXZlIGJlZW4gYXNrZWQgdG8gZGVzaWduIGEgbmV3IHN5c3RlbSwgcnVubmluZyBvbiBhIG11bHRpcHJvY2Vzc29yIGNvbXB1dGVyLiBUbyBzaGFyZSB0aGUgY29tcHV0YXRpb25zIGFtb25nIHByb2Nlc3NvcnMsIHRoZSBhcmVhIG9mIEJ5dGVsYW5kIHNob3VsZCBiZSBkaXZpZGVkIGJ5IHIgcGFyYWxsZWxzIGFuZCBzIG1lcmlkaWFucyBpbnRvIChyICsgMSkocyArIDEpIHNtYWxsZXIgcmVjdGFuZ2xlcy4gRWFjaCBwcm9jZXNzb3Igd2lsbCBjb3ZlciBvbmUgcmVjdGFuZ2xlIG9mIHRoaXMgZGl2aXNpb24gYW5kIHdpbGwgcHJvY2VzcyB0aGUgc3F1YXJlcyBvZiB0aGlzIHJlY3RhbmdsZSBvbmUgYWZ0ZXIgYW5vdGhlci4gVGhpcyB3YXkgdGhlIGNvbXB1dGF0aW9uIHRpbWUgZm9yIHN1Y2ggcmVjdGFuZ2xlIHdpbGwgYmUgdGhlIHN1bSBvZiBhbGwgY29tcHV0YXRpb24gdGltZXMgb2YgdGhlIHVuaXQgc3F1YXJlcyBjb250YWluZWQgaW4gdGhpcyByZWN0YW5nbGUuIFRoZSBjb21wdXRhdGlvbiB0aW1lIG9mIHRoZSBjb21wbGV0ZSBmb3JlY2FzdCB3aWxsIGJlIHRoZSBtYXhpbXVtIGFtb25nIGNvbXB1dGF0aW9uIHRpbWVzIG9mIHRoZSBpbmRpdmlkdWFsIHByb2Nlc3NvcnMuPFwvcD5cclxuXHJcbjxwPllvdXIgdGFzayBpcyB0byBcdWZiMDFuZCB0aGUgbWluaW1hbCBwb3NzaWJsZSBjb21wdXRhdGlvbiB0aW1lIGZvciBzb21lIGNob2ljZSBvZiByIHBhcmFsbGVscyBhbmQgcyBtZXJpZGlhbnMuPFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSwgdGhhdDo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5yZWFkcyB0aGUgZGltZW5zaW9ucyBvZiB0aGUgbWFwIG9mIEJ5dGVsYW5kLCB0aGUgcmVxdWlyZWQgbnVtYmVyIG9mIHBhcmFsbGVscyBhbmQgbWVyaWRpYW5zIGFuZCB0aGUgdW5pdCBjb21wdXRhdGlvbiB0aW1lcyBmcm9tIHRoZSBzdGFuZGFyZCBpbnB1dCw8XC9saT5cclxuXHQ8bGk+XHVmYjAxbmRzIHRoZSBtaW5pbWFsIHRpbWUgcmVxdWlyZWQgdG8gY29tcHV0ZSB0aGUgY29tcGxldGUgZm9yZWNhc3QsPFwvbGk+XHJcblx0PGxpPndyaXRlcyB0aGUgb2J0YWluZWQgdmFsdWUgdG8gdGhlIHN0YW5kYXJkIG91dHB1dC48XC9saT5cclxuPFwvdWw+XHJcbiIsImlucHV0IjoiPHA+VGhlIFx1ZmIwMXJzdCBsaW5lIG9mIHRoZSBpbnB1dCBjb250YWlucyBmb3VyIGludGVnZXJzIG4sIG0sIHIgYW5kIHMsIHNlcGFyYXRlZCBieSBzaW5nbGUgc3BhY2VzICgxICZsZTsgciAmbHQ7IG4gJmxlOyAxOCAsIDEgJmxlOyBzICZsdDsgbSAmbGU7IDE4ICkuIFRoZSBmb2xsb3dpbmcgbiBsaW5lcyBjb250YWluIHRoZSBjb21wdXRhdGlvbiB0aW1lcyBvZiB0aGUgdW5pdCBzcXVhcmVzLiBUaGUgai10aCBudW1iZXIgaW4gdGhlIChpICsgMSktc3QgbGluZSBpcyBjPHN1Yj5pLGo8XC9zdWI+ICZtZGFzaDsgdGhlIHRpbWUgcmVxdWlyZWQgdG8gcHJlcGFyZSB0aGUgd2VhdGhlciBmb3JlY2FzdCBmb3IgdGhlIHVuaXQgc3F1YXJlIGxvY2F0ZWQgYmV0d2VlbiB0aGUgKGkgJm1pbnVzOyAxKS1zdCBhbmQgaS10aCBwYXJhbGxlbCBhbmQgYmV0d2VlbiB0aGUgKGogJm1pbnVzOyAxKS1zdCBhbmQgai10aCBtZXJpZGlhbiAoMSAmbGU7IGkgJmxlOyBuLCAxICZsZTsgaiAmbGU7IG0sIDAgJmxlOyBjPHN1Yj5pLGo8XC9zdWI+ICZsZTsgMiAwMDAgMDAwICkuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+WW91ciBwcm9ncmFtIHNob3VsZCB3cml0ZSBleGFjdGx5IG9uZSBsaW5lLiBJdCBzaG91bGQgY29udGFpbiBvbmUgaW50ZWdlciAmbWRhc2g7IHRoZSBvcHRpbWFsIGNvbXB1dGF0aW9uIHRpbWUuPFwvcD5cclxuIiwiaGludCI6IjxwPlRoZSAyLW5kIGFuZCA0LXRoIHBhcmFsbGVsIGFuZCB0aGUgNC10aCBtZXJpZGlhbiBkaXZpZGUgdGhlIGNvdW50cnkgaW50byA2IHJlY3RhbmdsZXMgd2l0aCBjb21wdXRhdGlvbiB0aW1lcyAyMSwgMTMsIDI3LCAyNywgMTcsIDMxLiBUaGUgY29tcHV0YXRpb24gdGltZSBvZiB0aGUgY29tcGxldGUgZm9yZWNhc3QgaXMgMzEuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2008 5번