TopCoder

Thumb fhvirus
FHVirus
$\Huge{破台後跑十圈操場 ZCK請 FIN }$

User's AC Ratio

84.2% (32/38)

Submission's AC Ratio

31.8% (74/233)

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

  1. $L = 1$
  2. $N\leq 10^ 3$
  3. $\forall i, \; b_i = 1$
  4. 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

第一筆的輸入:
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

第一筆的答案:
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 doubleprintf請使用%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

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 2 4
1 1000 65536 262144 1
2 1000 65536 262144 1
3 1000 65536 262144 1
4 1000 65536 262144 1
5 1000 65536 262144 1
6 1000 65536 262144 1
7 1000 65536 262144 1
8 1000 65536 262144 1
9 1000 65536 262144 2 4
10 1000 65536 262144 2 4
11 1000 65536 262144 2 4
12 1000 65536 262144 2 4
13 1000 65536 262144 2 4
14 1000 65536 262144 2 4
15 1000 65536 262144 2 4
16 1000 65536 262144 3
17 1000 65536 262144 3
18 1000 65536 262144 3
19 1000 65536 262144 3
20 1000 65536 262144 3
21 1000 65536 262144 4
22 1000 65536 262144 4
23 1000 65536 262144 4
24 1000 65536 262144 4
25 1000 65536 262144 4
26 1000 65536 262144 4
27 1000 65536 262144 4
28 1000 65536 262144 4
29 1000 65536 262144 4
30 1000 65536 262144 4