AT_abc076_d [ABC076D] AtCoder Express

[problemUrl]: https://atcoder.jp/contests/abc076/tasks/abc076_d $ 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 $ 以内でなければならない。また、走行開始時と走行終了時には列車は止まっていなければならない。 列車が発車してから停車するまでに走れる最大の距離を求めなさい。

入力は以下の形式で標準入力から与えられる。 > $ 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 $ - 入力はすべて整数である ### Sample Explanation 1  - 最初の $ 30 $ 秒は、加速度を $ 1m/s^2 $ にし、加速します。その間に列車は $ 450m $ 走ります。 - 次の $ 40 $ 秒は、速度 $ 30m/s $ を保ちます。その間に列車は $ 1200m $ 走ります。 - 最後の $ 30 $ 秒は、加速度を $ -1m/s^2 $ にし、減速します。その間に列車は $ 450m $ 走ります。 合計で、$ 450 $ + $ 1200 $ + $ 450 $ = $ 2100m $ 走ることができます。 ### Sample Explanation 2  - 最初の $ 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 $ 走ることができます。 ### Sample Explanation 3  - 最初の $ 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 $ 走ることができます。 ### Sample Explanation 4  - 最初の $ 4.5 $ 秒は、加速度を $ 1m/s^2 $ にし、加速します。その間に列車は $ 10.125m $ 走ります。 - 最後の $ 4.5 $ 秒は、加速度を $ -1m/s^2 $ にし、減速します。その間に列車は $ 10.125m $ 走ります。 合計で、$ 10.125 $ + $ 10.125 $ = $ 20.25m $ 走ることができます。