시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgTiwgTSwgS1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1ZDU4OVx1YjgyY1x1Yzc1OCBcdWQwNmNcdWFlMzBcdWM2NDAsIFx1YWNlMFx1Yjk3YyBcdWJkODBcdWJkODRcdWQ1ODlcdWI4MmNcdWM3NTggXHVjMjE4XHViOTdjIFx1YjczYlx1ZDU1Y1x1YjJlNC4gKDEgJmx0Oz0gSyAmbHQ7PSAzLCBLICZsdDs9IE4sIE0gJmx0Oz0gMzAwKTxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWQ2YzQgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgTVx1YWMxY1x1Yzc1OCBcdWMyMThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LCBpXHViYzg4IFx1ZDU4OSBqXHViYzg4IFx1YzVmNFx1Yzc1OCBcdWM2ZDBcdWMxOGMgYTxzdWI+aWo8XC9zdWI+ICgmbWludXM7MjAgMDAwICZsZTsgYTxzdWI+aWo8XC9zdWI+ICZsZTsgMjAgMDAwKSBcdWI5N2MgXHViNzNiXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJkODBcdWJkODRcdWQ1ODlcdWI4MmNcdWM3NDAsIFx1ZDU4OVx1YjgyYyBcdWIwYjRcdWM3NTggXHViZDgwXHViZDg0IFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNSBcdWFjYTlcdWM3OTBcdWI5N2MgXHViNzNiXHVkNTVjXHViMmU0LiBcdWI0NTAgXHViZDgwXHViZDg0XHVkNTg5XHViODJjXHVjNzc0IFx1YWNiOVx1Y2U2OFx1Yzc0MCwgXHVhY2Y1XHVkMWI1IFx1YzZkMFx1YzE4Y1x1Yjk3YyBcdWQzZWNcdWQ1NjhcdWQ1NjhcdWM3NDQgXHViNzNiXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YmQ4MFx1YmQ4NFx1ZDU4OVx1YjgyY1x1YzVkMCBcdWMxOGRcdWQ1NThcdWIyOTQgXHViYWE4XHViNGUwIFx1YzZkMFx1YzE4Y1x1YjRlNFx1Yzc1OCBcdWQ1NjlcdWM3NTggXHVjZDVjXHViMzEzXHVhYzEyXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1Yjc3Yy48XC9wPlxyXG4iLCJoaW50IjoiPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlclwiPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlczJcL2VtZi5wbmdcIiBzdHlsZT1cImhlaWdodDoxODFweDsgd2lkdGg6MjA3cHhcIiBcLz48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6Ijc3MjYiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJFdmVuIG1vcmUgZnVuIiwiZGVzY3JpcHRpb24iOiI8cD5JdCZyc3F1bztzIHNvIG5pY2UgdG8gc2xlZXAgdW5kZXIgdGhlIHNreSBhbmQgdG8gYmUgd29rZW4gdXAgYnkgc2luZ2luZyBiaXJkcyBhbmQgdGhlIGZpcnN0IHJheXMgb2Ygc3VuIHJhaXNpbmcgZnJvbSB0aGUgaG9yaXpvbi4gV2FpdCwgeW91IGRvbiZyc3F1bzt0IHJlbWVtYmVyIGdvaW5nIHRvIHNsZWVwIGluIHRoZSBtaWRkbGUgb2YgdGhlIGZvcmVzdC48XC9wPlxyXG5cclxuPHA+V2hhdCB5b3UgZG8gcmVtZW1iZXIgaXMgdGhhdCB5b3Ugd2VyZSBjb3ZlcmluZyBzb21ldGhpbmcgd2l0aCB0aHJlZSByZWN0YW5nbGVzLiBVbnN1cmUgYWJvdXQgd2hhdCBpdCB3YXMsIHlvdSBkZWNpZGUgdG8gc29sdmUgdGhlIGZvbGxvd2luZyBwcm9ibGVtLjxcL3A+XHJcblxyXG48cD5Gb3IgYSBnaXZlbiBtYXRyaXggb2YgaW50ZWdlcnMsIGZpbmQgayBub24tb3ZlcmxhcHBpbmcgc3VibWF0cmljZXMgKGluIG90aGVyIHdvcmRzLCByZWN0YW5ndWxhciBmcmFnbWVudHMpLCBzdWNoIHRoYXQgdGhlIHN1bSBvZiBudW1iZXJzIGluIHRoZW0gaXMgYXMgYmlnIGFzIHBvc3NpYmxlLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgdGhlIHN0YW5kYXJkIGlucHV0IGNvbnRhaW5zIHRocmVlIGludGVnZXJzIG4sIG0gYW5kIGsgKDEgJmxlOyBrICZsZTsgMywgayAmbGU7IG4sIG0gJmxlOyAzMDApLCBkZW5vdGluZyB0aGUgaGVpZ2h0IGFuZCB3aWR0aCBvZiB0aGUgbWF0cml4IGFuZCB0aGUgbnVtYmVyIG9mIHN1Ym1hdHJpY2VzIHJlc3BlY3RpdmVseS4gVGhlIGZvbGxvd2luZyBuIGxpbmVzIGRlc2NyaWJlIHRoZSBtYXRyaXgsIHJvdyBieSByb3cuIEVhY2ggb2YgdGhlbSBjb250YWlucyBhIHNlcXVlbmNlIG9mIG0gaW50ZWdlcnMgYTxzdWI+aWo8XC9zdWI+ICgmbWludXM7MjAgMDAwICZsZTsgYTxzdWI+aWo8XC9zdWI+ICZsZTsgMjAgMDAwKS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgb25lIGludGVnZXIgdG8gdGhlIHN0YW5kYXJkIG91dHB1dCBlcXVhbCB0byB0aGUgYmlnZ2VzdCBwb3NzaWJsZSBzdW0gb2YgaW50ZWdlcnMgaW4gayBzdWJtYXRyaWNlcyBvZiB0aGUgZ2l2ZW4gbWF0cml4LiBUaGUgc3VibWF0cmljZXMgbWF5IHRvdWNoLCBidXQgdGhleSBjYW5ub3QgaGF2ZSBhbnkgY29tbW9uIGVsZW1lbnRzLjxcL3A+XHJcbiIsImhpbnQiOiI8cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXMyXC9lbWYucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTgxcHg7IHdpZHRoOjIwN3B4XCIgXC8+PFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

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

  • 문제를 번역한 사람: koosaga