[JOI2025 预选赛 R2] 台球

ID: 13566

远端评测题

1000ms

1000MiB

难度: 3

上传者:

标签>

2024

JOI（日本）

题目描述

比太郎在玩台球。JOI 国的台球是使用摆在台上的 $N$ 个球 $1,2,\ldots,N$ 的游戏，台上设有落球用的洞。落在洞里的球不会放回台上，那个球也不能再一次落洞。比太郎的目的是尽量把写有大号码的球落在洞里。

打球是一项需要集中注意力的工作。初始，比太郎的注意力是 $X$ ，击打球 $i$ （ $1≤i≤N$ ）后集中力减少 $A_i$ 。集中力不足 $A_i$ 时，不能击打球 $i$ 。

另外，在该台球中存在关于落球顺序的规则，具体来说， $P_i=-1$ （ $1≤i≤N$ ）时，球 $i$ 可以随时落下， $P_i ≠ -1$ 时，为了使球 $i$ 落下，球 $P_i$ 必须已经落下。

当给出了比太郎所具有的集中力和各球的信息时，判定比太郎是否能够将球击落洞中，在能够击落下球的情况下，求出能够落下的球的编号的最大值。

输入数据以如下格式给出：

$$\begin{aligned} &N\ X\\ & A_1\ A_2\ \cdots\ A_N\\ &P_1\ P_2\ \cdots\ P_N\\ \end{aligned} $$

输出一行一个整数，为比太郎击落的球的编号最大值。

如果比太郎无法击落球，输出 $-1$ 。

6 7
1 2 4 3 10 100
-1 -1 -1 -1 -1 -1

5 12
1 2 3 5 8
-1 1 2 3 4

8 10
3 1 4 1 5 9 2 6
-1 1 2 -1 4 4 5 7

2 1000000000000000
1 1
2 1

-1

9 2468024680
123456789 234567891 345678912 456789123 567891234 678912345 789123456 891234567 912345678
6 5 4 -1 3 2 1 9 8

首先，比太郎的集中力是 $7$ 。对于所有的 $i$ （ $1≤i≤N$ ），由于 $P_i=-1$ ，所以只要集中力足够，所有的球都可以随时掉到洞里。

例如，如下所示，比太郎可以击落 $4$ 个球。

子任务如下：