#P8198. [传智杯 #4 决赛] 背单词的小智

[传智杯 #4 决赛] 背单词的小智

题目背景

小智在刚刚结束的 CET-4 考试中顺利通过了!现在,他要开始备战 CET-6 了。

可是,他的单词功底太差了,于是他准备开始摆烂背单词。

可是,人脑的能力是有限的,小智的大脑每一天都会有一个记忆的上限,如果超过这个上限,再多的单词也记不下了。

有一天,小智在背单词的时候想到了一个问题,你能帮帮他吗?

题目描述

小智一共有 nn 个单词需要背,第 ii 个单词所拥有的「精神值」为 aia_i

小智每天的记忆力都是有上限 mm 的。如果小智在第 ii 天内背完了 [l,r][l,r] 内的单词,那么这些单词将会占用小智 Ci=j=lraj2C_i = \sum\limits_{j=l} ^ r a_j^2 的记忆力。

小智需要在最多 kk 天里把这些单词全部背完,他希望你在把这些单词背完的同时,让他每天需要的记忆力的最大值尽可能小。

也就是说,你需要将一个序列最多分为 kk 段,请你找到一个最小的 mm,使得 1ik\forall 1 \leq i \leq kCi=j=lraj2mC_i= \sum\limits_{j=l} ^ r a_j^2 \leq m,其中 llrr 为各段的左、右端点。

输入格式

第一行有两个整数 n,kn, k,表示小智需要背的单词数量和小智需要背完单词的天数。

第二行有 nn 个整数 aia_i,第 ii 个整数表示第 ii 个单词的「精神值」。

输出格式

共一行。

输出一个整数 mm,表示小智所需的最小记忆力。

5 1
1 2 3 4 5
55
4 2
1 2 3 4
16

提示

样例 1 解释

由于小智最多要在 1 天内背完单词,所以必须将这些单词一次性背完,代价为 5555

样例 2 解释

可以发现,当小智第 1 天背 [1,3][1,3] 的单词,第 2 天背 [4,4][4,4] 的单词时需要的记忆力最少,为 42=164^2 = 16

数据规模与约定

对于所有测试点,保证 1n1×1051 \leq n \leq 1 \times 10^51kn1 \leq k \leq n1ai1×1061\leq a_i \leq 1\times 10^6