| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1.5 초 | 1024 MB | 103 | 45 | 42 | 46.154% |
In a quest to be the very best, you have decided to set out on your journey around the region to prove your strength by collecting gym badges. You begin your solo adventure with your first and only Pokemon, which happens to be a legendary Wabbit.
Your Wabbit starts at level 0ドル$ and can only gain levels by challenging gyms. There are $N$ gyms numbered from 1ドル$ to $N$ spread across the region and you can challenge them in any order. To prevent over grinding, gym $i$ has its own level cap $L_i$ where you can only challenge the gym if Wabbit’s current level is less than or equal to $L_i$.
As there may be different number of trainers to defeat in a gym, the number of levels that Wabbit gains after challenging a gym may differ. To be precise, Wabbit will gain $X_i$ levels after challenging gym $i$.
Each gym $i$ rewards successful challengers with their own unique gym badge $i$. Find the maximum number of unique gym badges that you can obtain if you challenge the gyms in an optimal way.
Your program must read from standard input.
The first line contains an integer $N,ドル the number of gyms.
The second line contains $N$ integers, where the $i$th integer represents the level Wabbit gains by challenging $i$th gym, $X_i$.
The third line contains $N$ integers, where the $i$th integer represents the level cap of the $i$th gym, $L_i$.
Your program must print to standard output.
The output should contain a single integer on a single line, the maximum number of unique gyms badges that can be won.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 15 | 1ドル ≤ N ≤ 10$ |
| 2 | 9 | $L_i$ is constant |
| 3 | 27 | 1ドル ≤ N ≤ 5000$ |
| 4 | 49 | - |
5 4 6 3 5 2 10 6 4 8 12
4
An optimal solution can be obatined when the gyms are challenged in the following order: 3ドル,ドル 4ドル,ドル 1ドル,ドル 5ドル$.
This testcase is valid for subtasks 1, 2 and 4.
5 3 9 4 2 6 10 10 10 10 10
4
An optimal solution can be obatined when the gyms are challenged in the following order: 1ドル,ドル 3ドル,ドル 4ドル,ドル 2ドル$.
Note that after the challenging gym 4ドル,ドル Wabbit is at level 9ドル$ which is within the level cap of gym 2ドル$ and can thus challenge it.
At the end Wabbit will be at level 18ドル$ which is above the level cap of the gym 5ドル$ and hence cannot challenge it.