#P5618. 「一本通 5.6 练习 4」打印文章

「一本通 5.6 练习 4」打印文章

「一本通 5.6 练习 4」打印文章

题目描述

给定 NN 个按顺序排列的单词,第 ii 个单词有非负整数权值 CiC_i。将单词依次划分成若干个非空连续段。一个段 [l,r][l,r] 的费用为

(∑i=lrCi)2+M.\left(\sum_{i=l}^{r} C_i\right)^2+M.

求所有段的最小总费用。若 N=0N=0,总费用为 00。

输入格式

输入包含多组数据,读到文件结束。每组先输入两个整数 N,MN,M(0≤N≤5×1050\le N\le5\times10^5,0≤M≤10000\le M\le1000),然后输入 NN 个用空白分隔的整数 C1,C2,…,CNC_1,C_2,\ldots,C_N。

输出格式

每组数据输出一行一个整数,表示最小总费用。

样例 1

5 5
5 9 5 7 5
230