Помогите решить задачку.

Есть массив чисел. Надо разбить его на n отрезков, так чтобы минимизировать суммарный риск для всех отрезков. Риск для одного отрезка это произведение длины отрезка на сумму чисел на нем.

Ограничения: Длина массива < 8000

n < 800

Числа в массиве < 1e9

Ссылка на задачу https://www.hackerrank.com/contests/ioi-2014-practice-contest-2/challenges/guardians-lunatics-ioi14