T4 数列分段（segment）

题目描述

给定一个长度为 $n$ 的正整数序列 $a_1,a_2,\dots,a_n$。你需要把它恰好分成 $k$ 个连续的、非空的段。对于一个段 $[l,r]$，定义它的代价为这一段内所有元素之和的平方，即 $\big(\sum_{i=l}^r a_i\big)^2$。

请你合理地选择这 $k-1$ 个分界点，使得所有段的代价之和最小，输出这个最小值。

输入文件 segment.in，输出文件 segment.out。

输入格式

输入第一行两个整数 $n,k$，表示序列长度与要分成的段数。

第二行 $n$ 个整数 $a_i$，表示这个序列。

输出格式

输出一行一个整数，表示最小总代价。

样例 1 输入

5 2
1 100 1 100 1

样例 1 输出

20605

样例 1 解释

在第 $2$ 个数后切分，两段为 $[1,100]$ 与 $[1,100,1]$，代价为 $101^2+102^2=10201+10404=20605$，是所有切法中最小的。

样例 2 输入

4 2
3 1 2 4

样例 2 输出

52

数据规模与约定

• 对于 $30\%$ 的数据，保证 $n \le 10,k \le 3$。
• 对于 $100\%$ 的数据，保证 $1 \le k \le \min(n,100)$，$n \le 500$，$1 \le a_i \le 1000$。