시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
3 초 | 512 MB | 43 | 15 | 14 | 33.333% |
It is the night before the grand opening of a new art gallery. The gallery consists of n rooms, numbered from 1 to n. The rooms are organized sequentially, with room 1 being connected by a door to room 2, and room 2 being connected to room 3, and so on. Each room has a door that leads into it from the preceding room. That door is either locked or unlocked. If the door is unlocked, the room will contain a key. Otherwise, it will not contain a key.
To enter a room with a locked door, you must use a key that is compatible. Each key can open a subset of the doors. The gallery uses a special lock and key system to deter thieves. A key can only be used once, since a locked door will consume any key used to open it.
You start in the first room, which is guaranteed to contain a key, and would like to enter as many rooms as possible. The more rooms you can enter, the more paintings you can. . . admire.
Assuming you use keys optimally, what is the maximum number of rooms you can enter?
The first line contains a single integer n (2 ≤ n ≤ 300), which is the number of rooms.
The next n lines describe the rooms in the gallery in order. Each of these lines contains either:
The first room is guaranteed to have x > 0.
Display the maximum number of rooms you can enter.
7 3 2 6 7 0 2 2 7 2 5 6 0 0 0
5
6 3 4 5 6 2 4 5 1 4 0 0 0
6