LCC '21 Contest 1 J3 - Candy Collecting

View as PDF

Submit solution

Points: 5
Time limit: 2.0s
Memory limit: 64M

Problem type

You have found yourself in a Halloween cave with N paths. You already know that with these N paths, you will end up in 1 of K endings numbered from 1 to K, each one filled with some amount of candy! Of course, you want to get as much candy as possible, but after exploring 2 paths, spooky ghosts will chase you, and you'll need to get out of there as fast as possible! After grabbing candy by going through a path, you cannot visit the paths next to it, as the ghosts will block you from entering them. Can you figure out the maximum amount of candy you can get by going through at most 2 distinct paths that aren't next to each other?

Note: You do not necessarily have to go through 2 paths.

Input Specification

The first line will contain N (1 \leq N \leq 10^3), the number of paths, and K (1 \leq K \leq N), the number of endings. The next line will contain K integers a_i (1 \leq a_i \leq 1000), representing how much candy is in each path ending, respectively. The next line will contain N integers, ranging from 1 to K depending on which ending it leads to, or -1 if it is a dead end.

Output Specification

Output 1 integer, the total number of candy you can get before the spooky ghosts come for you.

Sample Input 1

5 4
1 2 3 4
1 2 3 4 -1

Sample Output 1


Sample Explanation 1

You can go through the 4th entrance to get to the 4th ending, getting 4 candy. Then, you can go through the 2nd entrance to get another 2 candies, adding up to 6 in total.

Sample Input 2

8 3
91 59 1
2 1 2 -1 -1 -1 3 3

Sample Output 2


Sample Explanation 2

After exploring the first ending and getting 91 candies, the only way you can get more would be to go through the 7th or 8th entrances, getting 1 more candy. You cannot enter the second ending since you've entered the first one, and the only paths are next to the path of the first one.


There are no comments at the moment.