714 . 偷懶

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

aacpschool

User's AC Ratio

100.0% (3/3)

Submission's AC Ratio

75.0% (3/4)

Tags

apcsc apcsc-greedy

Description

在接下來的 $N$ 天，學姐打算每天打工。第 $i$ 天打工可以賺到的錢是 $A_i$，但是如果她選擇偷懶的話當天的薪水會降到 $B_i(B_i \le A_i)$，為了生存，這 $N$ 天學姐至少要賺到 $K$ 塊錢，請問她最多可以偷懶幾天？

Input Format

輸入有三行，第一行包含兩個正整數分別對應到題目中的 $N$ 和 $K$，第二行有 $N$ 個正整數，第 $i$ 個正整數代表題目中的 $A_i$，第三行也有 $N$ 個正整數，第 $i$ 個正整數則代表題目中的 $B_i$。

  • $1 \le N \le 10^ 5, 0 \le K \le 10^ 9$
  • $0 \le A_i, B_i \le 10^ 4$
  • $B_i \le A_i$, $\forall$ $i$
  • $\sum A_i \ge K$

Output Format

輸出只有一行，包含一個整數代表最多能偷懶幾天。

Sample Input 1

5 10
3 3 3 3 3
2 2 2 2 2

Sample Output 1

5

Sample Input 2

5 20
5 6 7 8 9
4 3 2 1 0

Sample Output 2

3

Hints

Problem Source

TNFSH OJ

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~21 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 524288 65536 1 2
1 3000 524288 65536 1 2
2 3000 524288 65536 2
3 3000 524288 65536 2
4 3000 524288 65536 2
5 3000 524288 65536 2
6 3000 524288 65536 2
7 3000 524288 65536 2
8 3000 524288 65536 2
9 3000 524288 65536 2
10 3000 524288 65536 2
11 3000 524288 65536 2
12 3000 524288 65536 2
13 3000 524288 65536 2
14 3000 524288 65536 2
15 3000 524288 65536 2
16 3000 524288 65536 2
17 3000 524288 65536 2
18 3000 524288 65536 2
19 3000 524288 65536 2
20 3000 524288 65536 2
21 3000 524288 65536 2
Submit
Back to Top