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:
import sys
s = input()
gx,gy = map(int, input().split(' '))
x_d = [0]
y_d = []
cnt = 0
for i in range(len(s)):
    if s[i] == "T":
        cnt += 1
        if cnt % 2 == 0:
            x_d.append(0)
        elif cnt % 2 == 1:
            y_d.append(0)
    if s[i] == "F":
        if cnt % 2 == 0:
            x_d[-1] += 1
        elif cnt % 2 == 1:
            y_d[-1] += 1
gx -= x_d[0]
x_d[0] = 0
x_d.append(0)
y_d.append(0)
if (sum(x_d)-gx) % 2 or (sum(y_d)-gy) % 2 or sum(x_d) < abs(gx) or sum(y_d) < abs(gy):
    print("No")
    sys.exit()
x_n = (sum(x_d)-gx)//2
y_n = (sum(y_d)-gy)//2
DPx = [[False for i in range(x_n+2)] for j in range(len(x_d))]
DPy = [[False for i in range(y_n+2)] for j in range(len(y_d))]
for x in DPx:
    x[0] = True
for y in DPy:
    y[0] = True
for i in range(len(x_d)-1):
    for j in range(x_n+1):
        if DPx[i][j]:
            DPx[i+1][j] = True
            if j+x_d[i] <= x_n+1:
                DPx[i+1][j+x_d[i]] = True
for i in range(len(y_d)-1):
    for j in range(y_n+1):
        if DPy[i][j]:
            DPy[i+1][j] = True
            if j+y_d[i] <= y_n+1:
                DPy[i+1][j+y_d[i]] = True
if DPx[len(x_d)-1][x_n] and DPy[len(y_d)-1][y_n]:
    print("Yes")
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
S=input()
x,y=map(int,input().split())
xmove=[]
ymove=[]
x_dir=True
import itertools
first=True
for key,g in itertools.groupby(S):
  g=list(g)
  if key=="F":
    if first:
      x-=len(g)
    elif x_dir:
      xmove.append(len(g))
    else:
      ymove.append(len(g))
  elif key=="T":
    if len(g)%2==1:
      x_dir^=True
  first=False
  
stackX=[]
# index, move
XisOK=False
stackX.append([0,0])
while stackX:
  node=stackX.pop()
  ind=node[0]
  move=node[1]
  if ind==len(xmove):
    if x==move:
      XisOK=True
      break
    else:
      continue
  stackX.append([ind+1,move+xmove[ind]])
  stackX.append([ind+1,move+xmove[ind]*(-1)])
  
if not XisOK:
  print("No")
  exit(0)

stackY=[]
# index, move
YisOK=False
stackY.append([0,0])
while stackY:
  node=stackY.pop()
  ind=node[0]
  move=node[1]
  if ind==len(ymove):
    if y==move:
      YisOK=True
      break
    else:
      continue
  stackY.append([ind+1,move+ymove[ind]])
  stackY.append([ind+1,move+ymove[ind]*(-1)])

if YisOK:
  print("Yes")
else:
  print("No")

Submission status: Time Limit Exceeded

Solution code:
# D - FT Robot

import sys
sys.setrecursionlimit(100000000)

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

f = []
F_counter = 0
for i in range(len(s)):
    if s[i] == "F":
        F_counter += 1
    else:
        f.append(F_counter)
        F_counter = 0
f.append(F_counter)
        
def dp_x(X, f_idx):
    if f_idx == 0:
        return X == f[0]
    elif f_idx % 2 == 1:
        return dp_x(X, f_idx-1)
    else:
        return dp_x(X-f[f_idx], f_idx-2) or dp_x(X+f[f_idx], f_idx-2)
    
def dp_y(Y, f_idx):
    if f_idx == 0:
        return Y == 0
    elif f_idx == 1:
        return Y == f[1] or Y == -f[1]
    elif f_idx % 2 == 0:
        return dp_y(Y, f_idx-1)
    else:
        return dp_y(Y-f[f_idx], f_idx-2) or dp_y(Y+f[f_idx], f_idx-2)
    
print("Yes" if dp_x(x, len(f)-1) and dp_y(y, len(f)-1) else "No")

Submission status: Time Limit Exceeded

Solution code:
# D - FT Robot

from collections import deque
import copy

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

if len(s) == 1:
    if (s[0] == "F" and (x, y) == (1, 0)) or (s[0] == "T" and (x, y) == (0, 0)):
        print("Yes")
    else:
        print("No")
    exit()

zipped_s = []
count = 1
for idx in range(len(s) - 1):
    if s[idx] == s[idx+1]:
        count += 1
    else:
        zipped_s.append((s[idx], count))
        count = 1
zipped_s.append((s[-1], count))

n_move = s.count("F")

robot = deque([[[0,0], 0, 0, n_move]]) # 現在地、これから行うzipped_sの操作のインデックス、向き、残り移動回数
while robot:
    r = robot.pop()
    if r[1] == len(zipped_s):
        if r[0] == [x, y]:
            print("Yes")
            exit()
        else:
            continue
    elif r[3] < (abs(r[0][0] - x) + abs(r[0][1] - y)):
        continue
    elif zipped_s[r[1]][0] == "F":
        if r[2] == 0:
            r[0][0] += zipped_s[r[1]][1]
        elif r[2] == 1:
            r[0][1] += zipped_s[r[1]][1]
        elif r[2] == 2:
            r[0][0] -= zipped_s[r[1]][1]
        else:
            r[0][1] -= zipped_s[r[1]][1]
        r[3] -= zipped_s[r[1]][1]
        r[1] += 1
        robot.append(r)
    else:
        if zipped_s[r[1]][1] % 2 == 0:
            r[1] += 1
            robot.append(r)
            r2 = copy.deepcopy(r)
            r2[2] = (r2[2] + 2) % 4
            robot.append(r2)
        else:
            r[1] += 1
            r2 = copy.deepcopy(r)
            r[2] = (r[2] + 1) % 4
            robot.append(r)
            r2[2] = (r2[2] + 3) % 4
            robot.append(r2)
print("No")

Submission status: Time Limit Exceeded

Solution code:
# D - FT Robot

from collections import deque
import copy

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

if len(s) == 1:
    if (s[0] == "F" and (x, y) == (1, 0)) or (s[0] == "T" and (x, y) == (0, 0)):
        print("Yes")
    else:
        print("No")
    exit()

zipped_s = []
count = 1
for idx in range(len(s) - 1):
    if s[idx] == s[idx+1]:
        count += 1
    else:
        zipped_s.append((s[idx], count))
        count = 1
zipped_s.append((s[-1], count))

robot = deque([[[0,0], 0, 0]])
while robot:
    r = robot.pop()
    if r[1] == len(zipped_s):
        if r[0] == [x, y]:
            print("Yes")
            exit()
        else:
            continue
    elif zipped_s[r[1]][0] == "F":
        if r[-1] == 0:
            r[0][0] += zipped_s[r[1]][1]
        elif r[-1] == 1:
            r[0][1] += zipped_s[r[1]][1]
        elif r[-1] == 2:
            r[0][0] -= zipped_s[r[1]][1]
        else:
            r[0][1] -= zipped_s[r[1]][1]
        r[1] += 1
        robot.append(r)
    else:
        if zipped_s[r[1]][1] % 2 == 0:
            r[1] += 1
            robot.append(r)
            r2 = copy.deepcopy(r)
            r2[2] = (r2[2] + 2) % 4
            robot.append(r2)
        else:
            r[1] += 1
            r2 = copy.deepcopy(r)
            r[2] = (r[2] + 1) % 4
            robot.append(r)
            r2[2] = (r2[2] + 3) % 4
            robot.append(r2)
print("No")

Submission status: Time Limit Exceeded

Solution code:
s=[len(c) for c in list(input().split("T"))]
x,y=map(int,input().split())
XX=s[::2]
YY=s[1::2]
X=[XX[0]]
Y=[0]
XXX=[]
for i in range(1,len(XX)):
    for j in X:
        XXX.append(j+XX[i])
        XXX.append(j-XX[i])
    X=XXX
    XXX=[]

YYY=[]
for i in range(len(YY)):
    for j in Y:
        YYY.append(j+YY[i])
        YYY.append(j-YY[i])
    Y=YYY
    YYY=[]

if x in X and y in Y:
    print("Yes")
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys

YES = "Yes"  # type: str
NO = "No"  # type: str

def solve(s: str, x: int, y: int):
    LENS = len(s)
    s_list = list(map(len,s.split("T")))
    x_s_list = s_list[0::2]
    y_s_list = s_list[1::2]

    x_dp = [[False]*(2*LENS+1) for _ in range(len(x_s_list))]
    ## answer = x_dp[-1][x+LENS]
    for index,count in enumerate(x_s_list):
        ## 最初は
        if index == 0:
            x_dp[index][count+LENS] = True
            continue
        
        for j in range(2*LENS+1):
            if j-count >= 0 and j+count< 2*LENS+1:
                x_dp[index][j] = x_dp[index-1][j-count] or x_dp[index-1][j+count] 
            elif j-count >= 0:
                x_dp[index][j] = x_dp[index-1][j-count]
            elif j+count< 2*LENS+1:
                x_dp[index][j] = x_dp[index-1][j+count]


    y_dp = [[False]*(2*LENS+1) for _ in range(len(y_s_list))]
    for index,count in enumerate(y_s_list):
        ## 最初は
        if index == 0:
            y_dp[index][count+LENS] = True
            y_dp[index][-count+LENS] = True            
            continue
        
        for j in range(2*LENS+1):
            if j-count >= 0 and j+count< 2*LENS+1:
                y_dp[index][j] = y_dp[index-1][j-count] or y_dp[index-1][j+count] 
            elif j-count >= 0:
                y_dp[index][j] = y_dp[index-1][j-count]
            elif j+count< 2*LENS+1:
                y_dp[index][j] = y_dp[index-1][j+count]
    
    if not y_dp:
        if y != 0:
            print(NO)
        else:
            if x_dp[-1][x+LENS]:
                print(YES)
            else:
                print(NO)
        return

    if not x_dp:
        if x != 0:
            print(NO)
        else:
            if y_dp[-1][y+LENS]:
                print(YES)
            else:
                print(NO)
        return

    if x_dp[-1][x+LENS] and y_dp[-1][y+LENS]:
        print(YES)
    else:
        print(NO)

    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    s = next(tokens)  # type: str
    x = int(next(tokens))  # type: int
    y = int(next(tokens))  # type: int
    solve(s, x, y)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

    lf = [0]
    tf = 0
    for i in range(len(s)):
        if s[i] =="F":
            lf[tf] += 1
        else:
            lf.append(0)
            tf += 1

    lx = [lf[i] for i in range(len(lf)) if i % 2 == 0]
    ly = [lf[i] for i in range(len(lf)) if i % 2 == 1]
    start =lx.pop(0)
    dpx = [[False for _ in range(20000)] for _ in range(len(lx)+1)]
    dpx[0][start+10000] = True
    for i in range(len(lx)):
        for j in range(20000):
            if j-lx[i] >= 0:
                dpx[i+1][j] = dpx[i][j-lx[i]]
            if j+lx[i] < 20000:
                dpx[i+1][j] = dpx[i+1][j] or dpx[i][j+lx[i]]

    dpy = [[False for _ in range(20000)] for _ in range(len(ly)+1)]
    dpy[0][10000] = True
    for i in range(len(ly)):
        for j in range(20000):
            if j-ly[i] >= 0:
                dpy[i+1][j] = dpy[i][j-ly[i]]
            if j+ly[i] < 20000:
                dpy[i+1][j] = dpy[i+1][j] or dpy[i][j+ly[i]]

    if dpx[-1][x+10000] and dpy[-1][y+10000]:return "Yes"
    else:return "No"

print(main())

Submission status: Time Limit Exceeded

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

lf = [0]
tf = 0
for i in range(len(s)):
    if s[i] =="F":
        lf[tf] += 1
    else:
        lf.append(0)
        tf += 1

lx = [lf[i] for i in range(len(lf)) if i % 2 == 0]
ly = [lf[i] for i in range(len(lf)) if i % 2 == 1]
start =lx.pop(0)
dpx = [[False for _ in range(20000)] for _ in range(len(lx)+1)]
dpx[0][start+10000] = True
for i in range(len(lx)):
    for j in range(20000):
        if j-lx[i] >= 0:
            dpx[i+1][j] = dpx[i][j-lx[i]]
        if j+lx[i] < 20000:
            dpx[i+1][j] = dpx[i+1][j] or dpx[i][j+lx[i]]

dpy = [[False for _ in range(20000)] for _ in range(len(ly)+1)]
dpy[0][10000] = True
for i in range(len(ly)):
    for j in range(20000):
        if j-ly[i] >= 0:
            dpy[i+1][j] = dpy[i][j-ly[i]]
        if j+ly[i] < 20000:
            dpy[i+1][j] = dpy[i+1][j] or dpy[i][j+ly[i]]

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(9000)
s = input()
x, y = map(int, input().split())
finished = []

def dfs(now, index, direction):
    if index == len(s)-1:
        if s[index] == 'T':
            finished.append(now)
            return
        elif s[index] == 'F':
            if direction==1:
                nowx, nowy = now
                next = (nowx+1, nowy)
                finished.append(next)
                return
            elif direction==2:
                nowx, nowy = now
                next = (nowx, nowy+1)
                finished.append(next)
                return
            elif direction==3:
                nowx, nowy = now
                next = (nowx-1, nowy)
                finished.append(next)
                return
            elif direction==0:
                nowx, nowy = now
                next = (nowx, nowy-1)
                finished.append(next)
                return

    if s[index] == 'F':
        if direction==1:
            nowx, nowy = now
            next = (nowx+1, nowy)
            dfs(next, index+1, direction)

        elif direction==2:
            nowx, nowy = now
            next = (nowx, nowy+1)
            dfs(next, index+1, direction)

        elif direction==3:
            nowx, nowy = now
            next = (nowx-1, nowy)
            dfs(next, index+1, direction)

        elif direction==0:
            nowx, nowy = now
            next = (nowx, nowy-1)
            dfs(next, index+1, direction)

    elif s[index] == 'T':
        direction1 = (direction + 1)%4
        direction2 = (direction - 1)%4
        dfs(now, index+1, direction1)
        dfs(now, index+1, direction2)


now = (0, 0)
direction = 1
dfs(now, 0, direction)
if (x, y) in finished:
    print('Yes')
else:
    print('No')

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
from itertools import accumulate
def main():
    import itertools
    def eratosthenes_sieve(n):
        table = [0] * (n + 1)
        prime_list = []
        for i in range(2, n + 1):
            if table[i] == 0:
                prime_list.append(i)
                for j in range(i + i, n + 1, i):
                    table[j] = 1
        return prime_list
        def inputs():return (int(x) for x in input().split())
    input = sys.stdin.readline
    def inputs():
        return [int(x) for x in input().split()]
    S = input()
    x,y=inputs()
    cnt=0
    s =[]
    if S[0]=="T":
        s.append(0)
        cnt+=1
    else:
        cnt+=1
    for i in range(len(S)-2):
        if S[i]==S[i+1]:
            cnt+=1
        else:
            s.append(cnt)
            cnt=1
    s.append(cnt)
    flag=1
    x1 = []
    y1 = []
    t= 0
    for i in range(len(s)):
        if i%2==0:
            if flag==1:
              if i!=0:
                x1.append(s[i])
            else:
                y1.append(s[i])
        else:
            flag=(flag+s[i])%2
            t+=s[i]
    x2 = sum(x1)+s[0]
    y2= sum(y1)
    if abs(x)>x2 or abs(y)>y2:
      print("No")
      exit()
    m = max(x2,y2,t)
    dpx=[[-1]*(m*2+5) for i in range(len(x1)+1)]
    dpx[0][m+s[0]]=1
    dpy =[[-1]*(m*2+5) for i in range(len(y1)+1)]
    dpy[0][m]=1
    for i in range(len(x1)):
        for j in range(m*2):
          if dpx[i][j]!=-1:
            if j+x1[i]<=(m)*2:
                dpx[i+1][j+x1[i]]=1
            if j-x1[i]>=0:
                dpx[i+1][j-x1[i]]=1      
    for i in range(len(y1)):
        for j in range(m*2):
          if dpy[i][j]!=-1:
            if j+y1[i]<=m*2:
                dpy[i+1][j+y1[i]]=1
                #print(j+y1[i])
            if j-y1[i]>=0:
                dpy[i+1][j-y1[i]]=1
                #print(j-y1[i])
    if dpx[len(x1)][m+x]==1 and dpy[len(y1)][m+y]==1:
        print("Yes")
    else:
        print("No")
main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
from itertools import accumulate
def main():
    import itertools
    def eratosthenes_sieve(n):
        table = [0] * (n + 1)
        prime_list = []
        for i in range(2, n + 1):
            if table[i] == 0:
                prime_list.append(i)
                for j in range(i + i, n + 1, i):
                    table[j] = 1
        return prime_list
        def inputs():return (int(x) for x in input().split())
    input = sys.stdin.readline
    def inputs():
        return [int(x) for x in input().split()]
    S = input()
    x,y=inputs()
    cnt=0
    s =[]
    if S[0]=="T":
        s.append(0)
        cnt+=1
    else:
        cnt+=1
    for i in range(len(S)-2):
        if S[i]==S[i+1]:
            cnt+=1
        else:
            s.append(cnt)
            cnt=1
    s.append(cnt)
    flag=1
    x1 = []
    y1 = []
    for i in range(len(s)):
        if i%2==0:
            if flag==1:
              if i!=0:
                x1.append(s[i])
            else:
                y1.append(s[i])
        else:
            flag=(flag+s[i])%2
    x2 = sum(x1)
    y2= sum(y1)
    dpx=[[-1]*((x2+s[0])*2+5) for i in range(len(x1)+1)]
    dpx[0][x2+s[0]+s[0]]=1
    dpy =[[-1]*(y2*2+5) for i in range(len(y1)+1)]
    dpy[0][sum(y1)]=1
    for i in range(len(x1)):
        for j in range((x2+s[0])*2):
            if j+x1[i]<=(x2+s[0])*2 and dpx[i][j]!=-1:
                dpx[i+1][j+x1[i]]=1
            if j-x1[i]>=0 and dpx[i][j]!=-1:
                dpx[i+1][j-x1[i]]=1      
    for i in range(len(y1)):
        for j in range(y2*2):
            if j+y1[i]<=y2*2 and dpy[i][j]!=-1:
                dpy[i+1][j+y1[i]]=1
                #print(j+y1[i])
            if j-y1[i]>=0 and dpy[i][j]!=-1:
                dpy[i+1][j-y1[i]]=1
                #print(j-y1[i])
    if dpx[len(x1)][x2+s[0]+x]==1 and dpy[len(y1)][y2+y]==1:
        print("Yes")
    else:
        print("No")
main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
from itertools import accumulate
def main():
    import itertools
    def eratosthenes_sieve(n):
        table = [0] * (n + 1)
        prime_list = []
        for i in range(2, n + 1):
            if table[i] == 0:
                prime_list.append(i)
                for j in range(i + i, n + 1, i):
                    table[j] = 1
        return prime_list
        def inputs():return (int(x) for x in input().split())
    input = sys.stdin.readline
    def inputs():
        return [int(x) for x in input().split()]
    S = input()
    x,y=inputs()
    cnt=0
    s =[]
    if S[0]=="T":
        s.append(0)
        cnt+=1
    else:
        cnt+=1
    for i in range(len(S)-2):
        if S[i]==S[i+1]:
            cnt+=1
        else:
            s.append(cnt)
            cnt=1
    s.append(cnt)
    flag=1
    x1 = []
    y1 = []
    for i in range(len(s)):
        if i%2==0:
            if flag==1:
              if i!=0:
                x1.append(s[i])
            else:
                y1.append(s[i])
        else:
            flag=(flag+s[i])%2
    dpx=[[-1]*((sum(x1)+s[0])*2+5) for i in range(len(x1)+1)]
    dpx[0][sum(x1)+s[0]]=1
    dpy =[[-1]*(sum(y1)*2+5) for i in range(len(y1)+1)]
    dpy[0][sum(y1)]=1
    for i in range(len(x1)):
        for j in range((sum(x1)+s[0])*2):
            if j+x1[i]<=(sum(x1)+s[0])*2 and dpx[i][j]!=-1:
                dpx[i+1][j+x1[i]]=1
            if j-x1[i]>=0 and dpx[i][j]!=-1:
                dpx[i+1][j-x1[i]]=1      
    for i in range(len(y1)):
        for j in range(sum(y1)*2):
            if j+y1[i]<=sum(y1)*2 and dpy[i][j]!=-1:
                dpy[i+1][j+y1[i]]=1
                #print(j+y1[i])
            if j-y1[i]>=0 and dpy[i][j]!=-1:
                dpy[i+1][j-y1[i]]=1
                #print(j-y1[i])
    
    if dpx[len(x1)][sum(x1)+x]==1 and dpy[len(y1)][sum(y1)+y]==1:
        print("Yes")
    else:
        print("No")
main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
from itertools import accumulate
def main():
    import itertools
    def eratosthenes_sieve(n):
        table = [0] * (n + 1)
        prime_list = []
        for i in range(2, n + 1):
            if table[i] == 0:
                prime_list.append(i)
                for j in range(i + i, n + 1, i):
                    table[j] = 1
        return prime_list
        def inputs():return (int(x) for x in input().split())
    input = sys.stdin.readline
    def inputs():
        return [int(x) for x in input().split()]
    S = input()
    x,y=inputs()
    cnt=0
    s =[]
    if S[0]=="T":
        s.append(0)
        cnt+=1
    else:
        cnt+=1
    for i in range(len(S)-2):
        if S[i]==S[i+1]:
            cnt+=1
        else:
            s.append(cnt)
            cnt=1
    s.append(cnt)
    flag=1
    x1 = []
    y1 = []
    for i in range(len(s)):
        if i%2==0:
            if flag==1:
              if i!=0:
                x1.append(s[i])
            else:
                y1.append(s[i])
        else:
            flag=(flag+s[i])%2
    dpx=[[-1]*(16001) for i in range(len(x1)+1)]
    dpx[0][8000+s[0]]=1
    dpy =[[-1]*(16001) for i in range(len(y1)+1)]
    dpy[0][8000]=1
    for i in range(len(x1)):
        for j in range(16000):
            if j+x1[i]<=16000 and dpx[i][j]!=-1:
                dpx[i+1][j+x1[i]]=1
            if j-x1[i]>=0 and dpx[i][j]!=-1:
                dpx[i+1][j-x1[i]]=1      
    for i in range(len(y1)):
        for j in range(16000):
            if j+y1[i]<=16000 and dpy[i][j]!=-1:
                dpy[i+1][j+y1[i]]=1
                #print(j+y1[i])
            if j-y1[i]>=0 and dpy[i][j]!=-1:
                dpy[i+1][j-y1[i]]=1
                #print(j-y1[i])
    
    if dpx[len(x1)][8000+x]==1 and dpy[len(y1)][8000+y]==1:
        print("Yes")
    else:
        print("No")
main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
from itertools import accumulate
def main():
    import itertools
    def eratosthenes_sieve(n):
        table = [0] * (n + 1)
        prime_list = []
        for i in range(2, n + 1):
            if table[i] == 0:
                prime_list.append(i)
                for j in range(i + i, n + 1, i):
                    table[j] = 1
        return prime_list
        def inputs():return (int(x) for x in input().split())
    input = sys.stdin.readline
    def inputs():
        return [int(x) for x in input().split()]
    S = list(input())
    x,y=inputs()
    cnt=0
    s =[]
    if S[0]=="T":
        s.append(0)
        cnt+=1
    else:
        cnt+=1
    for i in range(len(S)-2):
        if S[i]==S[i+1]:
            cnt+=1
        else:
            s.append(cnt)
            cnt=1
    s.append(cnt)
    #print(s)
    flag=1
    x1 = []
    y1 = []
    ansx=s[0]
    ansy=0
    flagx=0
    flagy= 0
    #print(s)
    for i in range(len(s)):
        if i%2==0:
            if flag==1:
              if i!=0:
                x1.append(s[i])
            else:
                y1.append(s[i])
        else:
            flag=(flag+s[i])%2
    #print(x1,y1)
    for bit in range(1<<len(x1)):
        ansx = s[0]
        for k in range(len(x1)):
            if bit&(1<<k):
                ansx+=x1[k]
            else:
                ansx-=x1[k]
        if ansx==x:
            flagx=1
            break
    for bit in range(1<<len(y1)):
        ansy = 0
        for k in range(len(y1)):
            if bit&(1<<k):
                ansy+=y1[k]
            else:
                ansy-=y1[k]
        if ansy==y:
            flagy=1
            break
    if flagx and flagy:
        print("Yes")
    else:
        print("No")
main()

Submission status: Time Limit Exceeded

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

s = s.split("T")
s = [len(e) for e in s]
a = []
b = []
for i, s in enumerate(s):
    if i % 2 == 0:
        a.append(s)
    else:
        b.append(s)

x -= a.pop(0)
ans = True

dpx = [[False] * (2*abs(x) + 1) for _ in range(len(a) + 1)]
dpx[0][abs(x)] = True

for i in range(1,len(a)+1):
    for j in range(2*abs(x) + 1):
        if j + a[i-1] < 2*abs(x) + 1:
            dpx[i][j] |= dpx[i-1][j+a[i-1]]
        if j - a[i-1] >= 0:
            dpx[i][j] |= dpx[i-1][j-a[i-1]]

ans &= dpx[len(a)][x+abs(x)]

dpy = [[False] * (2*abs(y) + 1) for _ in range(len(b) + 1)]
dpy[0][abs(y)] = True

for i in range(1, len(b) + 1):
    for j in range(2*abs(y) + 1):
        if j + b[i-1] < 2*abs(y) + 1:
            dpy[i][j] |= dpy[i-1][j+b[i-1]]
        if j - b[i-1] >= 0:
            dpy[i][j] |= dpy[i-1][j-b[i-1]]

ans &= dpy[len(b)][y+abs(y)]

if ans:
    print("Yes")
else:
    print("No")

Submission status: Time Limit Exceeded

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

def main():
    S = list(input())
    X, Y = map(int, input().split())

    Xs = []
    Ys = []
    line = True
    first = True
    x0, y0 = 0, 0
    a = 0
    for s in S:
        if s == 'F':
            a += 1
        else:
            if first:
                if a > 0:
                    x0 = a
                a = 0
                first = False
                line = False
                continue
            if a > 0:
                if line:
                    Xs.append(a)
                else:
                    Ys.append(a)
                a = 0
            if line:
                line = False
            else:
                line = True
    if a > 0:
        if line:
            Xs.append(a)
        else:
            Ys.append(a)

    L = len(S)

    dpx = [[False for _ in range(2*L+1)] for _ in range(len(Xs)+1)]
    dpx[0][x0+L] = True

    for i, x in enumerate(Xs):
        for j in range(2*L+1):
            if j+x <= 2*L:
                dpx[i+1][j+x] = dpx[i][j] or dpx[i+1][j+x]
            if j-x >= 0:
                dpx[i+1][j-x] = dpx[i][j] or dpx[i+1][j-x]

    dpy = [[False for _ in range(2*L+1)] for _ in range(len(Ys)+1)]
    dpy[0][y0+L] = True

    for i, y in enumerate(Ys):
        for j in range(2*L+1):
            if j+y <= 2*L:
                dpy[i+1][j+y] = dpy[i][j] or dpy[i+1][j+y]
            if j-y >= 0:
                dpy[i+1][j-y] = dpy[i][j] or dpy[i+1][j-y]

    if dpx[-1][X+L] and dpy[-1][Y+L]:
        print('Yes')
    else:
        print('No')


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

D = [[], []]
st_x = 0
st_y = 0
st = 0
while st <= len(s)-1 and s[st] == "F":
    x -= 1
    st += 1

di = 0
for i in range(st, n):
    if s[i] == "T":
        di = (di+1) % 2
        D[di].append(0)
    else:
        D[di][-1] += 1

# print(D)


ANS = [0, 0]
st_po = [0, 0]
go_po = [x, y]
for i in range(2):
    mid = 8005#sum(D[i]) + 5
    DP = [[0] * (mid*2) for i in range(len(D[i]) + 1)]
    DP[0][st_po[i] + mid] = 1
    for j in range(len(D[i])):
        dd = D[i][j]
        for k in range(len(DP[0])):
            aa = 0
            bb = 0
            if 0 <= k-dd <= len(DP[0])-1:
                aa = DP[j][k-dd]
            if 0 <= k+dd <= len(DP[0])-1:
                bb = DP[j][k+dd]

            DP[j+1][k] = int(aa or bb)

    if 0 <= go_po[i]+mid <= len(DP[0])-1:
        ANS[i] = DP[-1][go_po[i]+mid]
    # print("len",mid*2)
    #if i == 1:
        # print(DP[1][7999+mid])
# print(ANS)

print("Yes" if ANS[0] and ANS[1] else "No")

Submission status: Time Limit Exceeded

Solution code:
s = input()
x, y = map(int, input().split())
l = s.split("T")
#print(l)
x -= len(l[0])
ys = []
xs = []
if len(l) == 1:
  if x == 0 and y == 0:
    print("Yes")
  else:
    print("No")
  exit(0)
for i in range(len(l)):
  if i == 0:
    continue
  if i % 2:
    ys.append(len(l[i]))
  else:
    xs.append(len(l[i]))
#移動しうるマスの総数はなんとか全列挙できるレベル
#先頭からi番目まで見たとき、移動可能であるマス
#何x何のDPなら追いつくのか考える
#bitDPするよりずっと現実的

dpy = [[0] * (2 * sum(ys) + 1) for _ in range(len(ys) + 2)]
dpx = [[0] * (2 * sum(xs) + 1) for _ in range(len(xs) + 2)]
dpy[0][sum(ys)] = 1
dpx[0][sum(xs)] = 1
#print(ys, xs)
#print(dpy, dpx)
for i in range(len(ys)):
  for j in range(2 * sum(ys) + 1):
    if dpy[i][j] == 0:
      continue
    #print(i, j)
    dpy[i + 1][j + ys[i]] += dpy[i][j]
    dpy[i + 1][j - ys[i]] += dpy[i][j]
for i in range(len(xs)):
  for j in range(2 * sum(xs) + 1):
    if dpx[i][j] == 0:
      continue
    dpx[i + 1][j + xs[i]] += dpx[i][j]
    dpx[i + 1][j - xs[i]] += dpx[i][j]
#print(dpx, dpy)
if y >= sum(ys) + 1 or x >= sum(xs) + 1:
  print("No")
  exit(0)
if dpy[len(ys)][y + sum(ys)] > 0 and dpx[len(xs)][x + sum(xs)] > 0:
  print("Yes")
else:
  print("No")

Submission status: Time Limit Exceeded

Solution code:
## PyPy3 なら通りそう

def ABC082D(Step, Size, advance, Goal):
  ## 初期化
  dp = [[False for j in range(2*Size+1)] for i in range(Step+1)]
  dp[0][Size] = True
  ## DP
  for i in range(Step):
    for j in range(2*Size+1):
      dp[i+1][j] = dp[i][max(j-advance[i],0)] or dp[i][min(j+advance[i],2*Size)] 
  return dp[Step][Goal+Size]


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

idx_first_T = S.find('T')
if idx_first_T == -1:
  if X == len(S) and Y == 0:
    print('Yes')
  else:
    print('No')
  exit()
else:
  X -= idx_first_T

lst_x = []
lst_y = []
pre_state = 1 ## 0:x-axis, 1:y-axis
advance = 0
for i in range(idx_first_T+1, len(S)):
  if S[i] == 'T':
    if advance > 0:
      if pre_state == 0:
        lst_x.append(advance)
      else:
        lst_y.append(advance)
      advance = 0
    pre_state = (pre_state + 1) % 2
  else:
    advance += 1
else:
  if advance > 0:
    if pre_state == 0:
      lst_x.append(advance)
    else:
      lst_y.append(advance)
    
bool_x = ABC082D(len(lst_x), len(S), lst_x, X)
bool_y = ABC082D(len(lst_y), len(S), lst_y, Y)
if bool_x and bool_y:
  print('Yes')
else:
  print('No')

Submission status: Time Limit Exceeded

Solution code:
def ABC082D(Step, Size, advance, Goal):
  ## 初期化
  dp = [[False for j in range(2*Size+1)] for i in range(Step+1)]
  dp[0][Size] = True
  ## DP
  for i in range(Step):
    for j in range(2*Size+1):
      dp[i+1][j] = dp[i][max(j-advance[i],0)] or dp[i][min(j+advance[i],2*Size)] 
  return dp[Step][Goal+Size]


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

idx_first_T = S.find('T')
if idx_first_T == -1:
  if X == len(S) and Y == 0:
    print('Yes')
  else:
    print('No')
  exit()
else:
  X -= idx_first_T

lst_x = []
lst_y = []
pre_state = 1 ## 0:x-axis, 1:y-axis
advance = 0
for i in range(idx_first_T+1, len(S)):
  if S[i] == 'T':
    if advance > 0:
      if pre_state == 0:
        lst_x.append(advance)
      else:
        lst_y.append(advance)
      advance = 0
    pre_state = (pre_state + 1) % 2
  else:
    advance += 1
else:
  if advance > 0:
    if pre_state == 0:
      lst_x.append(advance)
    else:
      lst_y.append(advance)
    
bool_x = ABC082D(len(lst_x), len(S), lst_x, X)
bool_y = ABC082D(len(lst_y), len(S), lst_y, Y)
if bool_x and bool_y:
  print('Yes')
else:
  print('No')