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:
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
mod=10**9+7

s=input()+"T"
N=len(s)
x,y=MI()

F=[[],[]]

temp=0
bit=0
for i in range(N):
    if s[i]=="F":
        temp+=1
    else:
        if temp!=0:
            F[bit].append(temp)
        bit=(bit+1)%2
        temp=0
        
Nx=len(F[0])
Ny=len(F[1])

        
#i番目の文字で，位置x [-N~N]につけるかどうか
dpx=[[False]*(2*N+1) for _ in range(Nx+1)]
dpy=[[False]*(2*N+1) for _ in range(Ny+1)]

dpx[0][N]=True
dpy[0][N]=True

if Nx>=1:
    dpx[1][N]=False
    dpx[1][N+F[0][0]]=True
    if s[0]=="T":
        dpx[1][N-F[0][0]]=True


for i in range(1,Nx):
    for j in range(2*N+1):
        if dpx[i][j]==1:
            jj=j+F[0][i]
            jjj=j-F[0][i]
            if jj<=(2*N):
                dpx[i+1][jj]=1
            if jjj>=0:
                dpx[i+1][jjj]=1
                
                
for i in range(Ny):
    for j in range(2*N+1):
        if dpy[i][j]==1:
            jj=j+F[1][i]
            jjj=j-F[1][i]
            if jj<=(2*N):
                dpy[i+1][jj]=1
            if jjj>=0:
                dpy[i+1][jjj]=1

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

Submission status: Time Limit Exceeded

Solution code:
#13:27
s = input()
l = len(s)
s = 'F' + s
x,y = map(int,input().split())
raw = [1]
for i in range(1,l+1):
  if s[i-1:i+1] == 'FF':
    raw[-1] += 1
  elif s[i-1:i+1] == 'TF':
    raw.append(1)
  if s[i-1:i+1] == 'TT':
    raw.append(0)
l2 = len(raw)
a = []
b = []
for i in range(l2):
  if i == 0:
    x -= raw[i]-1
  elif i % 2 == 0:
    a.append(raw[i])
  else:
    b.append(raw[i])
#print(raw)
#print(a,x)
#print(b,y)
now = [0 for _ in range(16001)]
now[8000] = 1
l = len(a)
for j in range(l):
  last = now
  now = [0 for _ in range(16001)]
  for i in range(16001):
    if last[i] == 1:
      now[i+a[j]] = 1
      now[i-a[j]] = 1
if now[8000+x] == 0:
  print('No')
  exit()
now = [0 for _ in range(16001)]
now[8000] = 1
l = len(b)
for j in range(l):
  last = now
  now = [0 for _ in range(16001)]
  for i in range(16001):
    if last[i] == 1:
      now[i+b[j]] = 1
      now[i-b[j]] = 1
if now[8000+y] == 1:
  print('Yes')
else:
  print('No')

Submission status: Time Limit Exceeded

Solution code:
#13:27
s = input()
l = len(s)
s = 'F' + s
x,y = map(int,input().split())
raw = [1]
for i in range(1,l+1):
  if s[i-1:i+1] == 'FF':
    raw[-1] += 1
  elif s[i-1:i+1] == 'TF':
    raw.append(1)
  if s[i-1:i+1] == 'TT':
    raw.append(0)
l2 = len(raw)
a = []
b = []
for i in range(l2):
  if i == 0:
    x -= raw[i]-1
  elif i % 2 == 0:
    a.append(raw[i])
  else:
    b.append(raw[i])
#print(raw)
#print(a,x)
#print(b,y)
now = [0 for _ in range(16001)]
now[8000] = 1
for aa in a:
  last = now
  now = [0 for _ in range(16001)]
  for i in range(16001):
    if last[i] == 1:
      now[i+aa] = 1
      now[i-aa] = 1
if now[8000+x] == 0:
  print('No')
  exit()
now = [0 for _ in range(16001)]
now[8000] = 1
for bb in b:
  last = now
  now = [0 for _ in range(16001)]
  for i in range(16001):
    if last[i] == 1:
      now[i+bb] = 1
      now[i-bb] = 1
if now[8000+y] == 1:
  print('Yes')
else:
  print('No')

Submission status: Time Limit Exceeded

Solution code:
#13:27
s = input()
l = len(s)
s = 'F' + s
x,y = map(int,input().split())
raw = [1]
for i in range(1,l+1):
  if s[i] == 'F':
    if s[i-1] == 'F':
      raw[-1] += 1
    else:
      raw.append(1)
  if s[i] == 'T':
    if s[i-1] == 'T':
      raw.append(0)
l2 = len(raw)
a = []
b = []
for i in range(l2):
  if i == 0:
    x -= raw[i]-1
  elif i % 2 == 0:
    a.append(raw[i])
  else:
    b.append(raw[i])
#print(raw)
#print(a,x)
#print(b,y)
nowa = [0 for _ in range(16001)]
nowa[8000] = 1
for aa in a:
  lasta = nowa
  nowa = [0 for _ in range(16001)]
  for i in range(16001):
    if lasta[i] == 1:
      nowa[i+aa] = 1
      nowa[i-aa] = 1
nowb = [0 for _ in range(16001)]
nowb[8000] = 1
for bb in b:
  lastb = nowb
  nowb = [0 for _ in range(16001)]
  for i in range(16001):
    if lastb[i] == 1:
      nowb[i+bb] = 1
      nowb[i-bb] = 1
if nowa[8000+x] * nowb[8000+y] == 1:
  print('Yes')
else:
  print('No')

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import itertools

tasks = list(input())
tasks_list = []
t_counter = 0
for i in range(len(tasks)):
  if i == 0:
    tasks_list.append([tasks[i],1])
    if tasks[i] == "T":
      t_counter += 1
  else:
    if tasks_list[-1][0] == tasks[i]:
      tasks_list[-1][1] = tasks_list[-1][1]+1
    elif tasks_list[-1][0] != tasks[i]:
      tasks_list.append([tasks[i],1])
      if tasks[i] == "T":
        t_counter += 1
t_bin = itertools.product((0,1), repeat=t_counter)

t_list = []
for i in t_bin:
  t_list.append(i)

target_x, target_y = map(int, input().split())

act_dict = {
  1: np.array([1, 0]),
  2: np.array([0, 1]),
  3: np.array([-1, 0]),
  4: np.array([0, -1]),
}

ans = "No"
for i in range(len(t_list)):
  t_counter = 0
  pos = np.array([0,0])
  act = 1

  for j in tasks_list:
    if j[0] == "F":
      pos += act_dict[act] * j[1]
    elif j[0] == "T":
      if act == 1:
        if j[1] % 2 == 0:
          if t_list[i][t_counter] == 0:
            act = 1
          if t_list[i][t_counter] == 1:
            act = 3
        if j[1] % 2 == 1:
          if t_list[i][t_counter] == 0:
            act = 2
          if t_list[i][t_counter] == 1:
            act = 4
      elif act == 2:
        if j[1] % 2 == 0:
          if t_list[i][t_counter] == 0:
            act = 2
          if t_list[i][t_counter] == 1:
            act = 4
        if j[1] % 2 == 1:
          if t_list[i][t_counter] == 0:
            act = 3
          if t_list[i][t_counter] == 1:
            act = 1
      elif act == 3:
        if j[1] % 2 == 0:
          if t_list[i][t_counter] == 0:
            act = 3
          if t_list[i][t_counter] == 1:
            act = 1
        if j[1] % 2 == 1:
          if t_list[i][t_counter] == 0:
            act = 4
          if t_list[i][t_counter] == 1:
            act = 2
      elif act == 4:
        if j[1] % 2 == 0:
          if t_list[i][t_counter] == 0:
            act = 4
          if t_list[i][t_counter] == 1:
            act = 2
        if j[1] % 2 == 1:
          if t_list[i][t_counter] == 0:
            act = 1
          if t_list[i][t_counter] == 1:
            act = 3
      t_counter += 1
  if pos[0] == target_x and pos[1] == target_y:
    ans = "Yes"
    break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import itertools

tasks = list(input())
t_bin = itertools.product((0,1), repeat=tasks.count("T"))
t_list = []
for i in t_bin:
  t_list.append(i)

target_x, target_y = map(int, input().split())

act_dict = {
  1: np.array([1, 0]),
  2: np.array([0, 1]),
  3: np.array([-1, 0]),
  4: np.array([0, -1]),
}

ans = "No"

for i in range(len(t_list)):
  t_counter = 0
  pos = np.array([0,0])
  act = 1

  for j in tasks:
    if j == "F":
      pos += act_dict[act]
    elif j == "T":
      if act == 1:
        if t_list[i][t_counter] == 0:
          act = 4
        elif t_list[i][t_counter] == 1:
          act = 2
      elif act == 2:
        if t_list[i][t_counter] == 0:
          act = 1
        elif t_list[i][t_counter] == 1:
          act = 3
      elif act == 3:
        if t_list[i][t_counter] == 0:
          act = 2
        elif t_list[i][t_counter] == 1:
          act = 4
      elif act == 4:
        if t_list[i][t_counter] == 0:
          act = 3
        elif t_list[i][t_counter] == 1:
          act = 1
      t_counter += 1
  if pos[0] == target_x and pos[1] == target_y:
    ans = "Yes"
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

s = input().split('T')
dx = list(map(len, s[0::2]))
dy = list(map(len, s[1::2]))
lx = sum(dx)
ly = sum(dy)
x, y = map(int, input().split())

dp = [defaultdict(bool) for _ in range(len(dx))]
dp[0][dx[0]] = True
for i in range(1, len(dx)):
    for j in range(-lx, lx + 1):
        dp[i][j] = dp[i - 1][j - dx[i]] or dp[i - 1][j + dx[i]]

x_ok = dp[len(dx) - 1][x]

if len(dy) > 0:
    dp = [defaultdict(bool) for _ in range(len(dy))]
    dp[0][dy[0]] = True
    dp[0][-dy[0]] = True
    for i in range(1, len(dy)):
        for j in range(-ly, ly + 1):
            dp[i][j] = dp[i - 1][j - dy[i]] or dp[i - 1][j + dy[i]]
    y_ok = dp[len(dy) - 1][y]
else:
    y_ok = y == 0

print('Yes' if x_ok and y_ok else 'No')

Submission status: Time Limit Exceeded

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

ss = s.split("T")
xmove = [i.count("F") for i in ss[::2]]
xfirst = xmove[0] # xの１回目はプラス方向固定のため切り出す
xmove = xmove[1:] # ２回目以降でリスト再作成
ymove = [i.count("F") for i in ss[1::2]]

lenx, leny = len(xmove), len(ymove)

# dp[i][p]: (x, y 各方向の)i回目の移動の後にpにいることができるか
dpx = [[False] * 8010 * 2 for _ in range(lenx+1)]
dpy = [[False] * 8010 * 2 for _ in range(leny+1)]

dpx[0][xfirst] = True
for i in range(lenx):
  for j in range(-8010, 8010):
    if j - xmove[i] > -8010:
      dpx[i+1][j] = max(dpx[i+1][j], dpx[i][j - xmove[i]])
    if j + xmove[i] < 8010: 
      dpx[i+1][j] = max(dpx[i+1][j], dpx[i][j + xmove[i]])

dpy[0][0] = True
for i in range(leny):
  for j in range(-8010, 8010):
    if j - ymove[i] > -8010:
      dpy[i+1][j] = max(dpy[i+1][j], dpy[i][j - ymove[i]])
    if j + ymove[i] < 8010:
      dpy[i+1][j] = max(dpy[i+1][j], dpy[i][j + ymove[i]])

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

Submission status: Time Limit Exceeded

Solution code:
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

k = 8000
def foo(fe,x,ev):
    n = len(fe)
    d = [ [False]*(2*k+1) for i in range(n+1) ]
    d[0][k] = True
    if len(fe)>0:
        d[1][fe[0]+k] = True
        if not ev:
            d[1][-fe[0]+k] = True
    for i in range(1,n):
        for j in range(-k,k+1):
            if d[i][j+k]:
                d[i+1][j+fe[i]+k] = True
                d[i+1][j-fe[i]+k] = True
    return d[n][x+k]

s = ins()
x,y = inm()
f = [ [], [] ]
strk = 0
turn = 0
n = len(s)
for i in range(n):
    if s[i]=='T':
        f[turn].append(strk)
        turn = 1 - turn
        strk = 0
    else:
        strk += 1
f[turn].append(strk)
if foo(f[0],x,True) and foo(f[1],y,False):
    print('Yes')
else:
    print('No')

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def main():
    order_F = []
    order_F = input().rstrip().split('T')
    x, y = map(int, input().split())
    distance = [len(i) for i in order_F]
    x -= distance[0]
    side = []
    vert = []
    sum_s = 0
    sum_v = 0
    s_append = side.append
    v_append = vert.append
    s_append(0)
    v_append(0)
    for i in range(1, len(distance)):
        if i%2 == 0:
            sum_s += distance[i]
            for j in reversed(range(len(side))):
                s_append(side[j] + distance[i])
        else:
            sum_v += distance[i]
            for j in reversed(range(len(vert))):
                v_append(vert[j] + distance[i])
    if  (sum_s - x)/2 in side and (sum_v - y)/2 in vert:
        print("Yes")
    else:
        print("No")

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def main():
    order_F = []
    order_F = input().rstrip().split('T')
    x, y = map(int, input().split())
    distance = [len(i) for i in order_F]
    side = []
    vert = []
    s_append = side.append
    v_append = vert.append
    s_append(distance[0])
    v_append(0)
    for i in range(1, len(distance)):
        if i%2 == 0:
            tmp = [j + distance[i] for j in side]
            for j, value in enumerate(side):
                side[j] = value - distance[i]
            side.extend(tmp)
        else:
            tmp = [j + distance[i] for j in vert]
            for j, value in enumerate(vert):
                vert[j] = value - distance[i]
            vert.extend(tmp)
    if x in side and y in vert:
        print("Yes")
    else:
        print("No")

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def main():
    order_F = []
    order_F = input().rstrip().split('T')
    x, y = map(int, input().split())
    distance = [len(i) for i in order_F]
    side = []
    vert = []
    side.append(distance[0])
    vert.append(0)
    for i in range(1, len(distance)):
        if i%2 == 0:
            tmp = [j for j in side]
            for j, value in enumerate(tmp):
                side[j] = value + distance[i]
                side.append(value - distance[i])
        else:
            tmp = [j for j in vert]
            for j, value in enumerate(tmp):
                vert[j] = value + distance[i]
                vert.append(value - distance[i])
    if x in side and y in vert:
        print("Yes")
    else:
        print("No")

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def main():
    order_F = []
    order_F = input().rstrip().split('T')
    x, y = map(int, input().split())
    vert_DP = [False] * 8001
    side_DP = [False] * 8001
    vert_DP[0] = True
    side_DP[0] = True
    vert_sum = 0
    side_sum = 0
    distance = [len(order_F[i]) for i, value in enumerate(order_F)]
    x -= distance[0]
    for i, value in enumerate(distance):
        if i == 0:
            continue
        if i % 2 == 0:
            side_sum += value
            for j in reversed(range(8001)):
                if side_DP[j]:
                    side_DP[j + value] = True
        else:
            vert_sum += value
            for j in reversed(range(8001)):
                if vert_DP[j]:
                    vert_DP[j + value] = True
    if side_sum < x or vert_sum < y:
        print("No")
    elif (side_sum - x) % 2 == 1 or (vert_sum - y) % 2 == 1:
        print("No")
    else:
        if side_DP[(side_sum - x)//2] and vert_DP[(vert_sum - y)//2]:
            print("Yes")
        else:
            print("No")

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def main():
    order_F = []
    order_F = input().rstrip().split('T')
    x, y = map(int, input().split())
    vert_DP = [False] * 8001
    side_DP = [False] * 8001
    vert_DP[0] = True
    side_DP[0] = True
    vert_sum = 0
    side_sum = 0
    distance = [len(order_F[i]) for i in range(len(order_F))]
    order_len = len(order_F)
    x -= len(order_F[0])
    for i in range(1, order_len):
        if i % 2 == 0:
            side_sum += distance[i]
            for j in reversed(range(8001 - distance[i])):
                if side_DP[j]:
                    side_DP[j + distance[i]] = True
        else:
            vert_sum += distance[i]
            for j in reversed(range(8001 - distance[i])):
                if vert_DP[j]:
                    vert_DP[j + distance[i]] = True
    if side_sum < x or vert_sum < y:
        print("No")
    elif (side_sum - x) % 2 == 1 or (vert_sum - y) % 2 == 1:
        print("No")
    else:
        if side_DP[(side_sum - x)//2] and vert_DP[(vert_sum - y)//2]:
            print("Yes")
        else:
            print("No")

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def main():
    order_F = []
    order_F = input().rstrip().split('T')
    x, y = map(int, input().split())
    vert_DP = [False] * 8001
    side_DP = [False] * 8001
    vert_DP[0] = True
    side_DP[0] = True
    vert_sum = 0
    side_sum = 0
    x -= len(order_F[0])
    for i in range(1, len(order_F)):
        distance = len(order_F[i])
        if i % 2 == 0:
            side_sum += distance
            for j in reversed(range(8001 - distance)):
                if side_DP[j]:
                    side_DP[j + distance] = True
        else:
            vert_sum += distance
            for j in reversed(range(8001 - distance)):
                if vert_DP[j]:
                    vert_DP[j + distance] = True
    if side_sum < x or vert_sum < y:
        print("No")
    elif (side_sum - x) % 2 == 1 or (vert_sum - y) % 2 == 1:
        print("No")
    else:
        if side_DP[(side_sum - x)//2] and vert_DP[(vert_sum - y)//2]:
            print("Yes")
        else:
            print("No")

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
s = input()
n = len(s)
xy = tuple(map(int, input().split()))

# 各ターンで、後何回動けるか
move = [0]
for i in range(n):
    if s[-i-1]=='F':
        move.append(move[-1]+1)
    else:
        move.append(move[-1])
move.reverse()

# 各ターンで行きうる位置
dp = [set() for j in range(n+1)]
dp[0].add((0,0,0))

if move[0]%2!=(sum(xy))%2:
    print('No')
    exit()

for i in range(n):
    for x, y, z in dp[i]:
        if abs(xy[0] - x) + abs(xy[1] - y) > move[i]:
            continue
        if s[i]=='F':
                if z==0:
                    dp[i+1].add((x+1,y,z))
                elif z==1:
                    dp[i+1].add((x,y+1,z))
                elif z==2:
                    dp[i+1].add((x-1,y,z))
                else:
                    dp[i+1].add((x,y-1,z))
        else:
                if z==0:
                    dp[i+1].add((x,y,1))
                    dp[i+1].add((x,y,3))
                elif z==3:
                    dp[i+1].add((x,y,0))
                    dp[i+1].add((x,y,2))
                else:
                    dp[i+1].add((x,y,z-1))
                    dp[i+1].add((x,y,z+1))

for x,y,z in dp[n]:
    if xy == (x,y):
        print('Yes')
        exit()

print('No')

Submission status: Time Limit Exceeded

Solution code:
s = input()
n = len(s)
xy = tuple(map(int, input().split()))

dp = [set() for j in range(n+1)]

dp[0].add((0,0,0))

for i in range(n):
    if s[i]=='F':
        for x,y,z in dp[i]:
            if abs(xy[0]-x)+abs(xy[1]-y)>n-i:
                continue
            if z==0:
                dp[i+1].add((x+1,y,z))
            elif z==1:
                dp[i+1].add((x,y+1,z))
            elif z==2:
                dp[i+1].add((x-1,y,z))
            else:
                dp[i+1].add((x,y-1,z))
    else:
        for x,y,z in dp[i]:
            if abs(xy[0]-x)+abs(xy[1]-y)>n-i:
                continue
            if z==0:
                dp[i+1].add((x,y,1))
                dp[i+1].add((x,y,3))
            elif z==3:
                dp[i+1].add((x,y,0))
                dp[i+1].add((x,y,2))
            else:
                dp[i+1].add((x,y,z-1))
                dp[i+1].add((x,y,z+1))

for x,y,z in dp[n]:
    if xy == (x,y):
        print('Yes')
        exit()

print('No')

Submission status: Time Limit Exceeded

Solution code:
s = input()
n = len(s)
xy = tuple(map(int, input().split()))

dp = [set() for j in range(n+1)]

dp[0].add((0,0,0))

for i in range(n):
    if s[i]=='F':
        for x,y,z in dp[i]:
            if z==0:
                dp[i+1].add((x+1,y,z))
            elif z==1:
                dp[i+1].add((x,y+1,z))
            elif z==2:
                dp[i+1].add((x-1,y,z))
            else:
                dp[i+1].add((x,y-1,z))
    else:
        for x,y,z in dp[i]:
            if z==0:
                dp[i+1].add((x,y,1))
                dp[i+1].add((x,y,3))
            elif z==3:
                dp[i+1].add((x,y,0))
                dp[i+1].add((x,y,2))
            else:
                dp[i+1].add((x,y,z-1))
                dp[i+1].add((x,y,z+1))

for x,y,z in dp[n]:
    if xy == (x,y):
        print('Yes')
        exit()

print('No')

Submission status: Time Limit Exceeded

Solution code:
s = input()
n = len(s)
xy = tuple(map(int, input().split()))

dp = [[set() for i in range(4)] for j in range(n+1)]

dp[0][0].add((0,0))

for i in range(n):
    if s[i]=='F':
        for j in range(4):
            for x,y in dp[i][j]:
                if j ==0:
                    dp[i+1][j].add((x+1,y))
                elif j == 1:
                    dp[i+1][j].add((x,y+1))
                elif j == 2:
                    dp[i+1][j].add((x-1,y))
                else:
                    dp[i+1][j].add((x,y-1))
    else:
        for j in range(4):
            for x,y in dp[i][j]:
                if j!=3:
                    dp[i+1][j+1].add((x,y))
                    dp[i+1][j-1].add((x,y))
                else:
                    dp[i+1][0].add((x,y))
                    dp[i+1][j-1].add((x,y))



for i in range(4):
    if xy in dp[-1][i]:
        print('Yes')
        exit()
print('No')

Submission status: Time Limit Exceeded

Solution code:
S=input()
x,y=map(int,input().split())
Xmove=[]
Ymove=[]
xdist=True
cnt=0
for i in range(len(S)):
  if S[i]=="T":
    if xdist:
      Xmove.append(cnt)
    else:
      Ymove.append(cnt)
    cnt=0
    xdist^=True
  else:
    cnt+=1
if S[-1]=="F":
  if xdist:
    Xmove.append(cnt)
  else:
    Ymove.append(cnt)

Xmax=sum(Xmove)
Ymax=sum(Ymove)
dpX=[[False for j in range(Xmax*2+10)] for i in range(len(Xmove)+1)]
dpY=[[False for j in range(Ymax*2+10)] for i in range(len(Ymove)+1)]

indX=0
if S[0]=="F":
  dpX[1][Xmax+Xmove[0]]=True
  indX=1
else:
  dpX[0][Xmax]=True
dpY[0][Ymax]=True

for i in range(indX,len(Xmove)):
  for j in range(len(dpX[i])):
    if dpX[i][j]:
      dpX[i+1][j-Xmove[i]]=True
      dpX[i+1][j+Xmove[i]]=True

if not dpX[-1][x+Xmax]:
  print("No")
  exit(0)

for i in range(len(Ymove)):
  for j in range(len(dpY[i])):
    if dpY[i][j]:
      dpY[i+1][j+Ymove[i]]=True
      dpY[i+1][j-Ymove[i]]=True

print(("No","Yes")[dpY[-1][y+Ymax]])

Submission status: Time Limit Exceeded

Solution code:
S=input()
x,y=map(int,input().split())
Xmove=[]
Ymove=[]
xdist=True
cnt=0
for i in range(len(S)):
  if S[i]=="T":
    if xdist:
      Xmove.append(cnt)
    else:
      Ymove.append(cnt)
    cnt=0
    xdist^=True
  else:
    cnt+=1
if S[-1]=="F":
  if xdist:
    Xmove.append(cnt)
  else:
    Ymove.append(cnt)

dpX=[[False for j in range(16001)] for i in range(len(Xmove)+1)]
dpY=[[False for j in range(16001)] for i in range(len(Ymove)+1)]

indX=0
if S[0]=="F":
  dpX[1][8000+Xmove[0]]=True
  indX=1
else:
  dpX[0][8000]=True
dpY[0][8000]=True

for i in range(indX,len(Xmove)):
  for j in range(len(dpX[i])):
    if dpX[i][j]:
      dpX[i+1][j-Xmove[i]]=True
      dpX[i+1][j+Xmove[i]]=True


if not dpX[-1][x+8000]:
  print("No")
  exit(0)

for i in range(len(Ymove)):
  for j in range(len(dpY[i])):
    if dpY[i][j]:
      dpY[i+1][j+Ymove[i]]=True
      dpY[i+1][j-Ymove[i]]=True

print(("No","Yes")[dpY[-1][y+8000]])

Submission status: Time Limit Exceeded

Solution code:
s = input()
x,y = map(int, input().split())
dp = [[[False]*(len(s)*4+1) for _ in range(2)] for _ in range(2)]
 
dp[0][0][0] = True
dp[0][1][0] = True
#print(dp)
index = 0
while index < len(s) and s[index] == 'F':
  index += 1
x -= index
xy_axis = 1
dp_index = 1
i = index+1
while i < len(s):
  num = 0
  while i < len(s) and s[i] == 'F':
    num += 1
    i += 1
  #print(num)
  for j in range(-len(s), len(s)+1):
    dp[dp_index][xy_axis][j] = dp[(dp_index+1)%2][xy_axis][j-num] or dp[(dp_index+1)%2][xy_axis][j+num]
  xy_axis = (xy_axis+1) % 2
  if xy_axis == 1:
      dp_index = (dp_index+1) % 2
  i += 1
 
#print(dp)
 
if dp[(dp_index + 1) % 2][0][x] and dp[(dp_index + xy_axis) % 2][1][y]:
  print('Yes')
else:
  print('No')

Submission status: Time Limit Exceeded

Solution code:
s = input()
x,y = map(int, input().split())
dp = [[[0]*(len(s)*4+1) for _ in range(2)] for _ in range(2)]

dp[0][0][0] = 1
dp[0][1][0] = 1
#print(dp)
index = 0
while index < len(s) and s[index] == 'F':
  index += 1
x -= index
xy_axis = 1
dp_index = 1
i = index+1
while i < len(s):
  num = 0
  while i < len(s) and s[i] == 'F':
    num += 1
    i += 1
  #print(num)
  for j in range(-len(s), len(s)+1):
    dp[dp_index][xy_axis][j] = dp[(dp_index+1)%2][xy_axis][j-num] | dp[(dp_index+1)%2][xy_axis][j+num]
  xy_axis = (xy_axis+1) % 2
  if xy_axis == 1:
      dp_index = (dp_index+1) % 2
  i += 1

#print(dp)

if dp[(dp_index + 1) % 2][0][x] & dp[(dp_index + xy_axis) % 2][1][y] == 1:
  print('Yes')
else:
  print('No')

Submission status: Time Limit Exceeded

Solution code:
# 盤面座標は8000x8000(x 2)
N = 8000
s = input()
target_x, target_y = map(int, input().split())

# "FTTFF" -> [1, 0, 2]と変換。'F1TF0TF2T'のFだけとる
dat_f = [len(Fcount) for Fcount in s.split("T")]

# マイナスを含むxとyのDP用配列(=x2)を作る +1するのは原点用
# x, yの閾値判定するのが面倒なので倍(=x2)用意する(index error対策)
curmap_x = [False] * ((N * 2 * 2) + 1)
curmap_y = [False] * ((N * 2 * 2) + 1)
nextmap_x = [False] * ((N * 2 * 2) + 1)
nextmap_y = [False] * ((N * 2 * 2) + 1)

# 初期座標 0,0なのだが、最初Fから始まる場合は(x,0)から始まるし、y軸を向きながら処理する
if s[0] == "F":
    start = 1
    curmap_x[N * 2 + dat_f[0]] = True
    direction_x = False
else:
    start = 0
    curmap_x[N * 2] = True
    direction_x = True

# y=0
curmap_y[N * 2] = True

# 処理すべき最初のFから
for i in range(start, len(dat_f)):
    step = dat_f[i]
    if direction_x:
        for j in range(N, N + (N * 2) + 1):
            nextmap_x[j] = True if curmap_x[j - step] or curmap_x[j + step] else False
        curmap_x, nextmap_x = nextmap_x, curmap_x
    else:
        for j in range(N, N + (N * 2) + 1):
            nextmap_y[j] = True if curmap_y[j - step] or curmap_y[j + step] else False
        curmap_y, nextmap_y = nextmap_y, curmap_y

    # くる
    direction_x = not direction_x

print("Yes" if curmap_x[N * 2 + target_x] and curmap_y[N * 2 + target_y] else "No")

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

S = input()
N = len(S)
X, Y = MAP()

# ランレングス圧縮
A1, A2 = [], []
cnt = d = 0
for s in S:
    if s == 'T':
        if d == 0:
            A1.append(cnt)
        else:
            A2.append(cnt)
        cnt = 0
        d ^= 1
    else:
        cnt += 1
if d == 0:
    A1.append(cnt)
else:
    A2.append(cnt)
# 最初だけ右固定なので別処理
X -= A1[0]
A1.pop(0)

# 縦横独立に、到達可の場所を確認する
M1 = len(A1)
M2 = len(A2)
dpx = [set() for i in range(M1+1)]
dpy = [set() for i in range(M2+1)]
dpx[0].add(0)
dpy[0].add(0)
for i, a in enumerate(A1):
    for x in dpx[i]:
        dpx[i+1].add(x+a)
        dpx[i+1].add(x-a)
for i, a in enumerate(A2):
    for y in dpy[i]:
        dpy[i+1].add(y+a)
        dpy[i+1].add(y-a)

if X in dpx[M1] and Y in dpy[M2]:
    Yes()
else:
    No()

Submission status: Time Limit Exceeded

Solution code:
      #FT robot
s=input()
gx,gy=map(int,input().split())
lists=list(s.split("T"))
xlist=[]
ylist=[]
if s[0]=="T":
    for i in range(len(lists)):
        if i%2==0:
            xlist.append(len(lists[i]))
        else:
            ylist.append(len(lists[i]))
elif s[0]=="F":
    for i in range(len(lists)):
        if i%2==0:
            xlist.append(len(lists[i]))
        else:
            ylist.append(len(lists[i]))
    gx-=xlist[0]
    del xlist[0]
Xsum=sum(xlist)
Ysum=sum(ylist)


if (Xsum+gx)%2!=0 or (Ysum+gy)%2!=0:
    print("No")   
else:
    gx1=(Xsum+gx)//2
    gx2=(Xsum-gx)//2
    gy1=(Ysum+gy)//2
    gy2=(Ysum-gy)//2
    dpx=[[False for i in range(Xsum+2)] for j in range(len(xlist)+2)]
    dpy=[[False for i in range(Ysum+2)] for j in range(len(ylist)+2)]
    #dpx[i][j]でi番目のカードまでを足して、値ｊを取れるか判定する
    dpx[0][0]=True
    dpy[0][0]=True
    for i in range(len(xlist)):
        for j in range(Xsum+2):
            dpx[i+1][j]=dpx[i][j-xlist[i]] or dpx[i][j]
    for i in range(len(ylist)):
        for j in range(Ysum+2):
            dpy[i+1][j]=dpy[i][j-ylist[i]] or dpy[i][j]    
    #ここまではあってそうなことがわかった
    flag1=False
    if 0<= gy1<= Ysum:   
        if dpy[len(ylist)][gy1]:
            flag1=True
    flag2=False
    if 0<=gy2<= Ysum :
        if dpy[len(ylist)][gy2]:
            flag2=True
    flag3=False
    if 0<=gx1<= Xsum:
        if dpx[len(xlist)][gx1]:
            flag3=True
    flag4=False
    if 0<=gx2<= Xsum:
        if dpx[len(xlist)][gx2]:
            flag4=True
    if (flag1 or flag2) and (flag3 or flag4):
        print("Yes")
    else:
        print("No")

Submission status: Time Limit Exceeded

Solution code:
#FT robot
s=input()
gx,gy=map(int,input().split())
lists=list(s.split("T"))
xlist=[]
ylist=[]
if s[0]=="T":
    for i in range(len(lists)):
        if i%2==0:
            xlist.append(len(lists[i]))
        else:
            ylist.append(len(lists[i]))
elif s[0]=="F":
    for i in range(len(lists)):
        if i%2==0:
            xlist.append(len(lists[i]))
        else:
            ylist.append(len(lists[i]))
    gx-=xlist[0]
    del xlist[0]
    
for some in xlist:
    some=abs(some)
for some in ylist:
    some=abs(some)
Xsum=sum(xlist)
Ysum=sum(ylist)
if (Xsum+gx)%2!=0 or (Ysum+gy)%2!=0:
    print("No")
    
else:
    gx1=(Xsum+gx)//2
    gx2=(Xsum-gx)//2
    gy1=(Ysum+gy)//2
    gy2=(Ysum-gy)//2
    dpx=[[False for i in range(8001)] for i in range(len(xlist)+2)]
    dpy=[[False for i in range(8001)] for j in range(len(ylist)+2)]
    #dpx[i][j]でi番目のカードまでを足して、値ｊを取れるか判定する
    dpx[0][0]=True
    dpy[0][0]=True
    for i in range(len(xlist)):
        for j in range(8001):
            dpx[i+1][j]=dpx[i][j-xlist[i]] or dpx[i][j]
    for i in range(len(ylist)):
        for j in range(8001):
            dpy[i+1][j]=dpy[i][j-ylist[i]] or dpy[i][j]        
    if (dpy[len(ylist)][gy1] or dpy[len(ylist)][gy2]) and (dpx[len(xlist)][gx1] or dpx[len(xlist)][gx2]):
        print("Yes")
    else:
        print("No")