Problem A
Brinnande träd
En skogsbrand har brutit ut i ett naturreservat. I området finns det en sällsynt art av träd som inte finns någon annanstans i världen. Du befinner dig i skogen, och på din väg hem tänker du försöka rädda så många träd som möjligt.
Totalt finns det $N$ sällsynta träd numrerade från $1$ till $N$, och du kommer springa förbi dem i den ordningen. Det tar $A_ i$ sekunder för dig att rädda det $i$:te trädet, men du måste påbörja räddningen senast sekund $X_ i$, annars brinner trädet upp. Däremot gör det inget om sekund $X_ i$ inträffar medan du håller på att rädda trädet.
Att springa mellan träden tar ingen tid alls för dig, men du kan bara springa framåt och kan därför bara rädda träd i den ordning som du besöker dem. Däremot vet du att
\[ X_1 \leq X_2 \leq X_3, \leq \cdots \leq X_ N \]Hitta det maximala antalet träd du kan rädda.
Indata
Den första raden innehåller ett heltal $N$ ($1 \leq N \leq 4 \cdot 10^5$), antalet träd.
Den andra raden innehåller $N$ heltal $X_ i$ ($0 \leq X_ i \leq 10^9$), senaste sekunden du måste påbörja en räddning av det $i$:te trädet.
Den tredje raden innehåller $N$ heltal $A_ i$ ($1 \leq A_ i \leq 10^9$), tiden det tar att rädda det $i$:te trädet.
Utdata
Skriv ut ett heltal, det maximala antalet träd som går att rädda.
Poängsättning
Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.
|
Grupp |
Poängvärde |
Gränser |
|
$1$ |
$10$ |
$A_1 = A_2 = \cdots = A_ N$ |
|
$2$ |
$18$ |
$X_1 = X_2 = \cdots = X_ N$ |
|
$3$ |
$15$ |
$N, A_ i, X_ i \leq 100$ |
|
$4$ |
$22$ |
$N \leq 2000$ |
|
$5$ |
$35$ |
Inga ytterligare begränsningar |
| Sample Input 1 | Sample Output 1 |
|---|---|
6 1 1 2 2 5 8 2 3 3 5 2 2 |
4 |
| Sample Input 2 | Sample Output 2 |
|---|---|
5 0 0 1 2 3 5 1 1 1 1 |
4 |
| Sample Input 3 | Sample Output 3 |
|---|---|
3 5 5 5 6 1 1 |
2 |
