UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#4862. [BeiJing 2017 Wc]太空飞船

Statistics 下载数据

Description

21XX年,秋。
小诚是THU(TomorrowHappyUniversity)航天学院船舶设计系本科四年级的学生。为了顺利毕业,小诚仔细阅读了
这几年被引用次数最多的十几篇会议论文,打算在权威理论的指导下设计一艘新型太空飞船。这将是一艘环形的太
空飞船,由N个舱室顺序组成。第i个舱室的设计长度为Li。为了给飞船提供能量,要在飞船上装置K个太空能量吸
收器。根据权威理论,这些吸收器应该尽量均匀地分散在飞船表面。也就是说,小诚要把飞船所有N个舱室划分成K
个部分(每个部分包括连续一段舱室),并给每个部分配置一个能量吸收器。设第i个部分舱室的长度之和为si,
则要令方差
尽量小。其中s_avg是K个部分的平均长度。可是,这个问题对于已经大学四年级的小诚来说太难了。你能否帮助他
完成设计呢?为方便起见,输出方差最小值与K的平方的乘积。

Input

第一行,两个整数N,K。
第二行,N个整数L1,L2,…,LN,由空格隔开。依次表示每个舱室的长度。

Output

输出一行,为一个整数,表示方差最小值与K^2的乘积。

Sample Input

5 3
4 2 6 1 3

Sample Output

24

Hint

N<=400,K<=20,1 ≤ Li ≤ 1,000

Source