solve this task An Animal Contest 3 P7 - Monkey Lasers
Moses the monkey finds himself in a grid with a ton of lasers!
The grid has rows numbered from to , and columns numbered from to . Each row from row
to has a special laser located on cell of that row. However, each laser can only face one direction , either left or
right, which Moses knows beforehand. A laser located at column facing left will vaporize everything in any cell on the
same row with column where . Similarly, a laser facing right will vaporize every cell on the same row with column
.
Moses can start off in any cell on row . He wishes to reach row , 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 . 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 has a cost of . Note that the special ability is available to be used
an infinite number of times in any row between and inclusive.
Given that Moses can end off in any cell on row , what is the smallest possible cost required to reach row
without being vaporized?
Constraints
Subtask 1 [10%]
Subtask 2 [30%]
Subtask 3 [60%]
No additional constraints.
Input Specification
Time limit: 2.0s Memory limit: 256M
N + 2 0 N + 1 M 1 M i 1
N ci di
i
j j < i
j > i
0 N + 1
1
i ki
0 N
N + 1 N + 1
1 ≤ N ≤ 2 × 10
5
2 ≤ M ≤ 10
9
1 ≤ ci ≤ M
1 ≤ ki ≤ 10
9
1 ≤ N ≤ 300
1 ≤ N ≤ 3 × 10
3
The first line contains two space-separated integers and .
The next line contains space-separated integers , the position of the laser for each row from to .
The third line contains a string of length where the laser is facing left if is L and facing right if is R .
The fourth and final line contains space-separated integers , the cost of using the special ability on each row
from to .
Output Specification
Output one integer representing the minimum cost Moses will incur to reach row .
Sample Input 1
2 3
2 1
LR
7 727 69
Sample Output 1
11
Explanation for Sample 1
N M
N ci 1 N
d N i
th di di
N + 1 ki
0 N
N + 1
For the purposes of this explanation, assume that cell is the top-leftmost cell and cell is the bottomrightmost 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 .
The top-middle diagram shows the grid's state after Moses uses his special ability while at row . This incurs a cost of .
Moses moves into the grid at cell , incurring a cost of . He destroys the laser on row . This is seen in the topright diagram.
Moses moves right into cell , incurring a cost of . 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 , incurring a cost of . He destroys the laser on row . This is depicted by the
bottom-middle diagram.
Moses moves down one more time arriving at cell , incurring a cost of . This is shown by the bottom-right
diagram.
Moses has reached row incurring a total cost of , which can be proven to be minimal.
Sample Input 2
3 3
1 3 2
LRR
420 563 447 7216
Sample Output 2
5 in c++. use segment tree