题目内容

在大模型训练中，常使用流水线并行（Pipeline Parallelism）将模型的不同层划分到多个计算节点上执行。为避免某个节点负载过高导致系统整体变慢，需要合理划分模型层。

假设一个模型共有 $L$ 层，第 $i$ 层的计算量为 $w_i$（$0 \le i \le L-1$）。现需将这些层划分到 $k$ 个计算节点上，使得整个系统的峰值负载最小。

划分规则

• 每一层必须恰好分配给一个计算节点；
• 每个计算节点负责一段连续的层，且至少分配 $1$ 层；
• 模型层按 $0 \rightarrow 1 \rightarrow \cdots \rightarrow L-1$ 的顺序执行，划分不得打乱层序。

负载定义

设某计算节点分到连续层 $w_l, w_{l+1}, \ldots, w_r$，则该节点段负载为

系统峰值负载为所有节点段负载的最大值：

目标

求一种合法划分，使 $peak$ 最小，并输出该最小值。

输入描述

第一行：整型 $L$，表示模型层数。

第二行：$L$ 个整型 $w_0, w_1, \ldots, w_{L-1}$，表示各层计算量。

第三行：整型 $k$，表示计算节点数量。

数据范围：

• $1 \le L \le 128$；
• $1 \le k \le L$；
• $1 \le w_i \le 1000$。

输出描述

输出一个整型，表示最小的系统峰值负载 $peak$。

样例1

输入

5
3 1 4 1 5
2

输出

8

说明

模型共 $L=5$ 层，需划到 $k=2$ 个节点。最优划分为 $[3,1,4]$ 与 $[1,5]$，两段负载分别为 $8$ 与 $6$，峰值为 $8$。

样例2

输入

4
10 20 30 40
2

输出

60

说明

最优划分为 $[10,20,30]$ 与 $[40]$，两段负载分别为 $60$ 与 $40$，峰值为 $60$。