← 返回题目列表

AtCoder · awc0005_d

D. 拆分交付包裹

中文机器翻译题面 查看原题

分数: 400 分

问题陈述

Takahashi 在一家运输公司负责交货计划。

今天,他需要制定一个计划来交付 N 包使用 K 卡车。

每个包裹的编号为 1 to N,以及包裹的重量 i is A_i.

为了提高配送效率,他决定对包裹进行整理 1, 2, \ldots, N 按此顺序并将它们分为 K 连续段,每个段至少包含 1 包裹,并将每个分段中的包裹分配给一辆卡车。每个包都属于一个段,并且段之间存在一一对应的关系 K 段和 K 卡车。

对于每辆卡车,分配给该卡车的包裹重量总和称为 负载 那辆卡车的 。

高桥希望最大化最小负载 K 卡车。

考虑所有可能的划分包裹的方式,找到“最小负载”的最大可能值 K 卡车。”

约束

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

输入

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

输出

在一行中打印最小负载的最大可能值 K 包裹被最佳分割时的卡车。


示例输入 1

5 2
1 2 3 4 5

示例输出 1

6

示例输入 2

7 3
3 1 4 1 5 9 2

示例输出 2

6

示例输入 3

10 4
100 200 150 300 50 250 400 100 350 200

示例输出 3

450