409988: GYM103886 O Vista (Cereal Mountains II)

After climbing the tallest mountains in Agastya's kingdom, Larry decides to go on a relaxing hike.

There are given $$$n$$$ cereal mountains arranged in a line, numbered $$$1 \dots n$$$ $$$(2 \leq n \leq 10^5)$$$. The cereal mountains are described as $$$2$$$ arrays $$$h_1, h_2, \dots, h_n$$$ and $$$v_1, v_2, \dots, v_n$$$; the heights of the mountains and the greatness of the view. Mountain $$$i$$$ has a height of $$$h_i$$$, and a view with greatness $$$v_i$$$ $$$(0 \leq h_i, v_i \leq 10^9)$$$.

Larry wants to hike a subarray of mountains. The difficulty of a hike $$$d(l, r)$$$ is defined as the difference between the highest and lowest mountain in the range $$$[l, r]$$$, more specifically: $$$d(l, r) = \max(h_{l}, h_{l+1}, \dots, h{r}) - \min(h_{l}, h_{l+1}, \dots, h{r})$$$.

The enjoyment of a hike $$$f(l, r)$$$ is defined as the sum of the greatness of the views of the mountains in the range $$$[l, r]$$$ divided by the difficulty of the range, more specifically: $$$f(l, r) = \frac{\sum_{n=l}^{r} v_{n}}{d(l, r)}$$$

Since Larry like challenges, he wants to hike a subarray with a difficulty greater than $$$0$$$.

Find the maximum enjoyment Larry can achieve in a hike with a difficulty greater than $$$0$$$.

It is guaranteed that there is at least one hike that fits the constraints.

The first line contains one integer $$$n$$$.

The next line contains $$$n$$$ space separated integers $$$v_1, v_2, \dots, v_n$$$.

The next line contains $$$n$$$ space separated integers $$$h_1, h_2, \dots, h_n$$$.

Print one real number, the maximum enjoyment of a hike with a difficulty greater than one. Your answer is considered correct if the relative or absolute error is less than or equal to $$$10^{-6}$$$.

More specifically, if your answer is $$$a$$$ and the expected answer is $$$b$$$, your answer will be accepted if $$$\frac{|a-b|}{\max(1, |b|)} \leq 10^{-6}$$$.

5
0 4 5 5 4
6 5 0 8 9

9.00000000000000000000

10
6 6 9 9 9 1 1 4 0 1
22 40 18 1 9 35 39 7 19 30

2.25000000000000000000

In the first sample case, the largest enjoyment of a hike we can get is with the hike ($$$4$$$, $$$5$$$).

The total enjoyment we will get is $$$(5 + 4)/(9 - 8) = 9$$$.

In the second sample case, we should take the hike ($$$1$$$, $$$3$$$).

Problem Credits: Agastya Goel, Eric Hsu