Code:

#include <cstdio>
#include <cstring>
using namespace std ;
typedef long long ll ;
const int MAXN = 3e3 + 10 ;
int n , m , q[MAXN] , head , tail ; 
ll f[MAXN][MAXN] , sum[MAXN] , a[MAXN] ;
double slope (int j1 , int j2 , int now) {
	return (f[j2][now] + sum[j2] * sum[j2] - f[j1][now] - sum[j1] * sum[j1]) * 1.0 / (sum[j2] - sum[j1]) ;
}
int main () {
	scanf ("%d %d" , &n , &m) ;
	for (int i = 1 ; i <= n ; i++)
		scanf ("%lld" , &a[i]) , sum[i] = sum[i - 1] + a[i] ;
	memset (f , 0x3f , sizeof (f)) ;
	for (int i = 1 ; i <= n ; i++) f[i][1] = sum[i] * sum[i] ;
	for (int k = 2 ; k <= m ; k++) {
		head = 1 ; tail = 1 ;
		q[1] = k ;
		for (int i = k + 1 ; i <= n ; i++) {
			while (head < tail && slope (q[head] , q[head + 1] , k - 1) < 2 * sum[i]) head++ ;
			int j = q[head] ;
			f[i][k] = f[j][k - 1] + (sum[i] - sum[j]) * (sum[i] - sum[j]) ;
			while (head < tail && slope (q[tail - 1] , q[tail] , k - 1) >= slope (q[tail] , i , k - 1)) tail-- ;
			q[++tail] = i ;
		}
	}
	printf ("%lld" , 1LL * f[n][m] * m - 1LL * sum[n] * sum[n]) ;
	return 0 ;
}