시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 32 MB 2 2 2 100.000%

문제

정수로 이루어진 N * M 행렬이 주어질 때, 당신은 K개의 겹치지 않는 부분행렬을 골라서, 부분행렬 안에 속하는 원소들의 합을 최대화하려고 한다.

입력

첫번째 줄에 N, M, K가 주어진다. 행렬의 크기와, 고를 부분행렬의 수를 뜻한다. (1 <= K <= 3, K <= N, M <= 300)

이후 N개의 줄에 M개의 수가 주어진다, i번 행 j번 열의 원소 aij (−20 000 ≤ aij ≤ 20 000) 를 뜻한다.

부분행렬은, 행렬 내의 부분 직사각형 격자를 뜻한다. 두 부분행렬이 겹침은, 공통 원소를 포함함을 뜻한다.

출력

부분행렬에 속하는 모든 원소들의 합의 최댓값을 출력하라.

예제 입력 1

4 5 2
6 -10 0 3 -6
-8 8 1 -5 3
-7 -3 2 4 -4
2 0 -1 3 -3

예제 출력 1

17

힌트

W3sicHJvYmxlbV9pZCI6Ijc3MjYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjMWNcdWFmYzBcdWM3YmMiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzgxNVx1YzIxOFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgTiAqIE0gXHVkNTg5XHViODJjXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljOCBcdWI1NGMsIFx1YjJmOVx1YzJlMFx1Yzc0MCBLXHVhYzFjXHVjNzU4IFx1YWNiOVx1Y2U1OFx1YzljMCBcdWM1NGFcdWIyOTQgXHViZDgwXHViZDg0XHVkNTg5XHViODJjXHVjNzQ0IFx1YWNlOFx1Yjc3Y1x1YzExYywgXHViZDgwXHViZDg0XHVkNTg5XHViODJjIFx1YzU0OFx1YzVkMCBcdWMxOGRcdWQ1NThcdWIyOTQgXHVjNmQwXHVjMThjXHViNGU0XHVjNzU4IFx1ZDU2OVx1Yzc0NCBcdWNkNWNcdWIzMDBcdWQ2NTRcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBOLCBNLCBLXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVkNTg5XHViODJjXHVjNzU4IFx1ZDA2Y1x1YWUzMFx1YzY0MCwgXHVhY2UwXHViOTdjIFx1YmQ4MFx1YmQ4NFx1ZDU4OVx1YjgyY1x1Yzc1OCBcdWMyMThcdWI5N2MgXHViNzNiXHVkNTVjXHViMmU0LiAoMSAmbHQ7PSBLICZsdDs9IDMsIEsgJmx0Oz0gTiwgTSAmbHQ7PSAzMDApPFwvcD5cclxuXHJcbjxwPlx1Yzc3NFx1ZDZjNCBOXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBNXHVhYzFjXHVjNzU4IFx1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQsIGlcdWJjODggXHVkNTg5IGpcdWJjODggXHVjNWY0XHVjNzU4IFx1YzZkMFx1YzE4YyBhPHN1Yj5pajxcL3N1Yj4gKCZtaW51czsyMCAwMDAgJmxlOyBhPHN1Yj5pajxcL3N1Yj4gJmxlOyAyMCAwMDApIFx1Yjk3YyBcdWI3M2JcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmQ4MFx1YmQ4NFx1ZDU4OVx1YjgyY1x1Yzc0MCwgXHVkNTg5XHViODJjIFx1YjBiNFx1Yzc1OCBcdWJkODBcdWJkODQgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1IFx1YWNhOVx1Yzc5MFx1Yjk3YyBcdWI3M2JcdWQ1NWNcdWIyZTQuIFx1YjQ1MCBcdWJkODBcdWJkODRcdWQ1ODlcdWI4MmNcdWM3NzQgXHVhY2I5XHVjZTY4XHVjNzQwLCBcdWFjZjVcdWQxYjUgXHVjNmQwXHVjMThjXHViOTdjIFx1ZDNlY1x1ZDU2OFx1ZDU2OFx1Yzc0NCBcdWI3M2JcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHViZDgwXHViZDg0XHVkNTg5XHViODJjXHVjNWQwIFx1YzE4ZFx1ZDU1OFx1YjI5NCBcdWJhYThcdWI0ZTAgXHVjNmQwXHVjMThjXHViNGU0XHVjNzU4IFx1ZDU2OVx1Yzc1OCBcdWNkNWNcdWIzMTNcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTU4XHViNzdjLjxcL3A+XHJcbiIsImhpbnQiOiI8cCBzdHlsZT1cInRleHQtYWxpZ246Y2VudGVyXCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzMlwvZW1mLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE4MXB4OyB3aWR0aDoyMDdweFwiIFwvPjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNzcyNiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkV2ZW4gbW9yZSBmdW4iLCJkZXNjcmlwdGlvbiI6IjxwPkl0JnJzcXVvO3Mgc28gbmljZSB0byBzbGVlcCB1bmRlciB0aGUgc2t5IGFuZCB0byBiZSB3b2tlbiB1cCBieSBzaW5naW5nIGJpcmRzIGFuZCB0aGUgZmlyc3QgcmF5cyBvZiBzdW4gcmFpc2luZyBmcm9tIHRoZSBob3Jpem9uLiBXYWl0LCB5b3UgZG9uJnJzcXVvO3QgcmVtZW1iZXIgZ29pbmcgdG8gc2xlZXAgaW4gdGhlIG1pZGRsZSBvZiB0aGUgZm9yZXN0LjxcL3A+XHJcblxyXG48cD5XaGF0IHlvdSBkbyByZW1lbWJlciBpcyB0aGF0IHlvdSB3ZXJlIGNvdmVyaW5nIHNvbWV0aGluZyB3aXRoIHRocmVlIHJlY3RhbmdsZXMuIFVuc3VyZSBhYm91dCB3aGF0IGl0IHdhcywgeW91IGRlY2lkZSB0byBzb2x2ZSB0aGUgZm9sbG93aW5nIHByb2JsZW0uPFwvcD5cclxuXHJcbjxwPkZvciBhIGdpdmVuIG1hdHJpeCBvZiBpbnRlZ2VycywgZmluZCBrIG5vbi1vdmVybGFwcGluZyBzdWJtYXRyaWNlcyAoaW4gb3RoZXIgd29yZHMsIHJlY3Rhbmd1bGFyIGZyYWdtZW50cyksIHN1Y2ggdGhhdCB0aGUgc3VtIG9mIG51bWJlcnMgaW4gdGhlbSBpcyBhcyBiaWcgYXMgcG9zc2libGUuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiB0aGUgc3RhbmRhcmQgaW5wdXQgY29udGFpbnMgdGhyZWUgaW50ZWdlcnMgbiwgbSBhbmQgayAoMSAmbGU7IGsgJmxlOyAzLCBrICZsZTsgbiwgbSAmbGU7IDMwMCksIGRlbm90aW5nIHRoZSBoZWlnaHQgYW5kIHdpZHRoIG9mIHRoZSBtYXRyaXggYW5kIHRoZSBudW1iZXIgb2Ygc3VibWF0cmljZXMgcmVzcGVjdGl2ZWx5LiBUaGUgZm9sbG93aW5nIG4gbGluZXMgZGVzY3JpYmUgdGhlIG1hdHJpeCwgcm93IGJ5IHJvdy4gRWFjaCBvZiB0aGVtIGNvbnRhaW5zIGEgc2VxdWVuY2Ugb2YgbSBpbnRlZ2VycyBhPHN1Yj5pajxcL3N1Yj4gKCZtaW51czsyMCAwMDAgJmxlOyBhPHN1Yj5pajxcL3N1Yj4gJmxlOyAyMCAwMDApLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCBvbmUgaW50ZWdlciB0byB0aGUgc3RhbmRhcmQgb3V0cHV0IGVxdWFsIHRvIHRoZSBiaWdnZXN0IHBvc3NpYmxlIHN1bSBvZiBpbnRlZ2VycyBpbiBrIHN1Ym1hdHJpY2VzIG9mIHRoZSBnaXZlbiBtYXRyaXguIFRoZSBzdWJtYXRyaWNlcyBtYXkgdG91Y2gsIGJ1dCB0aGV5IGNhbm5vdCBoYXZlIGFueSBjb21tb24gZWxlbWVudHMuPFwvcD5cclxuIiwiaGludCI6IjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlczJcL2VtZi5wbmdcIiBzdHlsZT1cImhlaWdodDoxODFweDsgd2lkdGg6MjA3cHhcIiBcLz48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

Camp > Czech, Polish and Slovak Preparation Camp > CPSPC 2010 33번

  • 문제를 번역한 사람: koosaga