链接: https://cses.fi/problemset/task/2086

板块: Advanced Techniques

时限: 1.00 s ｜ 内存: 512 MB

题目描述

给定一个包含 $n$ 个元素的数组，你需要将其划分为 $k$ 个子数组。每个子数组的代价是该子数组内元素之和的平方。在最优化的情况下，最小的总代价是多少？

输入

第一行有两个整数 $n$ 和 $k$：数组元素个数与子数组个数。数组元素编号为 $1,2,\dots,n$。

第二行有 $n$ 个整数 $x_1,x_2,\dots,x_n$：数组的内容。

输出

输出一个整数：最小总代价。

数据范围

$1 \le k \le n \le 3000$ $1 \le x_i \le 10^5$

样例输入

8 3
2 3 1 2 2 3 4 1

样例输出

110