← 返回题目列表

AtCoder · abc076_d

D. AtCoder快车

中文机器翻译题面 查看原题

分数: 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