Problem:


Score : 500 points

Problem Statement

A robot is put at the origin in a two-dimensional plane.
Initially, the robot is facing in the positive x-axis direction.

This robot will be given an instruction sequence s.
s consists of the following two kinds of letters, and will be executed in order from front to back.

F : Move in the current direction by distance 1.

T : Turn 90 degrees, either clockwise or counterclockwise.

The objective of the robot is to be at coordinates (x, y) after all the instructions are executed.
Determine whether this objective is achievable.

Constraints

s consists of F and T.

1 \leq |s| \leq 8 000

x and y are integers.

|x|, |y| \leq |s|

Input

Input is given from Standard Input in the following format:

s
x y

Output

If the objective is achievable, print Yes; if it is not, print No.

Sample Input 1

FTFFTFFF
4 2

Sample Output 1

Yes

The objective can be achieved by, for example, turning counterclockwise in the first T and turning clockwise in the second T.

Sample Input 2

FTFFTFFF
-2 -2

Sample Output 2

Yes

The objective can be achieved by, for example, turning clockwise in the first T and turning clockwise in the second T.

Sample Input 3

FF
1 0

Sample Output 3

No

Sample Input 4

TF
1 0

Sample Output 4

No

Sample Input 5

FFTTFF
0 0

Sample Output 5

Yes

The objective can be achieved by, for example, turning counterclockwise in the first T and turning counterclockwise in the second T.

Sample Input 6

TTTT
1 0

Sample Output 6

No



Sample input:
FTFFTFFF
4 2


Sample output:
Yes

Submission status: Time Limit Exceeded

Solution code:
s = list(input())
x, y = map(int, input().split())
import copy
N = len(s)
cur = [[1,0,0,0]]
ans = 'No'
for i in range(N):
  M = len(cur)
  for j in range(M):
    if s[i] == 'F':
      cur[j][2] += cur[j][0]
      cur[j][3] += cur[j][1]
      if i == N-1 and cur[j][2] == x and cur[j][3] == y:
        ans = 'Yes'
    elif cur[j][0] == 0:
      b = copy.copy(cur[j])
      cur[j][0] = 1
      cur[j][1] = 0
      b[0] = -1
      b[1] = 0
      cur.append(b)
      if i == N-1 and cur[j][2] == x and cur[j][3] == y:
        ans = 'Yes'
    else:
      b = copy.copy(cur[j])
      cur[j][0] = 0
      cur[j][1] = 1
      b[0] = 0
      b[1] = -1
      cur.append(b)
      if i == N-1 and cur[j][2] == x and cur[j][3] == y:
        ans = 'Yes'

print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = list(input())
x, y = map(int, input().split())
import copy
N = len(s)
cur = [[1,0,0,0]]
for i in range(N):
  M = len(cur)
  for j in range(M):
    if s[i] == 'F':
      cur[j][2] += cur[j][0]
      cur[j][3] += cur[j][1]
    elif cur[j][0] == 0:
      b = copy.copy(cur[j])
      cur[j][0] = 1
      cur[j][1] = 0
      b[0] = -1
      b[1] = 0
      cur.append(b)
    else:
      b = copy.copy(cur[j])
      cur[j][0] = 0
      cur[j][1] = 1
      b[0] = 0
      b[1] = -1
      cur.append(b)
n = len(cur)
ans = 'No'
for i in range(n):
  if cur[i][2] == x and cur[i][3] == y:
    ans = 'Yes'
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools


def parse(s):
    first_val = None
    verticals, horizontals = list(), list()
    seq = 0
    is_horizontal = True
    is_first = True
    for c in s:
        if c == 'T':
            if is_first:
                first_val = seq
                is_first = False
            elif is_horizontal:
                horizontals.append(seq)
            else:
                verticals.append(seq)
            is_horizontal = not is_horizontal
            seq = 0
        else:
            seq += 1
    if seq > 0:
        if is_first:
            first_val = seq
        elif is_horizontal:
            horizontals.append(seq)
        else:
            verticals.append(seq)
    return first_val, verticals, horizontals


def check(vals, target):
    vals.append(target)
    N = len(vals)
    for signs in itertools.product([-1, 1], repeat=N):
        if 0 == sum([s * v for s, v in zip(signs, vals)]):
            return True
    return False


def main():
    S = input()
    X, Y = list(map(int, input().split(' ')))
    fv, vs, hs = parse(S)
    if check(hs, X - fv) and check(vs, Y):
        print('Yes')
    else:
        print('No')


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc082/tasks/arc087_b


def run_length_encoding(s):
    '''
    連長圧縮を行う
    s ... iterable object e.g. list, str
    return
    ----------
    s_composed,s_num,s_idx
    それぞれ、圧縮後の文字列、その文字数、その文字が始まるidx
    '''
    s_composed = []
    s_sum = []
    s_idx = [0]
    pre = s[0]
    cnt = 1
    for i, ss in enumerate(s[1:], start=1):
        if pre == ss:
            cnt += 1
        else:
            s_sum.append(cnt)
            s_composed.append(pre)
            s_idx.append(i)
            cnt = 1
            pre = ss
    s_sum.append(cnt)
    s_composed.append(pre)
    # assert len(s_sum) == len(s_composed)
    return s_composed, s_sum, s_idx

# データに関しては事前にランレングス圧縮しておくと楽かもね


s = input()
x, y = map(int, input().split())
s_composed, s_sum, _ = run_length_encoding(s)

if s_composed[0] == 'T':  # 必ずTから始まるようにしたい
    s_composed.insert(0, 'F')
    s_sum.insert(0, 0)
# 前処理 xの移動履歴とyの移動履歴を作る
is_x = True
hist_x = []
hist_y = []
for s, n in zip(s_composed, s_sum):
    if s == 'T':
        if n & 1:  # xyの状態を反転させる
            is_x = not is_x
    else:
        if is_x:
            hist_x.append(n)
        else:
            hist_y.append(n)

'''
dpx[i][j]...x座標がjであることが可能か？ x方向の移動についてi回目の移動のあとに。
dpy[i][j]...y座標がjであることが可能か？ y方向の移動についてi回目の移動のあとに。

更新則
xについての移動,距離d移動するとすると
dpx[i+1][j+d]=dpx[i+1][j+d] or dpx[i][j]
dpx[i+1][j-d]=dpx[i+1][j-d] or dpx[i][j]
(配るDP)で更新すると楽かな？
yも同様

初期条件
dpx[:][:]=False
dpx[0][d_x0]=True #xの0回目の移動。

dpy[:][:] = False
dpy[0][d_y0]=True 簡単のために
dpy[0][-d_y0]=True
'''

if hist_x:
    # x_range = 2 * max(1, sum(hist_x))  # ここが0になるときがある
    x_range = 16002  # ここが0になるときがある
    shift = x_range // 2
    dpx = [[False] * x_range for _ in range(len(hist_x))]
    dpx[0][hist_x[0] + shift] = True
    for i in range(1, len(hist_x)):
        d = hist_x[i]
        for j in range(x_range):
            if j + d < x_range:
                dpx[i][j] = dpx[i][j] or dpx[i - 1][j + d]
            if -1 < j - d:
                dpx[i][j] = dpx[i][j] or dpx[i - 1][j - d]
    ansx = dpx[-1][x + shift]
# else:
#     ansx = x == 0

if hist_y:
    # y_range = 2 * max(1, sum(hist_y))  # ここが0になるときがある
    # print(y_range)
    y_range = 16002  # ここが0になるときがある
    shift = y_range // 2
    dpy = [[False] * y_range for _ in range(len(hist_y))]
    dpy[0][hist_y[0] + shift] = True
    dpy[0][-hist_y[0] + shift] = True
    for i in range(1, len(hist_y)):
        d = hist_y[i]
        for j in range(y_range):
            if j + d < y_range:
                dpy[i][j] = dpy[i][j] or dpy[i - 1][j + d]
            if -1 < j - d:
                dpy[i][j] = dpy[i][j] or dpy[i - 1][j - d]
    ansy = dpy[-1][y + shift]
else:
    ansy = y == 0

print('Yes' if ansx and ansy else 'No')


# print(ansx, ansy)
# print(*dpy, sep='\n')

Submission status: Time Limit Exceeded

Solution code:
s = str(input())
x,y = map(int,input().split())
x_list,y_list = [],[]
l = s.split('T')

for i in range(0,len(l),2):
  x_list.append(len(l[i]))
for i in range(1,len(l),2):
  y_list.append(len(l[i]))

ans_x,ans_y = [],[]

if s[0]=='F':
  ans_x.append(x_list[0])
  x_list=x_list[1:]
else:
  ans_x.append(0)
ans_y.append(0)

for i in x_list:
  ans = []
  for j in ans_x:
    ans.append(i+j)
    ans.append(j-i)
  ans_x = ans
for i in y_list:
  ans = []
  for j in ans_y:
    ans.append(i+j)
    ans.append(j-i)
  ans_y = ans
if x in ans_x and y in ans_y:
  print("Yes")
else:
  print("No")

Submission status: Time Limit Exceeded

Solution code:
s = list(input())
x,y = map(int,input().split())
i = 0
while i < len(s) and s[i] == "F":
    i += 1
    x -= 1

l = []
r = []
check = 1
count = 0
while i < len(s):
    if s[i] == "T":
        if count >0:
            if check == 1:
                l.append(count)
            else:
                r.append(count)
        check *= -1
        count = 0
    else:
        count += 1
    i += 1

if count >0:
    if check == 1:
        l.append(count)
    else:
        r.append(count)       

    
if abs(x) > sum(l) or abs(y) > sum(r):
    print("No")
    exit() 

dpx = [[0]*(sum(l)*2+3) for i in range(len(l)+1)]
lx = sum(l)*2+3
dpx[0][sum(l)] = 1
for i in range(len(l)):
    for j in range(lx):
        if dpx[i][j] == 1:
            dpx[i+1][j+l[i]] = 1
            dpx[i+1][j-l[i]] = 1

dpy = [[0]*(sum(r)*2+3) for i in range(len(r)+1)]
rx = sum(r)*2+3
dpy[0][sum(r)] = 1
for i in range(len(r)):
    for j in range(rx):
        if dpy[i][j] == 1:
            dpy[i+1][j+r[i]] = 1
            dpy[i+1][j-r[i]] = 1
if dpx[-1][sum(l)+x] == 1 and dpy[-1][sum(r)+y] == 1:
    print("Yes")
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
s = input()
x, y = map(int, input().split())
n = len(s)
#dp_x: +, -に向いてて行けるかどうか
dp_x = [[False, False] for i in range(2*n+2)]
dp_y = [[False, False] for i in range(2*n+2)]
dp_x[0][0] = True
dp_y[0][0] = True
dp_y[0][1] = True

flag = 0
for i in range(len(s)):
    if s[i] == "T":
        if flag == 0:
            flag = 2
            for j in range(-n, n+1):
                if dp_x[j][0]:
                    dp_x[j][1] = True

        elif flag == 2:
            flag = 1
            for j in range(-n, n+1):
                dp_x[j][0] = dp_x[j][1] or dp_x[j][0]
                dp_x[j][1] = dp_x[j][1] or dp_x[j][0]

        else:
            flag = 2
            for j in range(-n, n+1):
                dp_y[j][0] = dp_y[j][1] or dp_y[j][0]
                dp_y[j][1] = dp_y[j][1] or dp_y[j][0]


    else:
        if flag == 0:
            for j in range(n, -n-1, -1):
                dp_x[j][0] = dp_x[j-1][0]

        elif flag == 1:
            for j in range(n, -n-1, -1):
                dp_x[j][0] = dp_x[j-1][0]
                dp_x[-j][1] = dp_x[-j+1][1]
        else:
            for j in range(n, -n-1, -1):
                dp_y[j][0] = dp_y[j-1][0]
                dp_y[-j][1] = dp_y[-j+1][1]


if dp_x[x][0] or dp_x[x][1]:
    if dp_y[y][0] or dp_y[y][1]:
        print("Yes")
    else:
        print("No")
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
def main():
    S = input()
    X, Y = map(int, input().split())
    cur = set([(0, 0, 0)])
    D = [(1, 0), (0, -1), (-1, 0), (0, 1)]
    for s in S:
        nxt = set()
        if s == 'F':
            for x, y, d in cur:
                tx, ty = D[d]
                nxt.add((x + tx, y + ty, d))
        else:
            for x, y, d in cur:
                nxt.add((x, y, (d + 1) % 4))
                nxt.add((x, y, (d - 1) % 4))
        cur = nxt
    return any((X, Y, i) in cur for i in range(4))

print('Yes' if main() else 'No')

Submission status: Time Limit Exceeded

Solution code:
import sys
## io ##
def IS(): return sys.stdin.readline().rstrip()
def II(): return int(IS())
def MII(): return list(map(int, IS().split()))
def MIIZ(): return list(map(lambda x: x-1, MII()))
## dp ##
def DD2(d1,d2,init=0): return [[init]*d2 for _ in range(d1)]
def DD3(d1,d2,d3,init=0): return [DD2(d2,d3,init) for _ in range(d1)]
## math ##
MOD=10**9+7
def divc(x,y): return -(-x//y)
def divf(x,y): return x//y
def gcd(x,y):
    while y: x,y = y,x%y
    return x
def lcm(x,y): return x*y//gcd(x,y)
def get_primes(MAX_NUM=10**3):
    """Return a list of prime numbers"""
    is_prime = [True] * MAX_NUM
    is_prime[0] = False
    is_prime[1] = False
    primes = []
    for i in range(MAX_NUM):
        if is_prime[i]:
            primes.append(i)
            for j in range(2*i, MAX_NUM, i):
                is_prime[j] = False
    return primes
## libs ##
from itertools import accumulate as acc
from collections import deque, Counter
from heapq import heapify, heappop, heappush
from bisect import bisect_left
 
#======================================================#
 
def main():
    s = IS()
    x, y = MII()
    n = len(s)
    dpx = DD2(n,10**5,init=False)
    dpy = DD2(n,10**5,init=False)
    ff = s.split('T')
    ffx = [len(f) for f in ff[::2]]
    ffy = [len(f) for f in ff[1::2]]
    nx = len(ffx)
    ny = len(ffy)
    if len(ffx) > 0:
        dpx[0][ffx[0]] = True
        for i in range(1, nx):
            for j in range(-8000, 8001):
                dpx[i][j] = dpx[i-1][j-ffx[i]] or dpx[i-1][j+ffx[i]]
    if len(ffy) > 0:
        dpy[0][ffy[0]] = dpy[0][-ffy[0]]= True
        for i in range(1, ny):
            for j in range(-8000, 8001):
                dpy[i][j] = dpy[i-1][j-ffy[i]] or dpy[i-1][j+ffy[i]]
    if dpx[nx-1][x] and dpy[ny-1][y]: print('Yes')
    else: print('No')

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
## io ##
def IS(): return sys.stdin.readline().rstrip()
def II(): return int(IS())
def MII(): return list(map(int, IS().split()))
def MIIZ(): return list(map(lambda x: x-1, MII()))
## dp ##
def DD2(d1,d2,init=0): return [[init]*d2 for _ in range(d1)]
def DD3(d1,d2,d3,init=0): return [DD2(d2,d3,init) for _ in range(d1)]
## math ##
MOD=10**9+7
def divc(x,y): return -(-x//y)
def divf(x,y): return x//y
def gcd(x,y):
    while y: x,y = y,x%y
    return x
def lcm(x,y): return x*y//gcd(x,y)
def get_primes(MAX_NUM=10**3):
    """Return a list of prime numbers"""
    is_prime = [True] * MAX_NUM
    is_prime[0] = False
    is_prime[1] = False
    primes = []
    for i in range(MAX_NUM):
        if is_prime[i]:
            primes.append(i)
            for j in range(2*i, MAX_NUM, i):
                is_prime[j] = False
    return primes
## libs ##
from itertools import accumulate as acc
from collections import deque, Counter
from heapq import heapify, heappop, heappush
from bisect import bisect_left

#======================================================#

def main():
    s = IS()
    x, y = MII()
    n = len(s)
    dpx = DD2(n,10**5,init=False)
    dpy = DD2(n,10**5,init=False)
    ff = s.split('T')
    ffx = [len(f) for f in ff[::2]]
    ffy = [len(f) for f in ff[1::2]]
    nx = len(ffx)
    ny = len(ffy)
    if len(ffx) > 0:
        dpx[0][ffx[0]] = True
        for i in range(1, nx):
            now_x = ffx[i-1]
            next_x = ffx[i]
            for j in range(now_x-next_x, now_x+next_x+1):
                dpx[i][j] = dpx[i-1][j-ffx[i]] or dpx[i-1][j+ffx[i]]
    if len(ffy) > 0:
        dpy[0][ffy[0]] = True
        for i in range(1, ny):
            now_y = ffy[i-1]
            next_y = ffy[i]
            for j in range(now_y-next_y, now_y+next_y+1):
                dpy[i][j] = dpy[i-1][j-ffy[i]] or dpy[i-1][j+ffy[i]]
    if len(ffy) > 0:
        dpy[0][-ffy[0]] = True
        for i in range(1, ny):
            now_y = ffy[i-1]
            next_y = ffy[i]
            for j in range(now_y-next_y, now_y+next_y+1):
                dpy[i][j] = dpy[i-1][j-ffy[i]] or dpy[i-1][j+ffy[i]]
    if dpx[nx-1][x] and dpy[ny-1][y]: print('Yes')
    else: print('No')


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
## io ##
def IS(): return sys.stdin.readline().rstrip()
def II(): return int(IS())
def MII(): return list(map(int, IS().split()))
def MIIZ(): return list(map(lambda x: x-1, MII()))
## dp ##
def DD2(d1,d2,init=0): return [[init]*d2 for _ in range(d1)]
def DD3(d1,d2,d3,init=0): return [DD2(d2,d3,init) for _ in range(d1)]
## math ##
MOD=10**9+7
def divc(x,y): return -(-x//y)
def divf(x,y): return x//y
def gcd(x,y):
    while y: x,y = y,x%y
    return x
def lcm(x,y): return x*y//gcd(x,y)
def get_primes(MAX_NUM=10**3):
    """Return a list of prime numbers"""
    is_prime = [True] * MAX_NUM
    is_prime[0] = False
    is_prime[1] = False
    primes = []
    for i in range(MAX_NUM):
        if is_prime[i]:
            primes.append(i)
            for j in range(2*i, MAX_NUM, i):
                is_prime[j] = False
    return primes
## libs ##
from itertools import accumulate as acc
from collections import deque, Counter
from heapq import heapify, heappop, heappush
from bisect import bisect_left

#======================================================#

def main():
    s = IS()
    x, y = MII()
    n = len(s)
    dpx = DD2(n,10**5,init=False)
    dpy = DD2(n,10**5,init=False)
    ff = s.split('T')
    ffx = [len(f) for f in ff[::2]]
    ffy = [len(f) for f in ff[1::2]]
    nx = len(ffx)
    ny = len(ffy)
    if len(ffx) > 0:
        dpx[0][ffx[0]] = True
        for i in range(1, nx):
            for j in range(-8000, 8001):
                dpx[i][j] = dpx[i-1][j-ffx[i]] or dpx[i-1][j+ffx[i]]
    if len(ffy) > 0:
        dpy[0][ffy[0]] = dpy[0][-ffy[0]]= True
        for i in range(1, ny):
            for j in range(-8000, 8001):
                dpy[i][j] = dpy[i-1][j-ffy[i]] or dpy[i-1][j+ffy[i]]
    if dpx[nx-1][x] and dpy[ny-1][y]: print('Yes')
    else: print('No')


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
## io ##
def IS(): return sys.stdin.readline().rstrip()
def II(): return int(IS())
def MII(): return list(map(int, IS().split()))
def MIIZ(): return list(map(lambda x: x-1, MII()))
## dp ##
def DD2(d1,d2,init=0): return [[init]*d2 for _ in range(d1)]
def DD3(d1,d2,d3,init=0): return [DD2(d2,d3,init) for _ in range(d1)]
## math ##
MOD=10**9+7
def divc(x,y): return -(-x//y)
def divf(x,y): return x//y
def gcd(x,y):
    while y: x,y = y,x%y
    return x
def lcm(x,y): return x*y//gcd(x,y)
def get_primes(MAX_NUM=10**3):
    """Return a list of prime numbers"""
    is_prime = [True] * MAX_NUM
    is_prime[0] = False
    is_prime[1] = False
    primes = []
    for i in range(MAX_NUM):
        if is_prime[i]:
            primes.append(i)
            for j in range(2*i, MAX_NUM, i):
                is_prime[j] = False
    return primes
## libs ##
from itertools import accumulate as acc
from collections import deque, Counter
from heapq import heapify, heappop, heappush
from bisect import bisect_left

#======================================================#

def main():
    s = IS()
    x, y = MII()
    n = len(s)
    dpx = DD2(n,10**5,init=False)
    dpy = DD2(n,10**5,init=False)
    ff = s.split('T')
    ffx = [len(f) for f in ff[::2]]
    ffy = [len(f) for f in ff[1::2]]
    if len(ffx) > 0:
        dpx[0][ffx[0]] = True
        for i in range(1, len(ffx)):
            for j in range(-8000, 8001):
                dpx[i][j] = dpx[i-1][j-ffx[i]] or dpx[i-1][j+ffx[i]]
    if len(ffy) > 0:
        dpy[0][ffy[0]] = dpy[0][-ffy[0]]= True
        for i in range(1, len(ffy)):
            for j in range(-8000, 8001):
                dpy[i][j] = dpy[i-1][j-ffy[i]] or dpy[i-1][j+ffy[i]]
    if dpx[len(ffx)-1][x] and dpy[len(ffy)-1][y]: print('Yes')
    else: print('No')


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
S = input()
X, Y = map(int, input().split())

if S.find("F") < 0:
    if X != 0 or Y != 0:
        print("No")
        exit()

n = len(S)
d = list(map(len, S.split("T")))
xs = d[::2]
ys = d[1::2]

dpx = [[False] * (2 * n + 1) for _ in range(len(xs))]
for i in range(len(xs)):
    if i == 0:
        d = (-1) ** S.find("F")
        dpx[i][d * xs[i] + n] = True
        continue

    for j in range(2 * n + 1):
        if j + xs[i] <= 2 * n:
            dpx[i][j] |= dpx[i - 1][j + xs[i]]
        if 0 <= j - xs[i] <= 2 * n:
            dpx[i][j] |= dpx[i - 1][j - xs[i]]

dpy = [[False] * (2 * n + 1) for _ in range(len(ys) + 1)]
dpy[0][n] = True
for i in range(len(ys)):
    for j in range(2 * n + 1):
        if j + ys[i] <= 2 * n:
            dpy[i + 1][j] |= dpy[i][j + ys[i]]
        if 0 <= j - ys[i] <= 2 * n:
            dpy[i + 1][j] |= dpy[i][j - ys[i]]

ans = dpx[-1][X + n] & dpy[-1][Y + n]
print("Yes" if ans else "No")

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline
s = input().rstrip()
gx, gy = map(int, input().split())
rx, ry = 0, 0
head, inst = 0, []
while head < len(s) and s[head] == "F":
    head += 1
    rx += 1
while head < len(s):
    tcnt = 0
    while head < len(s) and s[head] == "T":
        tcnt += 1
        head += 1
    fcnt = 0
    while head < len(s) and s[head] == "F":
        fcnt += 1
        head += 1
    inst.append((tcnt % 2, fcnt))

f_total = sum([f for (_, f) in inst])
f_rem = [0] * (len(inst) + 1)
f_rem[len(inst)] = 0
for i in range(len(inst) - 1, -1, -1):
    f_rem[i] = f_rem[i + 1] + inst[i][1]
assert f_rem[0] == f_total


visited = set()


def reach(i, x, y, dx, dy):
    dist = abs(gx - x) + abs(gy - y)
    # print(f"i={i} ({x},{y}) dist={dist}: inst={inst[i:]}")
    if i == len(inst):
        return dist == 0
    if (i, x, y, dx, dy) in visited:
        return False
    visited.add((i, x, y, dx, dy))
    if dist > f_rem[i] or dist % 2 != f_rem[i] % 2:
        return False
    t, f = inst[i]
    if t:
        dy, dx = dx, -dy
    if reach(i + 1, x + f * dx, y + f * dy, dx, dy):
        return True
    if reach(i + 1, x - f * dx, y - f * dy, -dx, -dy):
        return True
    return False


print("Yes" if reach(0, rx, ry, 1, 0) else "No")

Submission status: Time Limit Exceeded

Solution code:
import heapq
import sys

sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline
s = input().rstrip()
gx, gy = map(int, input().split())
rx, ry = 0, 0
head, inst = 0, []
while head < len(s) and s[head] == "F":
    head += 1
    rx += 1
while head < len(s):
    tcnt = 0
    while head < len(s) and s[head] == "T":
        tcnt += 1
        head += 1
    fcnt = 0
    while head < len(s) and s[head] == "F":
        fcnt += 1
        head += 1
    inst.append((tcnt % 2, fcnt))

f_total = sum([f for (_, f) in inst])
f_rem = [0] * (len(inst) + 1)
f_rem[len(inst)] = 0
for i in range(len(inst) - 1, -1, -1):
    f_rem[i] = f_rem[i + 1] + inst[i][1]
assert f_rem[0] == f_total


visited = set()


def reach():
    hp = [(0, rx, ry, 1, 0)]
    while hp:
        i, x, y, dx, dy = heapq.heappop(hp)

        dist = abs(gx - x) + abs(gy - y)
        # print(f"i={i} ({x},{y}) dist={dist}: inst={inst[i:]}")
        if i == len(inst):
            if dist == 0:
                return True
            continue
        if (i, x, y, dx, dy) in visited:
            continue
        visited.add((i, x, y, dx, dy))
        if dist > f_rem[i]:
            continue
        t, f = inst[i]
        if t:
            dy, dx = dx, -dy
        heapq.heappush(hp, (i + 1, x + f * dx, y + f * dy, dx, dy))
        heapq.heappush(hp, (i + 1, x - f * dx, y - f * dy, -dx, -dy))
    return False


print("Yes" if reach() else "No")

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline
s = input().rstrip()
gx, gy = map(int, input().split())
rx, ry = 0, 0
head, inst = 0, []
while head < len(s) and s[head] == "F":
    head += 1
    rx += 1
while head < len(s):
    tcnt = 0
    while head < len(s) and s[head] == "T":
        tcnt += 1
        head += 1
    fcnt = 0
    while head < len(s) and s[head] == "F":
        fcnt += 1
        head += 1
    inst.append((tcnt % 2, fcnt))

f_total = sum([f for (_, f) in inst])
f_rem = [0] * (len(inst) + 1)
f_rem[len(inst)] = 0
for i in range(len(inst) - 1, -1, -1):
    f_rem[i] = f_rem[i + 1] + inst[i][1]
assert f_rem[0] == f_total


visited = set()


def reach(i, x, y, dx, dy):
    dist = abs(gx - x) + abs(gy - y)
    # print(f"i={i} ({x},{y}) dist={dist}: inst={inst[i:]}")
    if i == len(inst):
        return dist == 0
    if (i, x, y, dx, dy) in visited:
        return False
    visited.add((i, x, y, dx, dy))
    if dist > f_rem[i]:
        return False
    t, f = inst[i]
    if t:
        dy, dx = dx, -dy
    if reach(i + 1, x + f * dx, y + f * dy, dx, dy):
        return True
    if reach(i + 1, x - f * dx, y - f * dy, -dx, -dy):
        return True
    return False


print("Yes" if reach(0, rx, ry, 1, 0) else "No")

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import groupby

sys.setrecursionlimit(1000000)

s=input()
data=[s[i] for i in range(0,len(s))]
data=groupby(data)
s=[]
for key,group in data:
    g=len(list(group))
    if key=='F':
        s.append((key,g))
    else:
        s.append((key,g%2))


x,y=map(int,input().split())
N=len(s)

memo={}
def dfs(startx,starty,direction,num):
    if (startx,starty,direction,num) in memo.keys():
        return memo[(startx,starty,direction,num)]
    if num==N:
        memo[(startx,starty,direction,num)]=0
        memo[(startx,starty,direction,num)]=(startx==x and starty==y)
        return (startx==x and starty==y)

    if s[num][0]!='T':
        if direction==0:
            memo[(startx,starty,direction,num)]=0
            memo[(startx,starty,direction,num)]=dfs(startx+s[num][1],starty,direction,num+1)
            return memo[(startx,starty,direction,num)]
        if direction==90:
            memo[(startx,starty,direction,num)]=0
            memo[(startx,starty,direction,num)]=dfs(startx,starty+s[num][1],direction,num+1)
            return memo[(startx,starty,direction,num)]
        if direction==180:
            memo[(startx,starty,direction,num)]=0
            memo[(startx,starty,direction,num)]=dfs(startx-s[num][1],starty,direction,num+1)
            return memo[(startx,starty,direction,num)]
        if direction==270:
            memo[(startx,starty,direction,num)]=0
            memo[(startx,starty,direction,num)]=dfs(startx,starty-s[num][1],direction,num+1)
            return memo[(startx,starty,direction,num)]

    if s[num][0]=='T':
        memo[(startx,starty,direction,num)]=0
        if s[num][1]==1:
            if dfs(startx,starty,(direction+90)%360,num+1):
                memo[(startx,starty,direction,num)]=True
                return True
            if dfs(startx,starty,(direction-90)%360,num+1):
                memo[(startx,starty,direction,num)]=True
                return True

            memo[(startx,starty,direction,num)]=False
            return False
        else:
            if dfs(startx,starty,(direction)%360,num+1):
                memo[(startx,starty,direction,num)]=True
                return True
            if dfs(startx,starty,(direction-180)%360,num+1):
                memo[(startx,starty,direction,num)]=True
                return True

            memo[(startx,starty,direction,num)]=False
            return False

if dfs(0,0,0,0):
    print('Yes')
else:
    print('No')

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(1000000)

s=input()
x,y=map(int,input().split())
N=len(s)

memo={}
def dfs(startx,starty,direction,num):
    if (startx,starty,direction,num) in memo.keys():
        return memo[(startx,starty,direction,num)]
    if num==N:
        memo[(startx,starty,direction,num)]=0
        memo[(startx,starty,direction,num)]=(startx==x and starty==y)
        return (startx==x and starty==y)

    if s[num]=='F':
        if direction==0:
            memo[(startx,starty,direction,num)]=0
            memo[(startx,starty,direction,num)]=dfs(startx+1,starty,direction,num+1)
            return memo[(startx,starty,direction,num)]
        if direction==90:
            memo[(startx,starty,direction,num)]=0
            memo[(startx,starty,direction,num)]=dfs(startx,starty+1,direction,num+1)
            return memo[(startx,starty,direction,num)]
        if direction==180:
            memo[(startx,starty,direction,num)]=0
            memo[(startx,starty,direction,num)]=dfs(startx-1,starty,direction,num+1)
            return memo[(startx,starty,direction,num)]
        if direction==270:
            memo[(startx,starty,direction,num)]=0
            memo[(startx,starty,direction,num)]=dfs(startx,starty-1,direction,num+1)
            return memo[(startx,starty,direction,num)]

    if s[num]=='T':
        memo[(startx,starty,direction,num)]=0
        if dfs(startx,starty,(direction+90)%360,num+1):
            memo[(startx,starty,direction,num)]=True
            return True
        if dfs(startx,starty,(direction-90)%360,num+1):
            memo[(startx,starty,direction,num)]=True
            return True

        memo[(startx,starty,direction,num)]=False
        return False

if dfs(0,0,0,0):
    print('Yes')
else:
    print('No')

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10**8)

def dp(dp_l,i,N,xs,cum,now):
    if i == N:
        if now == 0:
            return True
        return False
    if abs(now) > cum[i]:
        return False
    if dp_l[i][abs(now)] != -1:
        return dp_l[i][abs(now)]
    dp_l[i][abs(now)] = dp(dp_l,i+1,N,xs,cum,now+xs[i]) or dp(dp_l,i+1,N,xs,cum,now-xs[i])
    return dp_l[i][abs(now)]

def check():
    S = input()
    x, y = map(int, input().split())
    fs = list(map(len,S.split('T')))
    if len(fs)<3:
        if x != fs[0]:
            return False
        if len(fs)==1:
            if y == 0:
                return True
            else:
                return False
        if y != fs[1] and y != -fs[1]:
            return False
        return True
    xs = fs[2::2]
    ys = fs[1::2]
    xs.sort(reverse = True)
    N = len(xs)
    M = len(ys)
    cum = [0]*(N+1)
    for i in range(N-1,-1,-1):
        cum[i] = cum[i+1]+xs[i]
    dp_l = [[-1]*(cum[0]+1) for _ in range(N)]
    if not dp(dp_l,0,N,xs,cum,fs[0]-x):
        return False
    ys.sort(reverse = True)
    cum = [ys[-1]]*(M+1)
    for i in range(M-1,-1,-1):
        cum[i] = cum[i+1]+ys[i]
    dp_l = [[-1]*(cum[0]+1) for _ in range(M)]
    if not dp(dp_l,0,M,ys,cum,-y):
        return False
    return True
if check():
    print('Yes')
else:
    print('No')