An Animal Contest 3 P7 - Monkey Lasers

View as PDF

Submit solution

Points: 25 (partial)
Time limit: 2.0s
Memory limit: 256M

Problem type

Moses the monkey finds himself in a grid with a ton of lasers!

The grid has N+2 rows numbered from 0 to N+1, and M columns numbered from 1 to M. Each row i from row 1 to N has a special laser located on cell c_i of that row. However, each laser can only face one direction d_i, either left or right, which Moses knows beforehand. A laser located at column i facing left will vaporize everything in any cell on the same row with column j where j < i. Similarly, a laser facing right will vaporize every cell on the same row with column j > i.

Moses can start off in any cell on row 0. He wishes to reach row N+1, but has a strong desire to not be vaporized. Thus, from his current cell, Moses can move to any adjacent cell inside the grid that does not cause him to be vaporized, incurring a cost of 1. However, he cannot move up. If Moses moves into a row where the laser is not looking in his direction, he uses his handy-dandy gadget to destroy it permanently. Note that Moses is not allowed to enter a cell with a laser.

Moses also has a special ability that he can use, and by using his special ability once, he flips the direction of every remaining laser. Using this ability while he is in row i has a cost of k_i. Note that the special ability is available to be used an infinite number of times in any row between 0 and N inclusive.

Given that Moses can end off in any cell on row N+1, what is the smallest possible cost required to reach row N+1 without being vaporized?


1 \le N \le 2 \times 10^5

2 \le M \le 10^9

1 \le c_i \le M

1 \le k_i \le 10^9

Subtask 1 [10%]

1 \le N \le 300

Subtask 2 [30%]

1 \le N \le 3 \times 10^3

Subtask 3 [60%]

No additional constraints.

Input Specification

The first line contains two space-separated integers N and M.

The next line contains N space-separated integers c_i, the position of the laser for each row from 1 to N.

The third line contains a string d of length N where the i^{th} laser is facing left if d_i is L and facing right if d_i is R.

The fourth and final line contains N+1 space-separated integers k_i, the cost of using the special ability on each row from 0 to N.

Output Specification

Output one integer representing the minimum cost Moses will incur to reach row N+1.

Sample Input 1

2 3
2 1
7 727 69

Sample Output 1


Explanation for Sample 1

For the purposes of this explanation, assume that cell (0, 1) is the top-leftmost cell and cell (N+1, M) is the bottom-rightmost cell in the above diagrams. The lasers in each row are labeled with the direction they are facing, L for left and R for right; Moses is represented by the character P.

The diagrams show Moses' situation every time he uses his special ability or makes a move. The following lines describe Moses' journey in chronological order.

The top-left diagram shows the grid's initial state. To minimize cost, Moses decides to start at cell (0, 1).

The top-middle diagram shows the grid's state after Moses uses his special ability while at row 0. This incurs a cost of 7.

Moses moves into the grid at cell (1, 1), incurring a cost of 1. He destroys the laser on row 1. This is seen in the top-right diagram.

Moses moves right into cell (1, 2), incurring a cost of 1. Since the laser is no longer there, this is a legal move. This is shown in the bottom-left diagram.

Moses then moves down into cell (2, 2), incurring a cost of 1. He destroys the laser on row 2. This is depicted by the bottom-middle diagram.

Moses moves down one more time arriving at cell (3, 2), incurring a cost of 1. This is shown by the bottom-right diagram.

Moses has reached row N+1 incurring a total cost of 11, which can be proven to be minimal.

Sample Input 2

3 3
1 3 2
420 563 447 7216

Sample Output 2



  • -1
    Sonaion  commented on Sept. 26, 2022, 5:57 p.m.

    Hey, may you give one bigger example, in general I would appreciate if one Big Example would be given as A File for Testing.