시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 32 MB 1 1 1 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) 를 뜻한다.

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

출력

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

예제 입력

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

예제 출력

17

힌트

출처

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

  • 문제를 번역한 사람: koosaga