AT_awc0005_d.配達ルートの分割

高桥负责一家运输公司的配送计划。

今天，他需要使用 $K$ 辆卡车运送 $N$ 个包裹。

每个包裹按 $1$ 到 $N$ 编号，第 $i$ 个包裹的重量为 $A_i$。

为提高配送效率，他决定将包裹按照 $1,2,\ldots,N$ 的顺序排列，并将它们划分为 $K$ 个连续的分段，每个分段至少包含 $1$ 个包裹，并将每个分段的包裹分配给一辆卡车。每个包裹恰好属于一个分段，$K$ 个分段与 $K$ 辆卡车一一对应。

对于每辆卡车，分配给它的所有包裹的重量之和称为该卡车的载重。

高桥希望最大化 $K$ 辆卡车中最小载重的值。

请你考虑所有可能的包裹划分方式，求出“$K$ 辆卡车中最小载重的最大可能值”。

$N$ $K$
$A_1$ $A_2$ $\ldots$ $A_N$

• 第一行包含两个整数 $N$ 和 $K$，用空格分隔，表示包裹数量和卡车数量。
• 第二行包含 $N$ 个整数 $A_1, A_2, \ldots, A_N$，用空格分隔，表示每个包裹的重量。

一行输出当包裹被最优划分时，$K$ 辆卡车中最小载重的最大可能值。

数据范围

• $1 \leq K \leq N \leq 10^5$
• $1 \leq A_i \leq 10^9$
• 所有输入均为整数。

由 ChatGPT 5 翻译