P13507 [OOI 2024] Three Arrays

你有三个长度为 $n$ 的数组 $D$、$L$ 和 $R$，下标从 $1$ 开始。同时给定整数 $a_{0}$ 和 $b_{0}$。你需要按如下规则构造两个长度为 $n+1$ 的数组 $A$ 和 $B$： - $A_{0} = a_{0}$，$B_{0} = b_{0}$ - 对于所有 $1 \leq i \leq n$，依次进行以下操作： - 令 $A_{i} = A_{i-1} + D_{i}$，$B_{i} = B_{i-1} + D_{i}$。 - 然后**恰好选择以下两种操作中的一种**并应用： - $A_{i} = \min(A_{i}, L_{i})$ - $B_{i} = \min(B_{i}, R_{i})$ 你希望通过上述操作，构造出 $A$ 和 $B$，使 $A_{n} + B_{n}$ 的值最大。请你求出能够得到的 $A_{n} + B_{n}$ 的最大值。

第一行包含一个整数 $n$（$1 \leq n \leq 100\,000$），表示数组 $D$、$L$ 和 $R$ 的长度。 第二行包含 $n$ 个整数 $D_{1}, D_{2}, \ldots, D_{n}$（$0 \leq D_{i} \leq 10^{9}$），表示数组 $D$。 第三行包含 $n$ 个整数 $L_{1}, L_{2}, \ldots, L_{n}$（$0 \leq L_{i} \leq 10^{9}$），表示数组 $L$。 第四行包含 $n$ 个整数 $R_{1}, R_{2}, \ldots, R_{n}$（$0 \leq R_{i} \leq 10^{9}$），表示数组 $R$。 第五行包含两个整数 $a_{0}$ 和 $b_{0}$（$0 \leq a_{0}, b_{0} \leq 10^{9}$）。

输出一个整数，表示所有可能方案中 $A_{n} + B_{n}$ 的最大值。

### 说明 在第一个输入样例中，以下操作顺序可以得到最大答案： - $A_{0} = 4$，$B_{0} = 8$。 - $A_{1} = A_{0} + D_{1} = 4 + 4 = 8$，$B_{1} = B_{0} + D_{1} = 8 + 4 = 12$。 - 对 $A_{1}$ 应用 $\min$，$A_{1} = \min(8, 10) = 8$，$B_{1} = 12$ 不变。 - $A_{2} = A_{1} + D_{2} = 8 + 0 = 8$，$B_{2} = B_{1} + D_{2} = 12 + 0 = 12$。 - 对 $A_{2}$ 应用 $\min$，$A_{2} = \min(8, 5) = 5$，$B_{2} = 12$ 不变。 - $A_{3} = A_{2} + D_{3} = 5 + 7 = 12$，$B_{3} = B_{2} + D_{3} = 12 + 7 = 19$。 - 对 $A_{3}$ 应用 $\min$，$A_{3} = \min(12, 3) = 3$，$B_{3} = 19$ 不变。 - $A_{4} = A_{3} + D_{4} = 3 + 0 = 3$，$B_{4} = B_{3} + D_{4} = 19 + 0 = 19$。 - 对 $A_{4}$ 应用 $\min$，$A_{4} = \min(3, 7) = 3$，$B_{4} = 19$ 不变。 - $A_{5} = A_{4} + D_{5} = 3 + 8 = 11$，$B_{5} = B_{4} + D_{5} = 19 + 8 = 27$。 - 对 $B_{5}$ 应用 $\min$，$A_{5} = 11$，$B_{5} = \min(27, 23) = 23$。 - $A_{5} + B_{5} = 11 + 23 = 34$。 可以证明这是最大值。 ### 计分方式 本题共六组测试。只有通过该组及其所有依赖组全部测试，才能获得该组分数。部分组不要求通过样例测试。**Offline-evaluation** 表示该组结果仅在赛后可见。 | 子任务 | 分值 | 额外约束 | < |子任务依赖 | 备注 | |:-----:|:------:|:----------------------:|:--:|:---------------:|:-------:| | | | $n$ | $D_i$ | | | | 0 | 0 | -- | -- | -- | 样例 | | 1 | 13 | $n \le 15$ | -- | 0 | | | 2 | 18 | $n \le 300$ | -- | 0, 1 | | | 3 | 14 | $n \le 5000$ | $D_{i} = 0$ | -- | | | 4 | 16 | $n \le 5000$ | -- | 0--3 | | | 5 | 19 | -- | $D_{i} = 0$ | 3 | | | 6 | 20 | -- | -- | 0--5 | **Offline-evaluation.** | 翻译由 ChatGPT-4.1 完成。