4620 . Easy Choice

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

Description

題目 PDF 檔在這裡

存在 $N$ 個物品，編號由 $1$ 到 $N$，編號 $i$ 的物品有其價值 $V_i$ 及代價 $C_i$ ，選擇其中一些物品。

假設 $m$ 為所選物品的數量而 ($A_1$,$A_2$,...,$A_m$) 為所選物品的編號集合($\forall 1\le i < j\le m$ , $A_i < A_j$)。

必須滿足 $\forall 1\le {i-1} < i\le m$ , $A_i-A_{i-1}\le K$，$A_1=1 , A_m=N$。

對於選取物品的分數定義為$\left\lfloor \dfrac{\sum_{i=1} ^ {m} V_{A_i}}{\sum_{i=1} ^ {m} C_{A_i}}\right\rfloor$ ， 請求出滿足條件下所選物品分數的最大值

Input Format

第一行包含兩個整數 $N$ , $K$ ($1\le K\le N\le 2\cdot 10 ^ 5$)

第二行包含 $N$ 個整數，第 $i$ 個整數代表 $V_i$ ($1\le V_i \le 10 ^ 5$)

第三行包含 $N$ 個整數，第 $i$ 個整數代表 $C_i$ ($1\le C_i \le 10 ^ 5$)

Output Format

輸出一個整數表示答案

Sample Input 1

2 1
3 3
1 2

Sample Output 1

2

Sample Input 2

5 3
1 2 3 4 5
1 1 1 1 1

Sample Output 2

3

Hints

Problem Source

TopCoder

roychuang

User's AC Ratio

100.0% (3/3)

Tags

小社賽 113 學年度

Problem Setter

Created by ianwen

Subtasks

No. Testdata Range Constraints Score
1 0~13 $1\le N\le 3000$ 17
2 0~33 無其他限制 83

Testdata and Limits

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