2162 . 辣椒頭大會

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

腦子裝咖哩
想像不出自己 AC 的題目是實作不出來的！雖然想像得出來也不一定可以就是了

User's AC Ratio

87.0% (47/54)

Submission's AC Ratio

35.1% (101/288)

Tags

CKcon 2020-CKcon 2020-CKcon-fin

Description

在每一年的辣椒頭大會中，人人剃龐克頭，寫著物理；而在最後一天，將有一個特別的活動：吃辣椒比賽！現在呢，你身為吃辣椒比賽的一員，想要獲得勝利。你發現，檯面上從左到右分別有N個辣椒，而每一個辣椒都會有兩個數值，第i個辣椒會有ai的「好吃度」，譬如說有特別的風味等、也會有bi的「辣度」。比賽有兩個規則：

  • 吃辣椒的時候，必須吃連續的辣椒！也就是說，你只能選一個1≤l≤r≤N，然後將第l個辣椒到第r個辣椒都吃了。
  • 為了避免一些人投機取巧，吃得很少，所以至少必須得吃L個辣椒（包含L個，即r−l+1≥L），只可多，不可少。

你也發現了評審們的評分標準了：如果你吃了l到r的這些辣椒，那評審們給你的分數將會是

∑i=lrai∑i=lrbi

（若不確定∑lrai的意思，可以看下面的Hints）。請問，給你N和所有的ai、bi，你能夠拿到的最高分數為何？如果你的答案與正確答案的相對誤差小於10−5，就會算對。

Testdata Set

  1. L=1
  2. N≤103
  3. ∀i,bi=1
  4. No further constraints

Input Format

第一行將有兩個正整數N,L。第二、三行將分別有N個數字，第一行的第i個數字為ai，第二行的第j個數字為bj，且對於所有的測試資料，保證1≤L≤N≤2×105，1≤ai,bi≤105。

此外，
對於佔分10%的測資，滿足L=1
對於佔分15%的測資，滿足N≤103
對於佔分30%的測資，滿足∀i,bi=1

Output Format

請輸出一個數字，代表答案。若你的答案與正確答案的相對誤差小於10−5，那一筆就會獲得AC。兩個實數a,b的相對誤差計算方式為：min(|a−b|,|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)可以得分數9496+9496+94961+2+1=7122；第二筆，因為L=5，只能選擇(l,r)=(1,5)，得分7+3+6+8+92+3+1+1+1=4.125。

還有，∑i=lrai的意思就是al+al+1+⋯+ar。

精度不夠？可以使用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≤103 15
3 16~20 ∀i,bi=1 30
4 0, 9~15, 21~30 No further constraints 45

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, 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
Submit
Back to Top