AT_abc076_d.[ABC076D] AtCoder Express

2168 年，AtCoder 公司不断发展壮大，最终决定建设一条名为 “AtCoder 特急” 的铁路。

现在，社长高桥君计划按如下方式运营 “AtCoder 特急” 的列车：

• 列车的行驶总时间为 $t_1 + t_2 + t_3 + \ldots + t_N$ 秒。
• 在最初的 $t_1$ 秒内，列车的速度不得超过 $v_1$ 米每秒。接下来的 $t_2$ 秒内，列车的速度不得超过 $v_2$ 米每秒。之后的 $t_3$ 秒及其后的每一段时间也同理。
• 在最后的 $t_N$ 秒内，列车的速度不得超过 $v_N$ 米每秒。

此外，受限于列车的性能，加速度必须在 $\pm 1\,\mathrm{m/s^2}$ 以内。同时，列车在出发和到达时都必须处于静止状态。

请你求出列车从出发到停下期间能够行驶的最大距离。

输入通过标准输入给出，格式如下：

$N$ $t_1$ $t_2$ $t_3$ … $t_N$ $v_1$ $v_2$ $v_3$ … $v_N$

请输出列车从出发到停下期间能够行驶的最大距离。只要绝对误差不超过 $10^{-3}$，即可视为正确。

约束条件

• $1 \leq N \leq 100$
• $1 \leq t_i \leq 200$
• $1 \leq v_i \leq 100$
• 输入均为整数

样例解释 1

• 最初的 $30$ 秒内，以 $1\,\mathrm{m/s^2}$ 的加速度加速，期间行驶 $450$ 米。
• 接下来的 $40$ 秒内，以 $30\,\mathrm{m/s}$ 匀速行驶，期间行驶 $1200$ 米。
• 最后的 $30$ 秒内，以 $-1\,\mathrm{m/s^2}$ 的加速度减速，期间行驶 $450$ 米。
• 总共可以行驶 $450 + 1200 + 450 = 2100$ 米。

样例解释 2

• 最初的 $34$ 秒内，以 $1\,\mathrm{m/s^2}$ 的加速度加速，期间行驶 $578$ 米。
• 接下来的 $26$ 秒内，以 $34\,\mathrm{m/s}$ 匀速行驶，期间行驶 $884$ 米。
• 再接下来的 $4$ 秒内，以 $1\,\mathrm{m/s^2}$ 的加速度加速，期间行驶 $144$ 米。
• 再接下来的 $8$ 秒内，以 $38\,\mathrm{m/s}$ 匀速行驶，期间行驶 $304$ 米。
• 最后的 $38$ 秒内，以 $-1\,\mathrm{m/s^2}$ 的加速度减速，期间行驶 $722$ 米。
• 总共可以行驶 $578 + 884 + 144 + 304 + 722 = 2632$ 米。

样例解释 3

• 最初的 $6$ 秒内，以 $1\,\mathrm{m/s^2}$ 的加速度加速，期间行驶 $18$ 米。
• 接下来的 $2$ 秒内，以 $6\,\mathrm{m/s}$ 匀速行驶，期间行驶 $12$ 米。
• 再接下来的 $4$ 秒内，以 $-1\,\mathrm{m/s^2}$ 的加速度减速，期间行驶 $16$ 米。
• 再接下来的 $14$ 秒内，以 $2\,\mathrm{m/s}$ 匀速行驶，期间行驶 $28$ 米。
• 最后的 $2$ 秒内，以 $-1\,\mathrm{m/s^2}$ 的加速度减速，期间行驶 $2$ 米。
• 总共可以行驶 $18 + 12 + 16 + 28 + 2 = 76$ 米。

样例解释 4

• 最初的 $4.5$ 秒内，以 $1\,\mathrm{m/s^2}$ 的加速度加速，期间行驶 $10.125$ 米。
• 最后的 $4.5$ 秒内，以 $-1\,\mathrm{m/s^2}$ 的加速度减速，期间行驶 $10.125$ 米。
• 总共可以行驶 $10.125 + 10.125 = 20.25$ 米。

由 ChatGPT 4.1 翻译