配点: 100 点
問題文
IOI 铁路是 1 经营一条铁路线。排列在IOI铁道线上 有 N 个站,按顺序 它们的编号最大为 1 从 N 。每个 i (1 \leqq i \leqq N - 1),车站 i 和车站 i + 1 由一条铁路线连接,其长度为 1 。
IOI 铁路处理货运。车站 2, 3, \ldots, N 有货 每个站都放置 1 。 位于 i (2 \leqq i \leqq N) 的货物价值为 A_i 。
IOI铁路运营货运列车 1 我拥有该组织。这列火车是第一站 1 并且可以在IOI铁路线上双向运行。在每个车站,您可以将储存在该车站的货物装载到火车上,或者将装载到火车上的货物卸下并留在该车站。
使用该货运列车的车站 2, 3, \ldots, N 我想把它运送到 1 。不过,这列火车不运载货物。 您只能发布 W 或更少。也就是说,任何时候列车上都没有货物。 不允许列出超过 W + 1 。此外,由于燃料限制,该列车的最大总里程为 D 只能运行。因此,所有货物都被送往车站。 可能无法将其传送到 1 。
IOI铁路社长JOI君希望,在这种情况下,通过适当地运行货运列车,他最终能够到达车站。 我想尽可能增加放置在 1 的货物的总价值。
当给出货运列车信息和各站存储的货物信息时,最终 编写一个程序来查找 1 中存储的货物值的最大可实现总和。
制約
- 2 \leqq N \leqq 450.
- 1 \leqq W \leqq N - 1.
- 2 \leqq D \leqq N^2 - N.
- 1 \leqq A_i \leqq 1\,000\,000 (2 \leqq i \leqq N).
- 所有输入值都是整数。
小課題
- (6 点) W = 1,A_i = 1 (2 \leqq i \leqq N).
- (9 点) A_i = 1 (2 \leqq i \leqq N).
- (24 点) W = 1.
- (13 点) N \leqq 15.
- (24 点) N \leqq 50.
- (24 点)没有额外的限制。
入力
输入按以下格式给出。
N W D A_2 A_3 \cdots A_N
出力
终于站了 1 可实现的最大价值作为放置的货物价值的总和 1 行。
入力例 1
4 1 10 1 1 1
出力例 1
2
例如,如果您运行如下所示的货运列车,它最终会到达车站。 货物总价值位于 1 它可以是 2 。
首先,货运列车 我在 1 。
- 货运列车在车站 运行 2 。 置于
- 駅 2 上的值 将 1 货物装载到货运列车上。
- 货运列车在车站 运行 1 。 置于
- 货运列车装载的价值 1 货运到站 将其放入 1 。
- 货运列车在车站 运行 4 。 置于
- 駅 4 上的值 将 1 货物装载到货运列车上。
- 货运列车在车站 运行 1 。 置于
- 货运列车装载的价值 1 货运到站 将其放入 1 。
火车行驶的总距离为 8 火车的总距离是 10 满足车辆只能在以下行驶的条件。
这时,终于站了 位于 1 的货物总价值为 2 。终于到站了 由于它不能大于 1 它可以是 3 ,2 。
此输入示例满足所有子任务约束。
入力例 2
7 3 16 1 1 1 1 1 1
出力例 2
5
例如,如果您运行如下所示的货运列车,它最终会到达车站。 货物总价值位于 1 它可以是 5 。
首先,货运列车 我在 1 。
- 货运列车在车站 运行 5 。 置于
- 駅 5 上的值 将 1 货物装载到货运列车上。
- 货运列车在车站 运行 6 。 置于
- 駅 6 上的值 将 1 货物装载到货运列车上。
- 货运列车在车站 运行 1 。 置于
- 装载在货运列车上 2 值 所有 1 货物到站 1 。
- 货运列车在车站 运行 2 。 置于
- 駅 2 上的值 将 1 货物装载到货运列车上。
- 货运列车在车站 运行 3 。 置于
- 駅 3 上的值 将 1 货物装载到货运列车上。
- 货运列车在车站 运行 4 。 置于
- 駅 4 上的值 将 1 货物装载到货运列车上。
- 货运列车在车站 运行 1 。 置于
- 装载在货运列车上 3 值 所有 1 货物到站 1 。
火车行驶的总距离为 16 火车的总距离是 16 满足车辆只能在以下行驶的条件。
这时,终于站了 位于 1 的货物总价值为 5 。终于到站了 由于它不能大于 1 它可以是 6 ,5 。
此输入示例是一个小作业。 2, 4, 5, 6 满足约束。 在
入力例 3
5 2 12 40 30 20 10
出力例 3
100
例如,如果您运行如下所示的货运列车,它最终会到达车站。 货物总价值位于 1 它可以是 100 。
首先,货运列车 我在 1 。
- 货运列车在车站 运行 5 。 置于
- 駅 5 上的值 将 10 货物装载到货运列车上。
- 货运列车在车站 运行 4 上运行。
- 駅 4 上的值 将 20 货物装载到货运列车上。
- 货运列车在车站 运行 2 。 置于
- 货运列车装载的价值 10 运费和价值 20 货运到站 将其放入 2 。
- 駅 2 上的值 将 40 货物装载到货运列车上。
- 货运列车在车站 运行 3 。 置于
- 駅 3 上的值 将 30 货物装载到货运列车上。
- 货运列车在车站 运行 1 。 置于
- 货运列车装载的价值 30 运费和价值 40 货运到站 将其放入 1 。
- 货运列车在车站 运行 2 。 置于
- 駅 2 上的值 将 10 运费和价值 20 货物装载到货运列车上。
- 货运列车在车站 运行 1 。 置于
- 货运列车装载的价值 10 运费和价值 20 货运到站 将其放入 1 。
火车行驶的总距离为 12 火车的总距离是 12 满足车辆只能在以下行驶的条件。
这时,终于站了 位于 1 的货物总价值为 100 。终于到站了 由于它不能大于 1 它可以是 101 ,100 。
此输入示例是一个小作业。 4, 5, 6 满足约束。 在
入力例 4
5 1 11 2 7 1 8
出力例 4
10
此输入示例是一个小作业。 3, 4, 5, 6 满足约束。 在
入力例 5
9 3 14 54640 754112 604290 105866 591907 801383 502975 379373
出力例 5
2214425
此输入示例是一个小作业。 4, 5, 6 满足约束。 在