Given an array of $n$ elements, your task is to divide into $k$ subarrays. The cost of each subarray is the square of the sum of the values in the subarray. What is the minimum total cost if you act optimally?
The first input line has two integers $n$ and $k$ : the array elements and the number of subarrays. The array elements are numbered $1,2,\dots,n$ .
The second line has $n$ integers $x_1,x_2,\dots,x_n$ : the contents of the array.
Print one integer: the minimum total cost.
8 3 2 3 1 2 2 3 4 1· \n · · · · · · · \n
110\n
An optimal solution is $[2,3,1]$ , $[2,2,3]$ , $[4,1]$ , whose cost is $(2+3+1)^2+(2+2+3)^2+(4+1)^2=110$ .