2162 . 辣椒頭大會
TopCoder
Description
在每一年的辣椒頭大會中，人人剃龐克頭，寫著物理；而在最後一天，將有一個特別的活動：吃辣椒比賽！現在呢，你身為吃辣椒比賽的一員，想要獲得勝利。你發現，檯面上從左到右分別有$N$個辣椒，而每一個辣椒都會有兩個數值，第$i$個辣椒會有$a_i$的「好吃度」，譬如說有特別的風味等、也會有$b_i$的「辣度」。比賽有兩個規則：
- 吃辣椒的時候，必須吃連續的辣椒！也就是說，你只能選一個$1 \leq l \leq r \leq N$，然後將第$l$個辣椒到第$r$個辣椒都吃了。
- 為了避免一些人投機取巧，吃得很少，所以至少必須得吃$L$個辣椒（包含$L$個，即$r - l + 1 \geq L $），只可多，不可少。
你也發現了評審們的評分標準了：如果你吃了$l$到$r$的這些辣椒，那評審們給你的分數將會是
$$\frac{\sum\limits_{i=l}^ r a_i}{\sum\limits_{i=l}^ r b_i}$$
（若不確定$\sum_l^ {r} a_i$的意思，可以看下面的Hints）。請問，給你$N$和所有的$a_i$、$b_i$，你能夠拿到的最高分數為何？如果你的答案與正確答案的相對誤差小於$10^ {-5}$，就會算對。
Testdata Set
- $L = 1$
- $N\leq 10^ 3$
- $\forall i, \; b_i = 1$
- No further constraints
Input Format
第一行將有兩個正整數$N, L$。第二、三行將分別有$N$個數字，第一行的第$i$個數字為$a_i$，第二行的第$j$個數字為$b_j$，且對於所有的測試資料，保證$1 \leq L \leq N \leq 2 \times 10^ 5$，$1 \leq a_i, b_i \leq 10^ 5$。
此外，
對於佔分$10\%$的測資，滿足$L = 1$
對於佔分$15\%$的測資，滿足$N\leq 10^ 3$
對於佔分$30\%$的測資，滿足$\forall i, \; b_i = 1$
Output Format
請輸出一個數字，代表答案。若你的答案與正確答案的相對誤差小於$10^ {-5}$，那一筆就會獲得AC。兩個實數$a, b$的相對誤差計算方式為：$\min(|a - b|, \frac{|a - b|}{\max(a - b)})$。
Sample Input 1
5 2
9496 9496 9496 9496 9496
1 2 1 2 1
第二筆的輸入：
5 5
7 3 6 8 9
2 3 1 1 1
Sample Output 1
7122.0000
第二筆的答案：
4.1250
Hints
第一筆選擇$(l, r) = (1, 3)$可以得分數$\frac{9496 + 9496 + 9496}{1 + 2 + 1} = 7122$；第二筆，因為$L = 5$，只能選擇$(l, r) = (1, 5)$，得分$\frac{7 + 3 + 6 + 8 + 9}{2 + 3 + 1 + 1 + 1} = 4.125$。
還有，$\sum\limits_{i=l}^ r a_ i$的意思就是$a_ l + a_ {l + 1} + \cdots + a_ r$。
精度不夠？可以使用long double哦！若使用long double，printf請使用%Lf。
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 1~8 | $L = 1$ | 10 |
| 2 | 0, 9~15 | $N\leq 10^ 3$ | 15 |
| 3 | 16~20 | $\forall i, \; b_i = 1$ | 30 |
| 4 | 0, 9~15, 21~30 | No further constraints | 45 |