分数: 400 点
问题陈述
2168年,比现在规模大得多的AtCoder Inc.正在启动名为“特快列车”的特快列车服务。 AtCoder Express.
在高桥社长制定的计划中,列车运行如下:
- 一列火车将运行 (t_1 + t_2 + t_3 + ... + t_N) 秒。
- 在第一个 t_1 秒,火车的运行速度最多为 v_1 m/s(米每秒)。同样,在随后的 t_2 秒,火车的运行速度最多为 v_2 米/秒,等等。
根据列车的规格,列车的加速度必须始终在 ±1m/s^2。此外,火车必须在运行的起点和终点停下。
求火车在运行中可以行驶的最大可能距离。
约束
- 1 \leq N \leq 100
- 1 \leq t_i \leq 200
- 1 \leq v_i \leq 100
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N t_1 t_2 t_3 … t_N v_1 v_2 v_3 … v_N
输出
打印火车在运行中可以行驶的最大距离。
如果输出与法官输出的绝对差最大为 10^{-3}.
示例输入 1
1 100 30
示例输出 1
2100.000000000000000

火车运行时达到的最大距离如下:
- 在第一个 30 秒,它的加速速度为 1m/s^2,覆盖 450 米。
- 在随后的 40 秒,它保持的速度 30m/s,覆盖 1200 米。
- 在最后 30 秒,以加速度减速 -1m/s^2,覆盖 450 米。
走过的总距离是 450 + 1200 + 450 = 2100 米。
示例输入 2
2 60 50 34 38
示例输出 2
2632.000000000000000

火车运行时达到的最大距离如下:
- 在第一个 34 秒,它的加速速度为 1m/s^2,覆盖 578 米。
- 在随后的 26 秒,它保持的速度 34m/s,覆盖 884 米。
- 在随后的 4 秒,它的加速速度为 1m/s^2,覆盖 144 米。
- 在随后的 8 秒,它保持的速度 38m/s,覆盖 304 米。
- 在最后 38 秒,以加速度减速 -1m/s^2,覆盖 722 米。
走过的总距离是 578 + 884 + 144 + 304 + 722 = 2632 米。
示例输入 3
3 12 14 2 6 2 7
示例输出 3
76.000000000000000

火车运行时达到的最大距离如下:
- 在第一个 6 秒,它的加速速度为 1m/s^2,覆盖 18 米。
- 在随后的 2 秒,它保持的速度 6m/s,覆盖 12 米。
- 在随后的 4 秒,以加速度减速 -1m/s^2,覆盖 16 米。
- 在随后的 14 秒,它保持的速度 2m/s,覆盖 28 米。
- 在最后 2 秒,以加速度减速 -1m/s^2,覆盖 2 米。
走过的总距离是 18 + 12 + 16 + 28 + 2 = 76 米。
示例输入 4
1 9 10
示例输出 4
20.250000000000000000

火车运行时达到的最大距离如下:
- 在第一个 4.5 秒,它的加速速度为 1m/s^2,覆盖 10.125 米。
- 在最后 4.5 秒,以加速度减速 -1m/s^2,覆盖 10.125 米。
走过的总距离是 10.125 + 10.125 = 20.25 米。
示例输入 5
10 64 55 27 35 76 119 7 18 49 100 29 19 31 39 27 48 41 87 55 70
示例输出 5
20291.000000000000