08763. 灯光秀高度调度 · 林老师的题库

题目描述

无人机社团要表演一场灯光秀。表演开始时，无人机悬停在高度 $h$ （整数，单位米）。场地规定：无人机的高度必须始终保持在 $0 \sim H$ 米之间（可以取到 $0$ 或 $H$ ），一旦低于 $0$ 米或高于 $H$ 米，系统会立即强制降落，表演就失败了。

整场表演共有 $n$ 个节目。在第 $i$ 个节目开始前，无人机必须把高度恰好调整 $c_{i}$ 米：可以选择升高 $c_{i}$ 米，也可以选择降低 $c_{i}$ 米，调整瞬间完成，但调整后的高度必须仍然合法。

社团希望最后一个节目开始时无人机的高度尽可能高。你的任务是：求依次完成全部 $n$ 次调整后，最后一个节目开始时能达到的最大高度；如果无论怎样选择升降，都会在某次调整后越界，输出 -1。

第一行三个整数 $n, h, H$ ，分别表示节目数、起始高度与高度上限。

第二行 $n$ 个整数 $c_{1}, c_{2}, \dots, c_{n}$ ，用空格分隔，表示每个节目开始前必须调整的高度变化量。

一行一个整数：能达到的最大高度；若无法避免越界则输出 -1。

输入

4 2 9
3 5 2 4

输出

样例解释：唯一合法的调整路线是 $2 + 3 5 - 5 0 + 2 2 + 4 6$ 。第一步降 $3$ 米会到 $- 1$ 米，第二步升 $5$ 米会到 $10$ 米，都越界，所以路线是被迫的，最后一个节目开始时的高度为 $6$ 。

样例解释：第一次调整 $2 + 3 = 5 > 4$ ， $2 - 3 = - 1 < 0$ ，两种选择都越界，无合法方案。

对于 $100%$ 的数据： $1 \leq n \leq 50$ ， $1 \leq H \leq 1000$ ， $0 \leq h \leq H$ ， $1 \leq c_{i} \leq H$ 。

本题共 $10$ 个测试点，每个测试点 $10$ 分。