Dash

题目描述

在二维平面上，高桥最初位于点 $(0, 0)$，他的初始生命值为 $H$。平面上放置了 $M$$个可恢复生命值的道具；第$i$个道具放置在$(x_i,y_i)$。 高桥将进行$N$步移动。第$i$ 步的操作如下。

令 $(x,y)$ 为他当前的坐标。 他消耗 $1$ 点生命值以根据字符串 $S$ 的第 $i$ 个字符 $S_i$ 移动到下列点之一：

$(x+1,y)$ 如果 $S_i$ 为 $R$； $(x-1,y)$ 如果 $S_i$ 为 $L$； $(x,y+1)$ 如果 $S_i$ 为 $U$； $(x,y-1)$ 如果 $S_i$ 为 $D$。

如果高桥的生命值变为负数，他会倒下并停止移动。否则，如果他移动到的点有一个道具放置，且他的生命值严格小于 $K$，那么他会在该处使用该道具，使他的生命值变为 $K$。

判断高桥是否可以完成这 $N$ 步移动而不被击倒。

输入格式

输入由标准输入按以下格式给出： $N$ $M$ $H$ $K$ $S$ $x_1$ $y_1$ $\vdots$ $x_M$ $y_M$

输出格式

如果他能完成这 $N$ 步移动而不被击倒，输出 $Yes$；否则输出 $No$。

4 2 3 1
RUDL
-1 -1
1 0

Yes

5 2 1 5
LDRLD
0 0
-1 -1

No

提示

$1\leq N,M,H,K\leq 2\times 10^5$ $S$ 是一个长度为 $N$ 的字符串，由 $R$、$L$、$U$、$D$ 组成。 $|x_i|,|y_i| \leq 2\times 10^5$ $(x_i, y_i)$ 两两互不相同。 输入中的所有数值均为整数，$S$ 除外。最开始，高桥的生命值为 $3$。下面描述各步移动。

第 $1$ 步：$S_i$ 为 $R$，所以他移动到点 $(1,0)$。他的生命值减为 $2$。尽管在点 $(1,0)$ 有一个道具，但他没有使用它，因为他的生命值不小于 $K=1$。

第 $2$ 步：$S_i$ 为 $U$，所以他移动到点 $(1,1)$。他的生命值减为 $1$。

第 $3$ 步：$S_i$ 为 $D$，所以他移动到点 $(1,0)$。他的生命值减为 $0$。点 $(1,0)$ 有一个道具，且他的生命值小于 $K=1$，所以他使用了该道具使生命值变为 $1$。

第 $4$ 步：$S_i$ 为 $L$，所以他移动到点 $(0,0)$。他的生命值减为 $0$。

因此，他可以完成这 $4$ 步而不倒下，所以应输出 $Yes$。注意生命值可以达到 $0$。
最开始，高桥的生命值为 $1$。下面描述各步移动。

第 $1$ 步：$S_i$ 为 $L$，所以他移动到点 $(-1,0)$。他的生命值减为 $0$。

第 $2$ 步：$S_i$ 为 $D$，所以他移动到点 $(-1,-1)$。他的生命值减为 $-1$。现在生命值为 $-1$，他倒下并停止移动。

因此，他会被击倒，所以应输出 $No$。注意尽管初始点 $(0,0)$ 处有一个道具，他在第 $1$ 步之前不会使用它，因为道具仅在移动后被使用。

标签: AtCoder|abc303C

来源

AtCoder|abc303C