#PU1352. USACO 2023 December Contest, Silver — Problem 3. Target Practice

USACO 2023 December Contest, Silver — Problem 3. Target Practice

USACO 2023 December Contest, Silver — Problem 3. Target Practice

题目描述

Bessie is a robovine, also known as a cowborg. She is on a number line trying to shoot a series of TT (1≤T≤105)(1 \leq T \leq 10^5) targets located at distinct positions. Bessie starts at position 00 and follows a string of CC (1≤C≤105)(1 \leq C \leq 10^5) commands, each one of L, F, or R: L: Bessie moves one unit to the left. R: Bessie moves one unit to the right. F: Bessie fires. If there is a target at Bessie's current position, it is hit and destroyed, and cannot be hit again. If you are allowed to change up to one command in the string to a different command before Bessie starts following it, what is the maximum number of targets that Bessie can hit?

输入格式

The first line contains TT and CC. The next line contains the locations of the TT targets, distinct integers in the range [−C,C][-C,C]. The next line contains the command string of length CC, containing only the characters F, L, and R.

输出格式

Print the maximum number of targets that Bessie can hit after changing up to one command in the string.

数据范围

Inputs 4-6: T,C≤1000T,C \le 1000 Inputs 7-15: No additional constraints. Problem credits: Suhas Nagar

样例

样例 1

3 7
0 -1 1
LFFRFRR
3
If you make no changes to the string, Bessie will hit two targets:
Command | Position | Total Targets Hit
--------+----------+-------------------
Start   |  0       | 0 
L       | -1       | 0
F       | -1       | 1
F       | -1       | 1 (can't destroy target more than once)
R       |  0       | 1
F       |  0       | 2
R       |  1       | 2
R       |  2       | 2
If you change the last command from R to F, Bessie will hit all three targets:
Command | Position | Total Targets Hit
--------+----------+-------------------
Start   |  0       | 0 
L       | -1       | 0
F       | -1       | 1
F       | -1       | 1 (can't destroy target more than once)
R       |  0       | 1
F       |  0       | 2
R       |  1       | 2
F       |  1       | 3

样例 2

1 5
0
FFFFF
1
If the commands are left unchanged, the only target at 0 will be destroyed.
Since a target cannot be destroyed multiple times, the answer is 1.

样例 3

5 6
1 2 3 4 5
FFRFRF
3