Problem:


Score : 600 points

Problem Statement

We have a rectangular grid of squares with H horizontal rows and W vertical columns. Let (i,j) denote the square at the i-th row from the top and the j-th column from the left.
On this grid, there is a piece, which is initially placed at square (s_r,s_c).

Takahashi and Aoki will play a game, where each player has a string of length N.
Takahashi's string is S, and Aoki's string is T. S and T both consist of four kinds of letters: L, R, U and D.

The game consists of N steps. The i-th step proceeds as follows:

First, Takahashi performs a move. He either moves the piece in the direction of S_i, or does not move the piece.

Second, Aoki performs a move. He either moves the piece in the direction of T_i, or does not move the piece.

Here, to move the piece in the direction of L, R, U and D, is to move the piece from square (r,c) to square (r,c-1), (r,c+1), (r-1,c) and (r+1,c), respectively. If the destination square does not exist, the piece is removed from the grid, and the game ends, even if less than N steps are done.

Takahashi wants to remove the piece from the grid in one of the N steps.
Aoki, on the other hand, wants to finish the N steps with the piece remaining on the grid.
Determine if the piece will remain on the grid at the end of the game when both players play optimally.

Constraints

2 \leq H,W \leq 2 \times 10^5

2 \leq N \leq 2 \times 10^5

1 \leq s_r \leq H

1 \leq s_c \leq W

|S|=|T|=N

S and T consists of the four kinds of letters L, R, U and D.

Input

Input is given from Standard Input in the following format:

H W N
s_r s_c
S
T

Output

If the piece will remain on the grid at the end of the game, print YES; otherwise, print NO.

Sample Input 1

2 3 3
2 2
RRL
LUD

Sample Output 1

YES

Here is one possible progress of the game:

Takahashi moves the piece right. The piece is now at (2,3).

Aoki moves the piece left. The piece is now at (2,2).

Takahashi does not move the piece. The piece remains at (2,2).

Aoki moves the piece up. The piece is now at (1,2).

Takahashi moves the piece left. The piece is now at (1,1).

Aoki does not move the piece. The piece remains at (1,1).

Sample Input 2

4 3 5
2 2
UDRRR
LLDUD

Sample Output 2

NO

Sample Input 3

5 6 11
2 1
RLDRRUDDLRL
URRDRLLDLRD

Sample Output 3

NO



Sample input:
2 3 3
2 2
RRL
LUD


Sample output:
YES

Submission status: Time Limit Exceeded

Solution code:
from _collections import deque
from _ast import Num


def parser():
    while 1:
        data = list(input().split(' '))
        for number in data:
            if len(number) > 0:
                yield (number)


input_parser = parser()


def gw():
    global input_parser
    return next(input_parser)


def gi():
    data = gw()
    return int(data)


MOD = int(1e9 + 7)

import numpy
from collections import deque
from math import sqrt
from math import floor
# https://atcoder.jp/contests/agc033/tasks/agc033_b
# B - LRUD Game
"""
"""
H = gi()
W = gi()
N = gi()
sr = gi()
sc = gi()
S = gw()
T = gw()
d_to_i = {"L": 0, "R": 1, "U": 2, "D": 3}
cnt = [[0 for x in range(4)] for i in range(2)]


def o(pos, si, ti, d, sb, tb):
    for i in range(N):
        if (d_to_i[S[i]] == si):
            pos += d
            if pos == sb:
                return 1
        if (d_to_i[T[i]] == ti):
            if (pos - d != tb):
                pos -= d
    return 0


off = 0
for i in range(N):
    #  print(cnt)
    off = o(sc, 0, 1, -1, 0, W + 1)
    off = off or o(sc, 1, 0, 1, W + 1, 0)
    off = off or o(sr, 2, 3, -1, 0, H + 1)
    off = off or o(sr, 3, 2, 1, H + 1, 0)

if off:
    print("NO")
else:
    print("YES")

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 9)

input = sys.stdin.readline

H, W, N = map(int, input().split())
sr, sc = map(int, input().split())
sr -= 1
sc -= 1

s = input()
t = input()

d = {
    'L': (0, -1),
    'R': (0, 1),
    'U': (-1, 0),
    'D': (1, 0)
}

memo = dict()


def next_move_pos(cur_r, cur_c, cur_step_index, bl_is_takahashi):
    if bl_is_takahashi:
        c = s[cur_step_index]
    else:
        c = t[cur_step_index]
    dr, dc = d[c]
    return cur_r + dr, cur_c + dc


def is_in_range(r, c):
    return 0 <= r < H and 0 <= c < W


def rec(cur_r, cur_c, cur_step_index, bl_cur_player_takahashi):
    if memo.get((cur_r, cur_c, cur_step_index, bl_cur_player_takahashi), None):
        return memo[(cur_r, cur_c, cur_step_index, bl_cur_player_takahashi)]

    if bl_cur_player_takahashi:
        nr, nc = next_move_pos(cur_r, cur_c, cur_step_index, True)
        if not is_in_range(nr, nc):
            memo[(cur_r, cur_c, cur_step_index, bl_cur_player_takahashi)] = True
            return True
        if rec(nr, nc, cur_step_index, not bl_cur_player_takahashi):
            memo[(cur_r, cur_c, cur_step_index, bl_cur_player_takahashi)] = True
            return True
        if rec(cur_r, cur_c, cur_step_index, not bl_cur_player_takahashi):
            memo[(cur_r, cur_c, cur_step_index, bl_cur_player_takahashi)] = True
            return True
    else:
        if cur_step_index == N - 1:
            memo[(cur_r, cur_c, cur_step_index, bl_cur_player_takahashi)] = False
            return False
        for nr, nc in (cur_r, cur_c), next_move_pos(cur_r, cur_c, cur_step_index, False):
            if not is_in_range(nr, nc): continue
            nnr, nnc = next_move_pos(nr, nc, cur_step_index + 1, True)
            if not is_in_range(nnr, nnc): continue
            if not rec(nr, nc, cur_step_index + 1, not bl_cur_player_takahashi):
                memo[(cur_r, cur_c, cur_step_index, bl_cur_player_takahashi)] = False
                return False
            if not rec(cur_r, cur_c, cur_step_index + 1, not bl_cur_player_takahashi):
                memo[(cur_r, cur_c, cur_step_index, bl_cur_player_takahashi)] = False
                return False
        memo[(cur_r, cur_c, cur_step_index, bl_cur_player_takahashi)] = True
        return True


print('NO' if rec(sr, sc, 0, True) else 'YES')

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

H, W, N = map(int, input().split())
si, sj = map(int, input().split())
si, sj = si - 1, sj - 1

S = input()
T = input()

# (1-based turn, 0:vertical | 1:horizontal, 0:minDiff | 1:exclusiveMaxDiff)
S_bounds = np.full((N + 1, 2, 2), 0, dtype=np.int)
T_bounds = np.full((N + 1, 2, 2), 0, dtype=np.int)

VERTICAL = 0
HORIZONTAL = 1
MIN_DIFF = 0
MAX_DIFF = 1

T_bounds[0, VERTICAL, :] = si
T_bounds[0, HORIZONTAL, :] = sj

piece_remaining = True

for t in range(N):
	S_bounds[t+1] = T_bounds[t]
	if S[t] == 'U':
		S_bounds[t+1, VERTICAL, MIN_DIFF] -= 1
	elif S[t] == 'D':
		S_bounds[t+1, VERTICAL, MAX_DIFF] += 1
	elif S[t] == 'L':
		S_bounds[t+1, HORIZONTAL, MIN_DIFF] -= 1
	elif S[t] == 'R':
		S_bounds[t+1, HORIZONTAL, MAX_DIFF] += 1
	
	min_i = S_bounds[t+1, VERTICAL, MIN_DIFF]
	max_i = S_bounds[t+1, VERTICAL, MAX_DIFF]
	min_j = S_bounds[t+1, HORIZONTAL, MIN_DIFF]
	max_j = S_bounds[t+1, HORIZONTAL, MAX_DIFF]

	if min_i < 0 or H <= max_i or min_j < 0 or W <= max_j:
		piece_remaining = False
		break

	T_bounds[t+1] = S_bounds[t+1]
	if T[t] == 'U':
		T_bounds[t+1, VERTICAL, MAX_DIFF] = max(0, S_bounds[t+1, VERTICAL, MAX_DIFF] - 1)
	elif T[t] == 'D':
		T_bounds[t+1, VERTICAL, MIN_DIFF] = min(H - 1, S_bounds[t+1, VERTICAL, MIN_DIFF] + 1)
	elif T[t] == 'L':
		T_bounds[t+1, HORIZONTAL, MAX_DIFF] = max(0, S_bounds[t+1, HORIZONTAL, MAX_DIFF] - 1)
	elif T[t] == 'R':
		T_bounds[t+1, HORIZONTAL, MIN_DIFF] = min(W - 1, S_bounds[t+1, HORIZONTAL, MIN_DIFF] + 1)

	min_i = T_bounds[t+1, VERTICAL, MIN_DIFF]
	max_i = T_bounds[t+1, VERTICAL, MAX_DIFF]
	min_j = T_bounds[t+1, HORIZONTAL, MIN_DIFF]
	max_j = T_bounds[t+1, HORIZONTAL, MAX_DIFF]

print('YES' if piece_remaining else 'NO')

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 9)

input = sys.stdin.readline

H, W, N = map(int, input().split())
sr, sc = map(int, input().split())
sr -= 1
sc -= 1

s = input()
t = input()

d = {
    'L': (0, -1),
    'R': (0, 1),
    'U': (-1, 0),
    'D': (1, 0)
}


def next_move_pos(cur_r, cur_c, cur_step_index, bl_is_takahashi):
    if bl_is_takahashi:
        c = s[cur_step_index]
    else:
        c = t[cur_step_index]
    dr, dc = d[c]
    return cur_r + dr, cur_c + dc


def is_in_range(r, c):
    return 0 <= r < H and 0 <= c < W


def rec(cur_r, cur_c, cur_step_index, bl_cur_player_takahashi):
    if bl_cur_player_takahashi:
        nr, nc = next_move_pos(cur_r, cur_c, cur_step_index, True)
        if not is_in_range(nr, nc):
            return True
        if rec(nr, nc, cur_step_index, not bl_cur_player_takahashi):
            return True
        if rec(cur_r, cur_c, cur_step_index, not bl_cur_player_takahashi):
            return True
    else:
        if cur_step_index == N - 1:
            return False
        for nr, nc in (cur_r, cur_c), next_move_pos(cur_r, cur_c, cur_step_index, False):
            if not is_in_range(nr, nc): continue
            nnr, nnc = next_move_pos(nr, nc, cur_step_index + 1, True)
            if not is_in_range(nnr, nnc): continue
            if not rec(nr, nc, cur_step_index + 1, not bl_cur_player_takahashi):
                return False
            if not rec(cur_r, cur_c, cur_step_index + 1, not bl_cur_player_takahashi):
                return False
        return True


print('NO' if rec(sr, sc, 0, True) else 'YES')

Submission status: Accepted

Solution code:
def is_keepable(size, sub, add, start):
    small, big = 1, size
    for i in range(N - 1, -1, -1):
        if T[i] == sub:
            big = min(big + 1, size)
        elif T[i] == add:
            small = max(small - 1, 1)
        if S[i] == sub:
            small += 1
        elif S[i] == add:
            big -= 1
        if small > big:
            return False
    return small <= start <= big


H, W, N = map(int, input().split())
sr, sc = map(int, input().split())
S = input()
T = input()
if is_keepable(H, "U", "D", sr) and is_keepable(W, "L", "R", sc):
    print("YES")
else:
    print("NO")

Submission status: Accepted

Solution code:
H, W, N = map(int, input().split())
sr, sc = map(int, input().split())
S = input()[::-1]
T = input()[::-1]
l = u = 1
r = W
d = H
for s, t in zip(S,T):
    if t == "U":
        d = min(d + 1, H)
    elif t == "D":
        u = max(1, u - 1)
    elif t == "R":
        l = max(1, l - 1)
    else:
        r = min(r + 1, W)


    if s == "U":
        u += 1
    elif s == "D":
        d -= 1
    elif s == "R":
        r -= 1
    else:
        l += 1
    if l > r or u > d or l > W or r < 1 or u > H or d < 1:
        print("NO")
        break
else:
    if u <= sr <= d and l <= sc <= r:
        print("YES")
    else:
        print("NO")

Submission status: Accepted

Solution code:
H, W, N = map(int, input().split())
*s, = map(lambda x: int(x) - 1, input().split())
S = input()
T = input()
l = t = 0
b = H
r = W
if S[-1] == 'L':
    l += 1
elif S[-1] == 'R':
    r -= 1
elif S[-1] == 'U':
    t += 1
else:
    b -= 1

for i in range(N - 2, -1, -1):
    a = T[i]
    if a == 'L':
        r += 1
        r = min(r, W)
    elif a == 'R':
        l -= 1
        l = max(l, 0)
    elif a == 'U':
        b += 1
        b = min(b, H)
    else:
        t -= 1
        t = max(t, 0)
    a = S[i]
    if a == 'L':
        l += 1
    elif a == 'R':
        r -= 1
    elif a == 'U':
        t += 1
    else:
        b -= 1
    if b <= t or r <= l:
        print('NO')
        exit()

print('YES' if t <= s[0] < b and l <= s[1] < r else 'NO')

Submission status: Accepted

Solution code:
H,W,N = map(int, input().split())
y,x = map(int, input().split())
S = input()
T = input()

y,x = y-1, x-1
xmin, xmax, ymin, ymax = 0,W-1, 0,H-1
S = S[::-1]
T = T[::-1]

d = {
  'L': (1,0),
  'R': (-1,0),
  'U': (0,1),
  'D': (0,-1),
}
 
for i in range(N):
  dx,dy = d[T[i]]
  xmin = xmin + dx if dx < 0 else xmin
  xmax = xmax + dx if dx > 0 else xmax
  ymin = ymin + dy if dy < 0 else ymin
  ymax = ymax + dy if dy > 0 else ymax

  if xmin < 0: xmin = 0
  if xmax >= W: xmax = W-1
  if ymin < 0: ymin = 0
  if ymax >= H: ymax = H-1

  dx,dy = d[S[i]]
  xmin = xmin + dx if dx > 0 else xmin
  xmax = xmax + dx if dx < 0 else xmax
  ymin = ymin + dy if dy > 0 else ymin
  ymax = ymax + dy if dy < 0 else ymax
  
  #print(i,xmin,xmax,ymin,ymax)
  if xmin > xmax or ymin > ymax:
    print("NO")
    #print(xmin,x,xmax)
    #print(ymin,y,ymax)
    exit(0)

if xmin <= x <= xmax and ymin <= y <= ymax:
  print("YES")
else:
  print("NO")
#print(xmin,x,xmax)
#print(ymin,y,ymax)

Submission status: Accepted

Solution code:
h,w,n=map(int,input().split())
x,y=map(lambda x:int(x)-1,input().split())
s=input()
t=input()

d=[0,h-1,0,w-1]
f=True
for i in range(n-1,-1,-1):
  if t[i]=="D":
    d[0]=max(d[0]-1,0)
  if t[i]=="U":
    d[1]=min(d[1]+1,h-1)
  if t[i]=="R":
    d[2]=max(d[2]-1,0)
  if t[i]=="L":
    d[3]=min(d[3]+1,w-1)
  
  
  if s[i]=="U":
    d[0]+=1
  if s[i]=="D":
    d[1]-=1
  if s[i]=="L":
    d[2]+=1
  if s[i]=="R":
    d[3]-=1
  if d[0]>d[1] or d[2]>d[3]:
    f=False
    break

if f and d[0]<=x and x<=d[1] and d[2]<=y and y<=d[3]:
  print("YES")
else:
  print("NO")

Submission status: Accepted

Solution code:
h,w,n = map(int,input().split())
y,x = map(int,input().split())
s = input()[::-1]
t = input()[::-1]

r = w
l = 1
d = h
u = 1

for i in range(n):
    
    if t[i] == "R":
        l = max(1,l-1)
    elif t[i] == "L":
        r = min(w,r+1)
    elif t[i] == "D":
        u = max(1,u-1)
    else:
        d = min(h,d+1)
    if s[i] == "R":
        r -= 1
    elif s[i] == "L":
        l += 1
    elif s[i] == "D":
        d -= 1
    else:
        u += 1
    if r < l or d < u:
        print("NO")
        exit()

if l <= x <= r and u <= y <= d:
    print("YES")
else:
    print("NO")

Submission status: Accepted

Solution code:
import functools
import sys
from collections import deque
import bisect
import copy
import heapq
import itertools
import math
import random
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


H, W, N = read_values()
YP, XP = read_index()
S = input().strip()
T = input().strip()


def main():
    X = [0, W]
    Y = [0, H]
    for t, s in zip(T[::-1], S[::-1]):
        if t == "L":
            X[1] = min(W, X[1] + 1)
        elif t == "R":
            X[0] = max(0, X[0] - 1)
        elif t == "U":
            Y[1] = min(H, Y[1] + 1)
        elif t == "D":
            Y[0] = max(0, Y[0] - 1)

        if s == "L":
            X[0] += 1
        elif s == "R":
            X[1] -= 1
        elif s == "U":
            Y[0] += 1
        elif s == "D":
            Y[1] -= 1

        if X[0] >= X[1] or Y[0] >= Y[1]:
            print("NO")
            return

    if X[0] <= XP < X[1] and Y[0] <= YP < Y[1]:
        print("YES")
    else:
        print("NO")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return float(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()


def main():
	h,w,n=MI()
	sr,sc=MI()
	S=RD()
	T=RD()

	ans="YES"

	#Rの検証
	x=w-sc+1
	for i,j in zip(S,T):
		if i=="R":
			x-=1
			if x==0:
				ans="NO"
		if j=="L":
			if x<w:
				x+=1

	#Lの検証
	x=sc
	for i,j in zip(S,T):
		if i=="L":
			x-=1
			if x==0:
				ans="NO"
		if j=="R":
			if x<w:
				x+=1

	#Dの検証
	x=h-sr+1
	for i,j in zip(S,T):
		if i=="D":
			x-=1
			if x==0:
				ans="NO"
		if j=="U":
			if x<h:
				x+=1

	#Uの検証
	x=sr
	for i,j in zip(S,T):
		if i=="U":
			x-=1
			if x==0:
				ans="NO"
		if j=="D":
			if x<h:
				x+=1

	print(ans)










if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
h,w,n=map(int,input().split())
sh,sw=map(int,input().split())
s=input()
t=input()
r='RLDU'
q='LRUD'
p=dict(zip(r,[w-sw+1,sw,h-sh+1,sh]))
ds=dict(zip(r,[0]*4))
dt=dict(zip(r,[0]*4))
for i,j in zip(s,t):
  ds[i]+=1
  for k,l in zip(r,q):
    if ds[k]-dt[l]>=p[k]:
      print('NO')
      exit()
  dt[j]+=1
  for k in r:
    dt[k]=min(dt[k],p[k]+ds[k]-1)
print('YES')

Submission status: Accepted

Solution code:
h,w,n = map(int,input().split())
sr,sc = map(int,input().split())
s = input()
t = input()
fl = True

#右
cur = sc
for i in range(n):
    if s[i] == "R":
        cur += 1
    if cur > w:
        fl = False
    if t[i] == "L" and cur > 2:
        cur -= 1
        
#左
cur = sc
for i in range(n):
    if s[i] == "L":
        cur -= 1
    if cur <= 0:
        fl = False
    if t[i] == "R" and cur < w:
        cur += 1
        
#上
cur = sr
for i in range(n):
    if s[i] == "U":
        cur -= 1
    if cur <= 0:
        fl = False
    if t[i] == "D" and cur < h:
        cur += 1
        
#下
cur = sr
for i in range(n):
    if s[i] == "D":
        cur += 1
    if cur > h:
        fl = False
    if t[i] == "U" and cur > 2:
        cur -= 1
        
if fl:
    print("YES")
else:
    print("NO")

Submission status: Accepted

Solution code:
H, W, N = map(int, input().split())
x, y = map(int, input().split())
S = input().rstrip()
T = input().rstrip()
L, R, U, D = 1, W, 1, H
for s, t in zip(reversed(S),reversed(T)):
    if t=="L": R = min(R+1,W)
    if t=="R": L = max(L-1,1)
    if t=="U": D = min(D+1,H)
    if t=="D": U = max(U-1,1)
    if s=="L": L = L+1
    if s=="R": R = R-1
    if s=="U": U = U+1
    if s=="D": D = D-1
    if L>R or U>D:
        print("NO")
        exit()
if L<=y<=R and U<=x<=D:
    print("YES")
else:
    print("NO")

Submission status: Accepted

Solution code:

max2 = lambda x,y: x if x > y else y
min2 = lambda x,y: x if x < y else y

def solve(H,W,start,S,T):
    limit = [W,H]
    offsets = [0]*4

    for s,t in zip(reversed(S),reversed(T)):
        offsets[t^1] = max2(offsets[t^1]-1,0)
        offsets[s] += 1
        if offsets[s]+offsets[s^1] >= limit[s//2]:
            return False
    h,w = start
    l,r,u,d = offsets
    return l <= w < W-r and u <= h < H-d



if __name__ == '__main__':
    H,W,N = map(int,input().split())
    start = tuple(map(lambda x: int(x)-1,input().split()))

    d = {'L':0,'R':1,'U':2,'D':3}

    S = tuple(d[c] for c in input())
    T = tuple(d[c] for c in input())


    print('YES' if solve(H,W,start,S,T) else 'NO')

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    h, w, n = map(int, readline().split())
    sr, sc = map(int, readline().split())
    s = input()
    t = input()

    c = dict()
    c["L"], c["R"] = sc, sc
    c["U"], c["D"] = sr, sr

    for first, second in zip(s, t):
        if first == "L" or first == "U":
            c[first] -= 1
        else:
            c[first] += 1

        if c["L"] == 0 or c["R"] == w + 1 or c["U"] == 0 or c["D"] == h + 1:
            return print("NO")

        if second == "L":
            c["R"] -= 1
            c["R"] = max(1, c["R"])
        if second == "R":
            c["L"] += 1
            c["L"] = min(w, c["L"])
        if second == "U":
            c["D"] -= 1
            c["D"] = max(1, c["D"])
        if second == "D":
            c["U"] += 1
            c["U"] = min(h, c["U"])

    print("YES")


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import *

H, W, N = map(int, input().split())
sr, sc = map(int, input().split())
S = input()[:-1]
T = input()[:-1]
U, D, L, R = 0, H-1, 0, W-1

for i in range(N-1, -1, -1):
    if T[i]=='U':
        D = min(H-1, D+1)
    elif T[i]=='D':
        U = max(0, U-1)
    elif T[i]=='L':
        R = min(W-1, R+1)
    else:
        L = max(0, L-1)
    
    if S[i]=='U':
        U += 1
    elif S[i]=='D':
        D -= 1
    elif S[i]=='L':
        L += 1
    else:
        R -= 1
    
    if U>D or L>R:
        print('NO')
        exit()

if U<=sr-1<=D and L<=sc-1<=R:
    print('YES')
else:
    print('NO')

Submission status: Accepted

Solution code:
def main():
    H, W, N = list(map(int, input().split()))
    sr, sc = list(map(lambda x: int(x) - 1, input().split()))
    S = input()
    T = input()
    # 後手が勝つ領域を後ろから順にさかのぼっていく
    ok_left, ok_right = 0, W - 1
    ok_up, ok_down = 0, H - 1
    for n in range(N - 1, -1, -1):
        s = S[n]
        if s == 'L':
            ok_left += 1
        if s == 'R':
            ok_right -= 1
        if s == 'U':
            ok_up += 1
        if s == 'D':
            ok_down -= 1
        if ok_left > ok_right or ok_up > ok_down:
            print('NO')
            return
        if n > 0:
            t = T[n - 1]
            if t == 'L':
                ok_right = min(ok_right + 1, W - 1)
            if t == 'R':
                ok_left = max(ok_left - 1, 0)
            if t == 'U':
                ok_down = min(ok_down + 1, H - 1)
            if t == 'D':
                ok_up = max(ok_up - 1, 0)
    if ok_left <= sc <= ok_right and ok_up <= sr <= ok_down:
        print('YES')
    else:
        print('NO')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    H, W, n = map(int, input().split())
    sr, sc = map(int, input().split())
    S = input()[::-1]
    T = input()[::-1]

    left, right = 1, W
    bottom, up = 1, H
    for s, t in zip(S, T):
        if t == "R":
            left -= 1
            left = max(1, left)
        elif t == "L":
            right += 1
            right = min(W, right)
        elif t == "U":
            bottom -= 1
            bottom = max(1, bottom)
        else:
            up += 1
            up = min(H, up)

        if s == "R":
            right -= 1
        elif s == "L":
            left += 1
        elif s == "U":
            up -= 1
        else:
            bottom += 1

        if left > right or bottom > up:
            print("NO")
            break
    else:
        print("YES" if left <= sc <= right and bottom <= H - sr + 1 <= up else "NO")


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
h, w, n = map(int, input().split())
sr, sc = map(int, input().split())
s = input()
t = input()
ll = rr = sc
uu = dd = sr
for ss, tt in zip(s, t):
    if ss == "L":
        ll -= 1
        if ll == 0:
            print("NO")
            exit()
    elif ss == "R":
        rr += 1
        if rr == w + 1:
            print("NO")
            exit()
    elif ss == "U":
        uu -= 1
        if uu == 0:
            print("NO")
            exit()
    else:
        dd += 1
        if dd == h + 1:
            print("NO")
            exit()
            
    if tt == "L":
        rr -= 1
        rr = max(rr, 1)
    elif tt == "R":
        ll += 1
        ll = min(ll, w)
    elif tt == "U":
        dd -= 1
        dd = max(dd, 1)
    else:
        uu += 1
        uu = min(uu, h)
print("YES")

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def main():

    H, W, N = in_nn()
    sy, sx = in_nn()
    S = in_s()
    T = in_s()

    # left
    now_x = sx
    for i in range(N):
        if S[i] == 'L':
            now_x -= 1
        if now_x == 0:
            print('NO')
            exit()
        if T[i] == 'R' and now_x < W:
            now_x += 1

    # right
    now_x = sx
    for i in range(N):
        if S[i] == 'R':
            now_x += 1
        if now_x == W + 1:
            print('NO')
            exit()
        if T[i] == 'L' and now_x > 1:
            now_x -= 1

    # up
    now_y = sy
    for i in range(N):
        if S[i] == 'U':
            now_y -= 1
        if now_y == 0:
            print('NO')
            exit()
        if T[i] == 'D' and now_y < H:
            now_y += 1

    # down
    now_y = sy
    for i in range(N):
        if S[i] == 'D':
            now_y += 1
        if now_y == H + 1:
            print('NO')
            exit()
        if T[i] == 'U' and now_y > 1:
            now_y -= 1

    print('YES')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import re
import math
import collections
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))


# ===CODE===

def main():
    h, w, n = ns()
    y, x = ns()
    s = list(input())
    t = list(input())

    su, sd, sl, sr = 0, 0, 0, 0
    tu, td, tl, tr = 0, 0, 0, 0

    yes = True

    for si, ti in zip(s, t):
        if si == "U":
            su += 1
        elif si == "D":
            sd += 1
        elif si == "L":
            sl += 1
        else:
            sr += 1

        if y - (su - td) < 1:
            yes = False
        if y + sd - tu > h:
            yes = False
        if x - (sl - tr) < 1:
            yes = False
        if x + sr - tl > w:
            yes = False

        if ti == "U":
            tu = min(tu + 1, y - 1 + sd)
        elif ti == "D":
            td = min(td + 1, h - y + su)
        elif ti == "L":
            tl = min(tl + 1, x - 1 + sr)
        else:
            tr = min(tr + 1, w - x + sl)

    print("YES" if yes else "NO")


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
h , w , n = map(int,input().split())
sr , sc = map(int,input().split())
s = input()
t = input()
scou = [0,0,0,0] 
tcou = [0,0,0,0]
hou = {"L":0,"R":1,"U":2,"D":3}
for i in range(n):
    scou[hou[s[i]]] += 1
    if sc - scou[0] + tcou[1] <= 0:
        print("NO")
        exit()
    if sc + scou[1] - tcou[0] >= w + 1:
        print("NO")
        exit()
    if sr - scou[2] + tcou[3] <= 0:
        print("NO")
        exit()
    if sr + scou[3] - tcou[2] >= h + 1:
        print("NO")
        exit()
    
    tcou[hou[t[i]]] += 1
    if sc - tcou[0] + scou[1] <= 0:
        tcou[0] -= 1
    if sc + tcou[1] - scou[0] >= w+1:
        tcou[1] -= 1
    if sr - tcou[2] + scou[3] <= 0:
        tcou[2] -= 1
    if sr + tcou[3] - scou[2] >= h+1:
        tcou[3] -= 1

print("YES")

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    H, W, N = map(int, input().split())
    sr, sc = map(int, input().split())
    sr = H + 1 - sr
    S = input()[::-1]
    T = input()[::-1]

    left, right = 1, W
    bottom, up = 1, H
    for s, t in zip(S, T):
        if t == "R":
            left -= 1
            left = max(1, left)
        elif t == "L":
            right += 1
            right = min(W, right)
        elif t == "U":
            bottom -= 1
            bottom = max(1, bottom)
        elif t == "D":
            up += 1
            up = min(H, up)

        if s == "R":
            right -= 1
        elif s == "L":
            left += 1
        elif s == "U":
            up -= 1
        elif s == "D":
            bottom += 1

        if left > right or bottom > up:
            print("NO")
            exit()

    print("YES" if left <= sc <= right and bottom <= sr <= up else "NO")


if __name__ == '__main__':
    resolve()