#P2862. 分糖果

    ID: 1974 传统题 1000ms 512MiB 尝试: 123 已通过: 43 难度: 8 上传者: 标签>CF2400提高+/省选-二分答案一维前缀和线性 DP离散化树状数组

分糖果

题目描述

小 W 有 nn 颗糖果,去助学的时候,小 W 希望将这 nn 颗糖果分给所在的 kk 个小朋友。

小 W 是个很怪的人,他觉得,每个小朋友应该分得编号连续的一段糖果,而且每个小朋友至少应该得到一颗糖果。

小 W 给每颗糖果一个值 viv_i 用来表示它的美味度(可以为负数)。作为一个绝对公平的追求者,他当然希望将所有糖果公平的分给所有小朋友,所以他希望所有小朋友各自分到的那一段糖果的美味度总和中的最大值尽量小。

小 W 定制了这样一套奇怪的规则,他却不知道该如何分糖果了,这个艰巨的任务就交给了你。

输入格式

第一行两个整数 n,kn,k。

接下来一行 nn 个整数表示 v1⋯nv_{1\cdots n}。

输出格式

输出一个整数,表示在恰好分成 kk 个非空连续段的所有方案中,最大段和的最小值。

3 2
-1 -1 -2
-2

数据规模与约定

对于 100%100\% 的数据,1≤k≤n≤2×1041\leq k\leq n\leq 2\times 10^4。

本站全部评测数据中,每颗糖果的美味度为整数,满足 −32768≤vi≤32767-32768\le v_i\le32767。