BAPC21-057.Implementation Irregularities

Medium · 1 s · 256 MB

icpc
bapc
2021

Impressed by the performance of the top teams at the recent BAPC preliminaries, you started to wonder whether teams were allowed to use one or multiple computers to implement their solutions.

Instead of unnecessarily bothering the organization with more questions, you will figure this out by yourself. Being a jury member, you already have estimates for the computer time required to solve each problem.

Using this information, and the time in the contest at which the top team solved each of their solved problems, compute the minimal number of computers used by the team.

The team may work on multiple problems before getting any one of them accepted. Furthermore, the contestants are great multitaskers and can work on a single problem using multiple computers at the same time, but each computer can only be used for one problem at a time.

Giriş formatı

The input consists of:

• One line containing an integer $n$ ( $1\leq n\leq 10^5$ ), the number of problems in the contest.

• One line containing $n$ integers $t_1, t_2, \dots, t_n$ ( $1\leq t_i \leq 10^4$ ), the computer time required to solve problem $i$ .

• One line containing $n$ integers $s_1, s_2, \dots, s_n$ ( $1\leq s_i \leq 10^9$ or $s_i = -1$ ), the time at which problem $i$ was solved, or $-1$ if it was not solved.

It is guaranteed that the team solved at least one problem.

Çıxış formatı

Output the minimum number of computers used by the team.

Qeyd

Source: Benelux Algorithm Programming Contest 2021 · Author: Ragnar Groot Koerkamp · License: CC BY-SA 4.0 · Original: https://bapc.eu · Statement adapted for AlgoLens and shared under the same license. · 14 of the 42 original test cases (the largest) are omitted here to keep the problem lightweight.

Nümunələr

Giriş #1

11
50 8 10 6 300 5 6 3 18 5 12
117 23 63 6 -1 48 80 42 37 13 131

Çıxış #1

Giriş #2

1
10
3

Çıxış #2

Giriş #3

2
2 4
3 3

Çıxış #3

Giriş #4

2
4 6
10 10

Çıxış #4