물류 담당 세훈이는 컨베이어 벨트 위에 일렬로 놓인 \(N\) 개의 상자를 처리한다. \(i\) 번째 상자의 무게는 \(a_i\) 이며, 무게는 음수일 수도 있다(예: 무게가 측정 기준보다 가벼운 빈 상자는 음수로 기록된다).

상자들을 연속한 구간 단위로 잘라 여러 묶음으로 나눈다. 각 묶음은 비어 있지 않은 연속 구간이어야 하고, 모든 상자는 정확히 하나의 묶음에 속한다.

한 묶음의 처리 비용은 그 묶음에 속한 상자 무게 합의 제곱이다. 전체 비용은 모든 묶음의 비용을 더한 값이다. 무게가 음수인 상자와 양수인 상자를 한 묶음으로 묶으면 합이 작아져 비용이 줄어들 수 있다. 묶음을 적절히 나누어 전체 비용의 최솟값을 구하여라.

• \(1 \le N \le 2{,}000\)
• \(-1{,}000 \le a_i \le 1{,}000\)

첫 줄에 상자의 개수 \(N\) 이 주어진다.

둘째 줄에 \(N\) 개의 정수 \(a_1, a_2, \dots, a_N\) 이 공백으로 구분되어 주어진다.

전체 처리 비용의 최솟값을 한 줄에 출력한다.

riseoj 작성

출처 Original