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 = input()
x,y = map(int,input().split())
cur_x = 0
cur_y = 0
L_x = []
L_y = []
s += 'K'
temp = 0
dirc = 'yoko'
for i in range(len(s)):
    if s[i] == 'F':
        temp += 1
    elif s[i] == 'T':
        if temp == 0:
            if dirc == 'yoko':
                dirc = 'tate'
            else:
                dirc = 'yoko'
        else:
            if dirc == 'yoko':
                L_x.append(temp)
                temp = 0
                dirc = 'tate'
            else:
                L_y.append(temp)
                temp = 0
                dirc = 'yoko'
    else:
        if temp != 0:
            if dirc == 'yoko':
                L_x.append(temp)
                temp = 0
                dirc = 'tate'
            else:
                L_y.append(temp)
                temp = 0
                dirc = 'yoko'
dp_x = [[False]*16001 for i in range(len(L_x))]
dp_y = [[False]*16001 for i in range(len(L_y))]
if s[0] == 'F':
    dp_x[0][L_x[0]+8000] = True
elif s[0] == 'T' and len(L_x) > 0:
    dp_x[0][L_x[0]+8000] = True
    dp_x[0][8000-L_x[0]] = True
if len(L_y) > 0:
    dp_y[0][L_y[0]+8000] = True
    dp_y[0][8000-L_y[0]] = True
for i in range(1,len(L_x)):
    t = L_x[i]
    for j in range(16001):
        if j-t >= 0 and j+t <= 16000:
            dp_x[i][j] = dp_x[i-1][j-t] or dp_x[i-1][j+t]
        elif j-t < 0 and j+t <= 16000:
            dp_x[i][j] = dp_x[i-1][j+t]
        elif j-t >= 0 and j+t > 16000:
            dp_x[i][j] = dp_x[i-1][j-t]
        else:
            None
for i in range(1,len(L_y)):
    t = L_y[i]
    for j in range(16001):
        if j-t >= 0 and j+t <= 16000:
            dp_y[i][j] = dp_y[i-1][j-t] or dp_y[i-1][j+t]
        elif j-t < 0 and j+t <= 16000:
            dp_y[i][j] = dp_y[i-1][j+t]
        elif j-t >= 0 and j+t > 16000:
            dp_y[i][j] = dp_y[i-1][j-t]
        else:
            None
if len(L_x) == 0 and len(L_y) == 0:
    if x == y == 0:
        print('Yes')
    else:
        print('No')
elif len(L_x) != 0 and len(L_y) == 0:
    if y == 0 and dp_x[len(L_x)-1][8000+x] == True:
        print('Yes')
    else:
        print('No')
elif len(L_x) == 0 and len(L_y) != 0:
    if x == 0 and dp_y[len(L_y)-1][8000+y] == True:
        print('Yes')
    else:
        print('No')
else:
    if dp_x[len(L_x)-1][8000+x] == True and dp_y[len(L_y)-1][8000+y] == True:
        print('Yes')
    else:
        print('No')

Submission status: Time Limit Exceeded

Solution code:
import sys
MAX = 8000

s = input()
x, y = map(int, input().split())
fn = [ int(len(f)) for f in s.split('T')]

xa = []
ya = []

for i in range(len(fn)):
    if i % 2 == 0:
        xa.append(fn[i])
    else:
        ya.append(fn[i])

xasum = sum(xa)
yasum = sum(ya)

if xasum < abs(x) or yasum < abs(y) or xasum + yasum < abs(x) + abs(y):
    print("No")
    sys.exit(0)

dpx = [False]*(2*MAX+1)
dpy = [False]*(2*MAX+1)

dpx[MAX] = True
dpy[MAX] = True

for i in range(len(xa)):
    dp_tmp = [False]*(2*MAX+1)
    for j in range(2*MAX+1):
        if j + xa[i] <= 2*MAX:
            dp_tmp[j+xa[i]] = dp_tmp[j+xa[i]] or dpx[j]
        if j - xa[i] >= 0 and i > 0:
            dp_tmp[j-xa[i]] = dp_tmp[j-xa[i]] or dpx[j]
    for j in range(2*MAX+1):
        dpx[j] = dp_tmp[j]

for i in range(len(ya)):
    dp_tmp = [False]*(2*MAX+1)
    for j in range(2*MAX+1):
        if j + ya[i] <= 2*MAX:
            dp_tmp[j+ya[i]] = dp_tmp[j+ya[i]] or dpy[j]
        if j - ya[i] >= 0:
            dp_tmp[j-ya[i]] = dp_tmp[j-ya[i]] or dpy[j]
    for j in range(2*MAX+1):
        dpy[j] = dp_tmp[j]

if dpx[MAX+x] and dpy[MAX+y]:
    print("Yes")
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    s = input().rstrip() + 'T'
    x,y = map(int, input().split())
    # 奇数はy方向, 偶数はx方向
    l = []
    susumu = 0
    for i in range(len(s)):
        if s[i] == 'T':
            l.append(susumu)
            susumu = 0
        else:
            susumu += 1
    b = len(l)
    dp = [[0]*16001 for _ in range(3)]
    dp[0][8000] = 1
    dp[1][8000] = 1
    for i in range(b):
        if i==0:
            dp[2][8000+l[i]] = 1
        elif i%2 == 0:
            for j in range(16000):
                if dp[0][j]:
                    dp[2][j-l[i]] = 1
                    dp[2][j+l[i]] = 1
        elif i%2 == 1:
            for j in range(16000):
                if dp[0][j]:
                    dp[2][j-l[i]] = 1
                    dp[2][j+l[i]] = 1
        dp = dp[1:] + [[0]*16000]
    if b%2 == 0:
        if dp[0][x+8000] == 1 and dp[1][y+8000] == 1:
            print('Yes')
        else:
            print('No')
    else:
        if dp[1][x+8000] == 1 and dp[0][y+8000] == 1:
            print('Yes')
        else:
            print('No')

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
s = input().rstrip('T')
x,y = map(int,input().split())
goal = set()
goal.add((x,y))
pos = [0,0]
stat = 0

for c in s:
  if c=='F':
    pos[stat] += 1
  else:
    px,py = pos
    stat = 1 - stat
    for x,y in list(goal):
      if stat:
        nx = x
        ny = py + (py-y)
      else:
        nx = px + (px-x)
        ny = y
      goal.add((nx,ny))
        
print('Yes' if tuple(pos) in goal else 'No')

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

# https://atcoder.jp/contests/abc082/tasks/arc087_b
# 16:28-

import sys

sys.setrecursionlimit(10000)


def main():
    s = input()
    x, y = map(int, input().split())

    n_f = len([1 for c in s if c == "F"])

    directions = {
        "r": ["u", "d"], "l": ["u", "d"], "u": ["l", "r"], "d": ["l", "r"]
    }

    def rec(now_x, now_y, dire, f_rest, s_idx, s, len_s, to_x, to_y):
        dist = abs(to_x - now_x) + abs(to_y - now_y)

        if s_idx == len_s and dist == 0:
            return True

        if dist > f_rest:
            return False  # ?

        # まだ可能性がある
        # print(s_idx, dist, f_rest)
        if s[s_idx] == "F":
            if dire == "u":
                return rec(now_x, now_y+1, dire, f_rest-1, s_idx+1, s, len_s, to_x, to_y)
            elif dire == "d":
                return rec(now_x, now_y-1, dire, f_rest-1, s_idx+1, s, len_s, to_x, to_y)
            elif dire == "r":
                return rec(now_x+1, now_y, dire, f_rest-1, s_idx+1, s, len_s, to_x, to_y)
            else:
                return rec(now_x-1, now_y, dire, f_rest-1, s_idx+1, s, len_s, to_x, to_y)  
        else:
            edges = []
            next_dires = directions[dire]
            for next_dire in next_dires:
                edges.append(rec(now_x, now_y, next_dire, f_rest, s_idx+1, s, len_s, to_x, to_y))
            return edges[0] or edges[1]

    ans = rec(0, 0, "r", n_f, 0, s, len(s), x, y)

    return "Yes" if ans else "No"


print(main())

Submission status: Time Limit Exceeded

Solution code:
s=input()
x,y=map(int,input().split())
XY=[[]for i in range(2)]
a=0
b=0
for i in range(len(s)):
  if s[i]=="T":
    XY[b].append(a)
    a=0
    b=(b+1)%2
  else:
    a=a+1
XY[b].append(a)
xx=sum(XY[0])
yy=sum(XY[1])
dpx=[[0]*(2*xx+5) for i in range(len(XY[0])+1)]#x=0とj=xx+2を対応させる
dpy=[[0]*(2*yy+5) for i in range(len(XY[1])+1)]#y=0とj=yy+2を対応させる
dpx[1][xx+XY[0][0]+2]=1
for i in range(1,len(XY[0])):
  for j in range(2*xx+5):
    if dpx[i][j]==1:
      dpx[i+1][j-XY[0][i]]=1
      dpx[i+1][j+XY[0][i]]=1
dpy[0][yy+2]=1
for i in range(len(XY[1])):
  for j in range(2*yy+5):
    if dpy[i][j]==1:
      dpy[i+1][j-XY[1][i]]=1
      dpy[i+1][j+XY[1][i]]=1
if x+xx+2<0 or 2*xx+4<x+xx+2 or y+yy+2<0 or 2*yy+4<y+yy+2:
  print("No")
  exit()
if dpx[-1][x+xx+2]==1 and dpy[-1][y+yy+2]==1:
  print("Yes")
else:
  print("No")

Submission status: Time Limit Exceeded

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""


def main():

    ss = list(input())[:-1]

    ss = s(ss)

    n = len(ss)

    x,y = m()

    x += 8000

    y += 8000

    dpx = set([8000])

    dpy = set([8000])

    ro = 0

    for i in range(1,n+1):
        pop = ss[i-1]
        if pop[0] == "T":
            if pop[1] % 2 == 1:
                ro ^= 1
        else:
            if i == 1:
                dpx = set([8000+pop[1]])
            else:
                if ro == 0:
                    ch = []
                    for num in dpx:
                        if num + pop[1] <= 16000:
                            ch.append(num + pop[1])    
                        if num - pop[1] >= 0:
                            ch.append(num - pop[1])
                        dpx = set(ch)
                else:
                    ch = []
                    for num in dpy:
                        if num + pop[1] <= 16000:
                            ch.append(num + pop[1])
                        if num - pop[1] >= 0:
                            ch.append(num - pop[1])
                        dpy = set(ch)

    if x in dpx and y in dpy:
        print("Yes")
    else:
        print("No")

            


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""


def main():

    x = list(input())[:-1]
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    
    
    ss = a

    n = len(ss)

    x,y = m()

    x += 8000

    y += 8000

    dpx = [[False for i in range(8000*2 + 1)] for j in range(n+1)]

    dpy = [[False for i in range(8000*2 + 1)] for j in range(n+1)]

    dpx[0][8000] = True

    dpy[0][8000] = True

    ro = 0


    for i in range(1,n+1):
        pop = ss[i-1]
        if pop[0] == "T":
            if pop[1] % 2 == 1:
                ro ^= 1
            for j in range(16000+1):
                dpx[i][j] = dpx[i-1][j]
                dpy[i][j] = dpy[i-1][j]
        else:
            if i == 1:
                dpx[i][pop[1]+ 8000] = True
                dpy[i][8000] = True
                
            else:
                if ro == 0:
                    for j in range(16000+1):
                        if j + pop[1] <= 16000:
                            if dpx[i-1][j]:
                                dpx[i][j + pop[1]] = dpx[i-1][j]
                        if j - pop[1] >= 0:
                            if dpx[i-1][j]:
                                dpx[i][j - pop[1]] = dpx[i-1][j]
                        dpy[i][j] = dpy[i-1][j]
                else:
                    for j in range(16000+1):
                        if j + pop[1] <= 16000:
                            if dpy[i-1][j]:
                                dpy[i][j + pop[1]] = dpy[i-1][j]
                        if j - pop[1] >= 0:
                            if dpy[i-1][j]:
                                dpy[i][j - pop[1]] = dpy[i-1][j]
                        dpx[i][j] = dpx[i-1][j]

    if dpx[-1][x] and dpy[-1][y]:
        print("Yes")
    else:
        print("No")

            


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""


def main():

    ss = list(input())[:-1]

    ss = s(ss)

    n = len(ss)

    x,y = m()

    x += 8000

    y += 8000

    dpx = [[False for i in range(8000*2 + 1)] for j in range(n+1)]

    dpy = [[False for i in range(8000*2 + 1)] for j in range(n+1)]

    dpx[0][8000] = True

    dpy[0][8000] = True

    ro = 0

    for i in range(1,n+1):
        pop = ss[i-1]
        if pop[0] == "T":
            if pop[1] % 2 == 1:
                ro ^= 1
            for j in range(16000+1):
                dpx[i][j] = dpx[i-1][j]
                dpy[i][j] = dpy[i-1][j]
        else:
            if i == 1:
                dpx[i][pop[1]+ 8000] = True
                dpy[i][8000] = True
                
            else:
                if ro == 0:
                    for j in range(16000+1):
                        if j + pop[1] <= 16000:
                            if dpx[i-1][j]:
                                dpx[i][j + pop[1]] = dpx[i-1][j]
                        if j - pop[1] >= 0:
                            if dpx[i-1][j]:
                                dpx[i][j - pop[1]] = dpx[i-1][j]
                        dpy[i][j] = dpy[i-1][j]
                else:
                    for j in range(16000+1):
                        if j + pop[1] <= 16000:
                            if dpy[i-1][j]:
                                dpy[i][j + pop[1]] = dpy[i-1][j]
                        if j - pop[1] >= 0:
                            if dpy[i-1][j]:
                                dpy[i][j - pop[1]] = dpy[i-1][j]
                        dpx[i][j] = dpx[i-1][j]

    if dpx[-1][x] and dpy[-1][y]:
        print("Yes")
    else:
        print("No")

            


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""


def main():

    ss = list(input())[:-1]

    ss = s(ss)

    n = len(ss)

    x,y = m()

    x += 8000

    y += 8000

    dpx = [[0 for i in range(8000*2 + 1)] for j in range(n+1)]

    dpy = [[0 for i in range(8000*2 + 1)] for j in range(n+1)]

    dpx[0][8000] = 1

    dpy[0][8000] = 1

    ro = 0

    for i in range(1,n+1):
        pop = ss[i-1]
        if pop[0] == "T":
            if pop[1] % 2 == 1:
                ro ^= 1
            for j in range(16000+1):
                dpx[i][j] = dpx[i-1][j]
                dpy[i][j] = dpy[i-1][j]
        else:
            if i == 1:
                dpx[i][pop[1]+ 8000] = 1
                dpy[i][8000] = 1
                
            else:
                if ro == 0:
                    for j in range(16000+1):
                        if j + pop[1] <= 16000:
                            if dpx[i-1][j]:
                                dpx[i][j + pop[1]] = dpx[i-1][j]
                        if j - pop[1] >= 0:
                            if dpx[i-1][j]:
                                dpx[i][j - pop[1]] = dpx[i-1][j]
                        dpy[i][j] = dpy[i-1][j]
                else:
                    for j in range(16000+1):
                        if j + pop[1] <= 16000:
                            if dpy[i-1][j]:
                                dpy[i][j + pop[1]] = dpy[i-1][j]
                        if j - pop[1] >= 0:
                            if dpy[i-1][j]:
                                dpy[i][j - pop[1]] = dpy[i-1][j]
                        dpx[i][j] = dpx[i-1][j]

    if dpx[-1][x] and dpy[-1][y]:
        print("Yes")
    else:
        print("No")

            


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

ss = list(input())[:-1]

ss = s(ss)

n = len(ss)

x,y = m()

x += 8000

y += 8000

dpx = [[False for i in range(8000*2 + 1)] for j in range(n+1)]

dpy = [[False for i in range(8000*2 + 1)] for j in range(n+1)]

dpx[0][8000] = True

dpy[0][8000] = True

ro = 0

for i in range(1,n+1):
    pop = ss[i-1]
    if pop[0] == "T":
        if pop[1] % 2 == 1:
            ro ^= 1
        for j in range(16000+1):
            dpx[i][j] = dpx[i-1][j]
            dpy[i][j] = dpy[i-1][j]
    else:
        if i == 1:
            dpx[i][pop[1]+ 8000] = True
            dpy[i][8000] = True
            
        else:
            if ro == 0:
                for j in range(16000+1):
                    if j + pop[1] <= 16000:
                        if dpx[i-1][j]:
                            dpx[i][j + pop[1]] = dpx[i-1][j]
                    if j - pop[1] >= 0:
                        if dpx[i-1][j]:
                            dpx[i][j - pop[1]] = dpx[i-1][j]
                    dpy[i][j] = dpy[i-1][j]
            else:
                for j in range(16000+1):
                    if j + pop[1] <= 16000:
                        if dpy[i-1][j]:
                            dpy[i][j + pop[1]] = dpy[i-1][j]
                    if j - pop[1] >= 0:
                        if dpy[i-1][j]:
                            dpy[i][j - pop[1]] = dpy[i-1][j]
                    dpx[i][j] = dpx[i-1][j]

if dpx[-1][x] and dpy[-1][y]:
    print("Yes")
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

ss = list(input())[:-1]

ss = s(ss)

n = len(ss)

x,y = m()

x += 8000

y += 8000

dpx = [[False for i in range(8000*2 + 1)] for j in range(n+1)]

dpy = [[False for i in range(8000*2 + 1)] for j in range(n+1)]

dpx[0][8000] = True

dpy[0][8000] = True

ro = 0

for i in range(1,n+1):
    pop = ss[i-1]
    if pop[0] == "T":
        if pop[1] % 2 == 1:
            ro ^= 1
        for j in range(16000+1):
            dpx[i][j] = dpx[i-1][j]
            dpy[i][j] = dpy[i-1][j]
    else:
        if i == 1:
            dpx[i][pop[1]+ 8000] = True
            dpy[i][8000] = True
            
        else:
            if ro == 0:
                for j in range(16000+1):
                    if j + pop[1] <= 16000:
                        if dpx[i-1][j]:
                            dpx[i][j + pop[1]] = dpx[i-1][j]
                    if j - pop[1] >= 0:
                        if dpx[i-1][j]:
                            dpx[i][j - pop[1]] = dpx[i-1][j]
                for j in range(16000+1):
                    dpy[i][j] = dpy[i-1][j]
            else:
                for j in range(16000+1):
                    if j + pop[1] <= 16000:
                        if dpy[i-1][j]:
                            dpy[i][j + pop[1]] = dpy[i-1][j]
                    if j - pop[1] >= 0:
                        if dpy[i-1][j]:
                            dpy[i][j - pop[1]] = dpy[i-1][j]
                for j in range(16000+1):
                    dpx[i][j] = dpx[i-1][j]

if dpx[-1][x] and dpy[-1][y]:
    print("Yes")
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)


def dfs(L, i, pos):
    global goal, LL
    rst = False
    if i == LL:
        rst |= (pos == goal)
    else:
        d = L[i]
        if pos + d not in memo[i]:
            r = dfs(L, i + 1, pos + d)
            memo[i][pos + d] = r
        rst |= memo[i][pos + d]
        if pos - d not in memo[i]:
            r = dfs(L, i + 1, pos - d)
            memo[i][pos - d] = r
        rst |= memo[i][pos - d]
    return rst


S = input().split('T')
x, y = map(int, input().split())

X = []
Y = []
for i, s in enumerate(S):
    if i % 2 == 0:
        X.append(len(s))
    else:
        Y.append(len(s))

if sum(X) < abs(x) or sum(Y) < abs(y):
    print('No')
    exit()


goal, LL = x, len(X)
memo = [{} for _ in range(LL)]
memo[0][X[0]] = True
flag_x = dfs(X, 1, X[0])

goal, LL = y, len(Y)
memo = [{} for _ in range(LL)]
flag_y = dfs(Y, 0, 0)

if flag_x and flag_y:
    print('Yes')
else:
    print('No')

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)


def dfs(L, i, pos):
    global goal, LL
    rst = False
    if i == LL:
        rst |= (pos == goal)
    else:
        d = L[i]
        rst |= dfs(L, i + 1, pos + d)
        rst |= dfs(L, i + 1, pos - d)
    return rst


S = input().split('T')
x, y = map(int, input().split())

X = []
Y = []
for i, s in enumerate(S):
    if i % 2 == 0:
        X.append(len(s))
    else:
        Y.append(len(s))

if sum(X) < abs(x) or sum(Y) < abs(y):
    print('No')
    exit()


goal, LL = x, len(X)
flag_x = dfs(X, 1, X[0])
goal, LL = y, len(Y)
flag_y = dfs(Y, 0, 0)

if flag_x and flag_y:
    print('Yes')
else:
    print('No')

Submission status: Time Limit Exceeded

Solution code:
##幅優先探索
from collections import deque

def dfs(S,X,Y):
    que = deque()
    que.append([0,0,0,0])
    l = len(S)
    d = [[1,0],[0,1],[-1,0],[0,-1]]
    cd = [[1,3],[2,0],[3,1],[0,2]]

    while que:
        x,y,s,current_d = que.popleft()

        if s <= l-1:    
            if S[s] == "F":
                que.append([x+d[current_d][0],y+d[current_d][1],s+1,current_d])
            else:##S[s] == "T"
                for i in cd[current_d]:
                    que.append([x,y,s+1,i])
        else:
            if x == X and y == Y:
                return "Yes"
    return "No"



def main():
    s = input()
    x,y = map(int,input().split())
    print(dfs(s,x,y))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def solve():
    s = input()
    x, y = map(int, input().split())
    
    move_x, move_y = [], [0]
    direction = 0
    cnt = 0
    for i in range(len(s)):
        if s[i] == 'F':
            cnt += 1
        if s[i] == 'T' or i == len(s) - 1:
            if direction == 0:
                move_x.append(cnt)
            else:
                move_y.append(cnt)
            direction ^= 1
            cnt = 0
    
    dp_x = [[False] * 16001 for _ in range(len(move_x))]
    dp_x[0][8000 + move_x[0]] = True
    for i in range(1, len(move_x)):
        for j in range(16001):
            if dp_x[i - 1][j]:
                dp_x[i][j + move_x[i]] = True
                dp_x[i][j - move_x[i]] = True
    
    dp_y = [[False] * 16001 for _ in range(len(move_y))]
    dp_y[0][8000] = True
    for i in range(1, len(move_y)):
        for j in range(16001):
            if dp_y[i - 1][j]:
                dp_y[i][j + move_y[i]] = True
                dp_y[i][j - move_y[i]] = True
    
    if dp_x[-1][8000 + x] and dp_y[-1][8000 + y]:
        print('Yes')
    else:
        print('No')


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
s = input()
x, y = map(int, input().split())

mv = [len(e) for e in s.split("T")]
mv_x = mv[2::2]
mv_y = mv[1::2]


def solve_dp(li, start, end):
    l = len(li)
    mx = sum(li)

    if l == 0:
        return start == end

    left = start - mx
    right = start + mx

    if end > right or end < left:
        return 0

    dp = [[0] * (2 * mx + 1) for _ in range(l + 1)]
    dp[0][start] = 1
    for i, e in enumerate(li, 1):
        for j in range(left, right + 1):
            if left <= j - e <= right:
                dp[i][j] |= dp[i-1][j-e]
            if left <= j + e <= right:
                dp[i][j] |= dp[i-1][j+e]

    return dp[l][end]


bl_x = solve_dp(mv_x, mv[0], x)
bl_y = solve_dp(mv_y, 0, y)

if bl_x and bl_y:
    ans = "Yes"
else:
    ans = "No"

print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input()
x, y = map(int, input().split())

mv = [len(e) for e in s.split("T")]
mv_x = mv[2::2]
mv_y = mv[1::2]

MAX = 8000


def solve_dp(li, start, end):
    l = len(li)
    dp = [[0] * (2 * MAX + 1) for _ in range(l + 1)]
    dp[0][start] = 1
    for i, e in enumerate(li, 1):
        for j in range(-MAX, MAX + 1):
            if -MAX <= j - e <= MAX:
                dp[i][j] |= dp[i-1][j-e]
            if -MAX <= j + e <= MAX:
                dp[i][j] |= dp[i-1][j+e]

    return dp[l][end]


bl_x = solve_dp(mv_x, mv[0], x)
bl_y = solve_dp(mv_y, 0, y)

if bl_x and bl_y:
    ans = "Yes"
else:
    ans = "No"

print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input()
N = len(s)
x,y = map(int, input().split())
ls = s.split('T')
A = []
B = []
dpx = [0]*(2*N+1)
dpy = [0]*(2*N+1)
for i,c in enumerate(ls):
  if i%2==0:
    A += [len(c)]
  else:
    B += [len(c)]
x -= A[0]
A = A[1:]
dpx[N] = 1
dpy[N] = 1
for a in A:
  dpx = [1 if (i>=a and dpx[i-a]) or (i<=2*N-a and dpx[i+a]) else 0 for i in range(2*N+1)]
for b in B:
  dpy = [1 if (i>=b and dpy[i-b]) or (i<=2*N-b and dpy[i+b]) else 0 for i in range(2*N+1)]
if x>N or y>N:
  print('No')
elif dpx[x+N] and dpy[y+N]:
  print('Yes')
else:
  print('No')