시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 40 17 12 37.500%

문제

티떱랜드에서 가장 유명한 놀이기구의 앞에 총 N명이 한 줄로 서 있다. 1번째 사람은 줄의 가장 앞에 있는 사람이고, N번째 사람은 가장 뒤에 있는 사람이다.

이 놀이기구에는 총 K개의 열차가 있으며, 다음과 같이 사람들을 태워야 한다.

  • 첫 번째 열차에 줄의 앞에서부터 q1명을 태워야 한다.
  • 두 번째 열차에 첫 번째 열차를 타고 줄의 앞에서부터 q2명을 태워야 한다.
  • ...
  • K번째 열차에 남은 qK명을 태워야 한다.

q1, q2, ..., qK는 항상 양수이며, Σqi = n 이다.

티떱랜드의 사장 민혁이는 사람들이 모르는 사람과 놀이기구를 타는 일을 좋아하지 않는다는 것을 알고 있다. 오늘 민혁이는 사람들을 행복하게 만들기 위해서 최적의 q1, q2, ..., qK값을 찾으려고 한다.

모든 i번 사람과 j번 사람 사이에는 어색한 정도 uij가 정의되어 있다. uij = uji이며, 모든 1 ≤ i ≤ N에 대해서, uii = 0이다.

열차의 어색함은 놀이기구에 타 있는 모든 사람들의 쌍의 어색한 정도의 합이다.

열차의 어색함의 합을 최소로하는 q1, q2, ..., qK를 찾는 프로그램을 작성하시오.

입력

첫째 줄에 사람의 수 N과 열차의 수 K가 주어진다. (1 ≤ N ≤ 4000, 1 ≤ K ≤ min(N, 800))이 주어진다.

둘째 줄부터 N개의 줄에는 N개의 정수가 주어지며, 이것은 행렬 u (0 ≤ uij ≤ 9, uij = uji, uii = 0)을 나타낸다.

출력

열차의 어색함의 합을 최솟값을 출력한다.

예제 입력 1

5 2
0 0 1 1 1
0 0 1 1 1
1 1 0 0 0
1 1 0 0 0
1 1 0 0 0

예제 출력 1

0

예제 입력 2

8 3
0 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1
1 1 0 1 1 1 1 1
1 1 1 0 1 1 1 1
1 1 1 1 0 1 1 1
1 1 1 1 1 0 1 1
1 1 1 1 1 1 0 1
1 1 1 1 1 1 1 0

예제 출력 2

7

예제 입력 3

3 2
0 2 0
2 0 3
0 3 0

예제 출력 3

2

힌트

첫 번째 예제의 경우에는 (1, 2), (3, 4, 5)로 타고, 두 번째 예제의 경우에는 (1, 2, 3), (4, 5, 6), (7, 8)로 타면 최소다.

출처