긴 생산 라인에 \(N\) 개의 작업 모듈이 일렬로 놓여 있고, \(i\) 번째 모듈에는 음이 아닌 정수 처리량 \(A_i \ge 0\) 이 적혀 있다.

이 라인을 정확히 \(K\) 개의 연속된 구획으로 나누려고 한다. 즉 각 구획은 라인에서 서로 겹치지 않는 연속 구간이고, 모든 모듈이 정확히 하나의 구획에 속하며, 빈 구획은 없어야 한다.

하나의 구획에 속한 모듈들의 처리량 합을 \(S\) 라고 할 때 그 구획의 비용은 \(S^2\) 으로 정의된다. 라인 전체의 총비용은 \(K\) 개 구획 비용의 합이다.

총비용을 최소로 만드는 분할의 총비용을 구하여라.

예를 들어 \(A = [1, 2, 3, 4]\) 를 \(K = 2\) 개로 나눈다면, \(\{1,2,3\}\,|\,\{4\}\) 로 자를 때 \(6^2 + 4^2 = 52\) 로 최소가 된다.

\(1 \le K \le N \le 100{,}000\)

\(0 \le A_i \le 10^6\)

각 구획의 비용은 구획 내 처리량 합의 제곱이며, 총비용은 모든 구획 비용의 합이다. 정답은 64비트 정수 범위 안에 들어간다.

첫째 줄에 두 정수 \(N\) 과 \(K\) 가 공백으로 구분되어 주어진다 (\(1 \le K \le N \le 100{,}000\)).

둘째 줄에 \(N\) 개의 정수 \(A_1, A_2, \dots, A_N\) 이 공백으로 구분되어 주어진다 (\(0 \le A_i \le 10^6\)).

정확히 \(K\) 개의 연속 구획으로 나눌 때 가능한 최소 총비용을 한 줄에 출력한다.

riseoj 작성

출처 Original