/ 
Time Limit: 2 sec / Memory Limit: 256 MB
配点：400 点
問題文
2168年、AtCoder 社は成長し、ついに "AtCoder特急" という鉄道を建設することを決めた。
さて、社長の高橋君は、"AtCoder特急" の列車を以下のように運行することを計画した。
- 列車の走行時間は、(t_1 + t_2 + t_3 + ... + t_N) 秒である。
- 最初の t_1 秒間は、列車は速度 v_1 m/s 以内で走っていなければならない。また、次の t_2 秒間は、列車は速度 v_2 m/s 以内で走っていなければならない。 次の t_3 秒間、またそれ以降についても同様である。
- 最後の t_N 秒間は、列車は速度 v_N m/s 以内で走っていなければならない。
ただし、列車の性能上、加速度は ±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 にし、加速します。その間に列車は 450m 走ります。
- 次の 40 秒は、速度 30m/s を保ちます。その間に列車は 1200m 走ります。
- 最後の 30 秒は、加速度を -1m/s^2 にし、減速します。その間に列車は 450m 走ります。
合計で、450 + 1200 + 450 = 2100m 走ることができます。
入力例 2
2 60 50 34 38
出力例 2
2632.000000000000000
- 最初の 34 秒は、加速度を 1m/s^2 にし、加速します。その間に列車は 578m 走ります。
- 次の 26 秒は、速度 34m/s を保ちます。その間に列車は 884m 走ります。
- 次の 4 秒は、加速度を 1m/s^2 にし、加速します。その間に列車は 144m 走ります。
- 次の 8 秒は、速度 38m/s を保ちます。その間は列車は 304m 走ります。
- 最後の 38 秒は、加速度を -1m/s^2 にし、減速します。その間に列車は 722m 走ります。
合計で、578 + 884 + 144 + 304 + 722 = 2632m 走ることができます。
入力例 3
3 12 14 2 6 2 7
出力例 3
76.000000000000000
- 最初の 6 秒は、加速度を 1m/s^2 にし、加速します。その間に列車は 18m 走ります。
- 次の 2 秒は、速度 6m/s を保ちます。その間に列車は 12m 走ります。
- 次の 4 秒は、加速度を -1m/s^2 にし、減速します。その間に列車は 16m 走ります。
- 次の 14 秒は、速度 2m/s を保ちます。その間は列車は 28m 走ります。
- 最後の 2 秒は、加速度を -1m/s^2 にし、減速します。その間に列車は 2m 走ります。
合計で、18 + 12 + 16 + 28 + 2 = 76m 走ることができます。
入力例 4
1 9 10
出力例 4
20.250000000000000000
- 最初の 4.5 秒は、加速度を 1m/s^2 にし、加速します。その間に列車は 10.125m 走ります。
- 最後の 4.5 秒は、加速度を -1m/s^2 にし、減速します。その間に列車は 10.125m 走ります。
合計で、10.125 + 10.125 = 20.25m 走ることができます。
入力例 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
Score : 400 points
Problem Statement
In the year 2168, AtCoder Inc., which is much larger than now, is starting a limited express train service called AtCoder Express.
In the plan developed by the president Takahashi, the trains will run as follows:
- A train will run for (t_1 + t_2 + t_3 + ... + t_N) seconds.
- In the first t_1 seconds, a train must run at a speed of at most v_1 m/s (meters per second). Similarly, in the subsequent t_2 seconds, a train must run at a speed of at most v_2 m/s, and so on.
According to the specifications of the trains, the acceleration of a train must be always within ±1m/s^2. Additionally, a train must stop at the beginning and the end of the run.
Find the maximum possible distance that a train can cover in the run.
Constraints
- 1 \leq N \leq 100
- 1 \leq t_i \leq 200
- 1 \leq v_i \leq 100
- All input values are integers.
Input
Input is given from Standard Input in the following format:
N t_1 t_2 t_3 … t_N v_1 v_2 v_3 … v_N
Output
Print the maximum possible that a train can cover in the run.
Output is considered correct if its absolute difference from the judge's output is at most 10^{-3}.
Sample Input 1
1 100 30
Sample Output 1
2100.000000000000000
The maximum distance is achieved when a train runs as follows:
- In the first 30 seconds, it accelerates at a rate of 1m/s^2, covering 450 meters.
- In the subsequent 40 seconds, it maintains the velocity of 30m/s, covering 1200 meters.
- In the last 30 seconds, it decelerates at the acceleration of -1m/s^2, covering 450 meters.
The total distance covered is 450 + 1200 + 450 = 2100 meters.
Sample Input 2
2 60 50 34 38
Sample Output 2
2632.000000000000000
The maximum distance is achieved when a train runs as follows:
- In the first 34 seconds, it accelerates at a rate of 1m/s^2, covering 578 meters.
- In the subsequent 26 seconds, it maintains the velocity of 34m/s, covering 884 meters.
- In the subsequent 4 seconds, it accelerates at a rate of 1m/s^2, covering 144 meters.
- In the subsequent 8 seconds, it maintains the velocity of 38m/s, covering 304 meters.
- In the last 38 seconds, it decelerates at the acceleration of -1m/s^2, covering 722 meters.
The total distance covered is 578 + 884 + 144 + 304 + 722 = 2632 meters.
Sample Input 3
3 12 14 2 6 2 7
Sample Output 3
76.000000000000000
The maximum distance is achieved when a train runs as follows:
- In the first 6 seconds, it accelerates at a rate of 1m/s^2, covering 18 meters.
- In the subsequent 2 seconds, it maintains the velocity of 6m/s, covering 12 meters.
- In the subsequent 4 seconds, it decelerates at the acceleration of -1m/s^2, covering 16 meters.
- In the subsequent 14 seconds, it maintains the velocity of 2m/s, covering 28 meters.
- In the last 2 seconds, it decelerates at the acceleration of -1m/s^2, covering 2 meters.
The total distance covered is 18 + 12 + 16 + 28 + 2 = 76 meters.
Sample Input 4
1 9 10
Sample Output 4
20.250000000000000000
The maximum distance is achieved when a train runs as follows:
- In the first 4.5 seconds, it accelerates at a rate of 1m/s^2, covering 10.125 meters.
- In the last 4.5 seconds, it decelerates at the acceleration of -1m/s^2, covering 10.125 meters.
The total distance covered is 10.125 + 10.125 = 20.25 meters.
Sample Input 5
10 64 55 27 35 76 119 7 18 49 100 29 19 31 39 27 48 41 87 55 70
Sample Output 5
20291.000000000000