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:
from copy import deepcopy
def main():
    s=input()
    x,y=map(int,input().split())
    a=[0]*8000
    b=[0]*8000
    tmp=0
    T=True
    asize=0
    bsize=0
    for i in s:
        if i=="T":
            tmp=1-tmp
            T=True
        elif tmp==0:
            if T:
                asize+=1
                T=False
            a[asize-1]+=1
        else:
            if T:
                bsize+=1
                T=False
            b[bsize-1]+=1
    c={0}
    for i in range(asize):
        d=set()
        if i==0:
            if s[0]=="T":
                d.add(-a[i])
            d.add(a[i])
        else:
            for j in c:
                d.add(j+a[i])
                d.add(j-a[i])
        c=deepcopy(d)
    if not x in c:
        print("No")
        quit()
    c={0}
    for i in range(bsize):
        d=set()
        for j in c:
            d.add(j+b[i])
            d.add(j-b[i])
        c=deepcopy(d)
    if not y in c:
        print("No")
        quit()
    print("Yes")
if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy
s=input()
x,y=map(int,input().split())
a=[0]*8000
b=[0]*8000
tmp=0
T=True
asize=0
bsize=0
for i in s:
    if i=="T":
        tmp=1-tmp
        T=True
    elif tmp==0:
        if T:
            asize+=1
            T=False
        a[asize-1]+=1
    else:
        if T:
            bsize+=1
            T=False
        b[bsize-1]+=1
c={0}
for i in range(asize):
    d=set()
    if i==0:
        if s[0]=="T":
            d.add(-a[i])
        d.add(a[i])
    else:
        for j in c:
            d.add(j+a[i])
            d.add(j-a[i])
    c=deepcopy(d)
if not x in c:
    print("No")
    quit()
c={0}
for i in range(bsize):
    d=set()
    for j in c:
        d.add(j+b[i])
        d.add(j-b[i])
    c=deepcopy(d)
if not y in c:
    print("No")
    quit()
print("Yes")

Submission status: Time Limit Exceeded

Solution code:
s = input()
x,y = map(int,input().split())
k = 0
data = [[],[]]
f = 0
p = 1
for s_ in s:
    if p==1 and s_=='F':
        x -= 1
        continue
    p = 0
    if s_ == 'T':
        if f:
            data[k].append(f)
        k = (k+1)%2
        f = 0
    else:
        f += 1
if f:
    data[k].append(f)

dpx = [[0]*16001 for _ in range(len(data[0])+1)]
dpy = [[0]*16001 for _ in range(len(data[1])+1)]
dpx[0][8000] = 1
dpy[0][8000] = 1

for i in range(len(data[0])):
    for j in range(len(dpx[i])):
        if dpx[i][j]==1:
            dpx[i+1][j+data[0][i]] = 1
            dpx[i+1][j-data[0][i]] = 1

for i in range(len(data[1])):
    for j in range(len(dpy[i])):
        if dpy[i][j]==1:
            dpy[i+1][j+data[1][i]] = 1
            dpy[i+1][j-data[1][i]] = 1
if dpx[-1][8000+x]==1 and dpy[-1][8000+y]==1:
    print('Yes')
else:
    print('No')

Submission status: Time Limit Exceeded

Solution code:
# /usr/bin/python
# -*- coding: utf-8 -*-
import sys
import math



Sn = str(input())
X,Y = map(int, input().split())

xyn = [0]
for c in Sn:
  if c == 'T':
    xyn.append(0)
  else:
    xyn[-1] += 1

Xn = xyn[2::2]
Yn = xyn[1::2]

dp_x = [xyn[0]]
for i in range(len(Xn)):
  dp_xn = []
  for j in dp_x:
    dp_xn = dp_xn + [j+Xn[i], j-Xn[i]]
  dp_x = dp_xn

dp_y = [0]
for i in range(len(Yn)):
  dp_yn = []
  for j in dp_y:
    dp_yn = dp_yn + [j+Yn[i], j-Yn[i]]
  dp_y = dp_yn

if X in dp_x and Y in dp_y:
  print("Yes")
else:
  print("No")

Submission status: Time Limit Exceeded

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

import sys
input = sys.stdin.readline

def io_generator():
	return input()

#+++++++++++++++++++

def isBitOn(value, n):
	return (value & (2 ** n)) > 0
	
def isMake(l,v):
	if len(l)==0 and v ==0:
		return True
		
	for i in range(2 ** len(l)):
		r=sum([v * (1-2*isBitOn(i,j)) for j,v in enumerate(l)])
		if r == v:
			return True
	return False
	
def move_next(v,i):
	rv = (v | 2 ** (i))
	ri = i+1
	return rv, ri
	
def buck(v,i):
	#111,3->101,3
	#101,3->010,2
	for j in range(i-1):
		n=i-1-j
		d=(v & 2** (n - 1))
		if d > 0:
			nv=(v & (2**(n-1) - 1))
			nnv,ni = move_next(nv, n)
			return True,nnv,ni
	return False, -1, -1
	
def isMake3(l,a_target):
	tree=0
	ii=0
	l.sort()
	est=lambda al,av:sum([v * isBitOn(av,j) for j,v in enumerate(l)])
	cc=True
	
	while cc:
		ccv=est(l, tree)
		#print(bin(tree),ii, est(l,tree),a_target)
		while ccv < a_target:
			tree, ii = move_next(tree,ii)
			#print(bin(tree),ii, est(l,tree),a_target)
			if ii > len(l):
				return False, -1
			ccv += l[ii-1]
			
		if ccv == a_target:
			return True, tree
		else:
			cc,tree,ii=buck(tree, ii)
			
	return False, -1
	
def isMake2(l, a_target):
	off=sum(l)
	if abs(a_target) > off:
		return False
	elif abs(a_target) == off:
		return True
	
	ll=[2*i for i in l]
	ret, _ = isMake3(ll, off + a_target)
	return ret
	
#def isMakeDp(l, a_target, ttl):

def next(a_xy):
	return (a_xy+1)%2
	
def main(io):
	ft=io()
	goal = list(map(int, io().split()))
	
	isFirstMove=True
	init_pos=[0,0]
	xy=0
	mm=0
	ml=[[],[]]
	for c in ft:
		if isFirstMove and c=='F':
			init_pos[0]+=1
		elif isFirstMove and c=='T':
			isFirstMove=False
			xy = next(xy)
			mm=0
		elif c == 'F':
			mm+=1
		elif c== 'T':
			if mm > 0:
				ml[xy].append(mm)
			xy=next(xy)
			mm=0
	if mm>0:
		ml[xy].append(mm)

	is_debug=False
	if is_debug:
		print(ml)
		print(init_pos)
		print(goal)
	for i in range(2):
		if not isMake2(ml[i], goal[i] - init_pos[i]):
			return 'No'
	return 'Yes'

#++++++++++++++++++++

if __name__ == "__main__":
	io= lambda : io_generator()
	print (main(io))

Submission status: Time Limit Exceeded

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

import sys
input = sys.stdin.readline

def io_generator():
	return input()

#+++++++++++++++++++


def isBitOn(value, n):
	return (value & (2 ** n)) > 0
	
def isMake(l,v):
	if len(l)==0 and v ==0:
		return True
		
	for i in range(2 ** len(l)):
		r=sum([v * (1-2*isBitOn(i,j)) for j,v in enumerate(l)])
		if r == v:
			return True
	return False
	
def move_next(v,i):
	rv = (v | 2 ** (i))
	ri = i+1
	return rv, ri
	
def buck(v,i):
	#111,3->101,3
	#101,3->010,2
	for j in range(i-1):
		n=i-1-j
		d=(v & 2** (n - 1))
		if d > 0:
			nv=(v & (2**(n-1) - 1))
			nnv,ni = move_next(nv, n)
			return True,nnv,ni
	return False, -1, -1
	
def isMake3(l,a_target):
	tree=0
	ii=0
	l.sort()
	est=lambda al,av:sum([v * isBitOn(av,j) for j,v in enumerate(l)])
	cc=True
	
	iii=0
	while cc:
		ccv=est(l, tree)
		#print(bin(tree),ii, est(l,tree),a_target)
		while ccv < a_target:
			tree, ii = move_next(tree,ii)
			#print(bin(tree),ii, est(l,tree),a_target)
			if ii > len(l):
				return False, -1
			ccv += l[ii-1]
			
		if ccv == a_target:
			return True, tree
		else:
			cc,tree,ii=buck(tree, ii)
			
	return False, -1
	
def isMake2(l, a_target):
	off=sum(l)
	ll=[2*i for i in l]
	ret, _ = isMake3(ll, off + a_target)
	return ret
	
#def isMakeDp(l, a_target, ttl):

def next(a_xy):
	return (a_xy+1)%2
	
def main(io):
	ft=io()
	goal = list(map(int, io().split()))
	
	isFirstMove=True
	init_pos=[0,0]
	xy=0
	mm=0
	ml=[[],[]]
	for c in ft:
		if isFirstMove and c=='F':
			init_pos[0]+=1
		elif isFirstMove and c=='T':
			isFirstMove=False
			xy = next(xy)
			mm=0
		elif c == 'F':
			mm+=1
		elif c== 'T':
			if mm > 0:
				ml[xy].append(mm)
			xy=next(xy)
			mm=0
	if mm>0:
		ml[xy].append(mm)

	is_debug=False
	if is_debug:
		print(ml)
		print(init_pos)
		print(goal)
	for i in range(2):
		if not isMake2(ml[i], goal[i] - init_pos[i]):
			return 'No'
	return 'Yes'

#++++++++++++++++++++

if __name__ == "__main__":
	io= lambda : io_generator()
	print (main(io))

Submission status: Time Limit Exceeded

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

def io_generator():
	return input()

#+++++++++++++++++++


def isBitOn(value, n):
	return (value & (2 ** n)) > 0
	
def isMake(l,v):
	if len(l)==0 and v ==0:
		return True
		
	for i in range(2 ** len(l)):
		r=sum([v * (1-2*isBitOn(i,j)) for j,v in enumerate(l)])
		if r == v:
			return True
	return False
	
def move_next(v,i):
	rv = (v | 2 ** (i))
	ri = i+1
	return rv, ri
	
def buck(v,i):
	#111,3->101,3
	#101,3->010,2
	for j in range(i-1):
		n=i-1-j
		d=(v & 2** (n - 1))
		if d > 0:
			nv=(v & (2**(n-1) - 1))
			nnv,ni = move_next(nv, n)
			return True,nnv,ni
	return False, -1, -1
	
def isMake3(l,a_target):
	tree=0
	ii=0
	l.sort()
	est=lambda al,av:sum([v * isBitOn(av,j) for j,v in enumerate(l)])
	cc=True
	
	iii=0
	while cc:
		ccv=est(l, tree)
		#print(bin(tree),ii, est(l,tree),a_target)
		while ccv < a_target:
			tree, ii = move_next(tree,ii)
			#print(bin(tree),ii, est(l,tree),a_target)
			if ii > len(l):
				return False, -1
			ccv += l[ii-1]
			
		if est(l,tree)==a_target:
			return True, tree
		else:
			cc,tree,ii=buck(tree, ii)
			
	return False, -1
	
def isMake2(l, a_target):
	off=sum(l)
	ll=[2*i for i in l]
	ret, _ = isMake3(ll, off + a_target)
	return ret
	
#def isMakeDp(l, a_target, ttl):

def next(a_xy):
	return (a_xy+1)%2
	
def main(io):
	ft=io()
	goal = list(map(int, io().split()))
	
	isFirstMove=True
	init_pos=[0,0]
	xy=0
	mm=0
	ml=[[],[]]
	for c in ft:
		if isFirstMove and c=='F':
			init_pos[0]+=1
		elif isFirstMove and c=='T':
			isFirstMove=False
			xy = next(xy)
			mm=0
		elif c == 'F':
			mm+=1
		elif c== 'T':
			if mm > 0:
				ml[xy].append(mm)
			xy=next(xy)
			mm=0
	if mm>0:
		ml[xy].append(mm)

	is_debug=False
	if is_debug:
		print(ml)
		print(init_pos)
		print(goal)
	for i in range(2):
		if not isMake2(ml[i], goal[i] - init_pos[i]):
			return 'No'
	return 'Yes'

#++++++++++++++++++++

if __name__ == "__main__":
	io= lambda : io_generator()
	print (main(io))

Submission status: Time Limit Exceeded

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

def io_generator():
	return input()

#+++++++++++++++++++


def isBitOn(value, n):
	return (value & (2 ** n)) > 0
	
def isMake(l,v):
	if len(l)==0 and v ==0:
		return True
		
	for i in range(2 ** len(l)):
		r=sum([v * (1-2*isBitOn(i,j)) for j,v in enumerate(l)])
		if r == v:
			return True
	return False
	
def move_next(v,i):
	return (v | 2 ** (i)), i+1
	
def buck(v,i):
	#111,3->101,3
	#101,3->010,2
	for j in range(i-1):
		n=i-1-j
		d=(v & 2** (n - 1))
		if d > 0:
			nv=(v & (2**(n-1) - 1))
			nnv,ni = move_next(nv, n)
			return True,nnv,ni
	return False, -1, -1
	
def isMake3(l,a_target):
	tree=0
	ii=0
	l.sort()
	est=lambda al,av:sum([v * isBitOn(av,j) for j,v in enumerate(l)])
	cc=True
	
	iii=0
	while cc:
		#print(bin(tree),ii, est(l,tree),a_target)
		while est(l,tree) < a_target:
			tree,ii=move_next(tree,ii)
			#print(bin(tree),ii, est(l,tree),a_target)
			if ii > len(l):
				return False, -1
			
		if est(l,tree)==a_target:
			return True, tree
		else:
			cc,tree,ii=buck(tree, ii)
			
	return False, -1
	
def isMake2(l, a_target):
	off=sum(l)
	ll=[2*i for i in l]
	ret, _ = isMake3(ll, off + a_target)
	return ret
	
def next(a_xy):
	return (a_xy+1)%2
	
def main(io):
	ft=io()
	goal = list(map(int, io().split()))
	
	isFirstMove=True
	init_pos=[0,0]
	xy=0
	mm=0
	ml=[[],[]]
	for c in ft:
		if isFirstMove and c=='F':
			init_pos[0]+=1
		elif isFirstMove and c=='T':
			isFirstMove=False
			xy = next(xy)
			mm=0
		elif c == 'F':
			mm+=1
		elif c== 'T':
			if mm > 0:
				ml[xy].append(mm)
			xy=next(xy)
			mm=0
	if mm>0:
		ml[xy].append(mm)

	is_debug=False
	if is_debug:
		print(ml)
		print(init_pos)
		print(goal)
	for i in range(2):
		if not isMake2(ml[i], goal[i] - init_pos[i]):
			return 'No'
	return 'Yes'

#++++++++++++++++++++

if __name__ == "__main__":
	io= lambda : io_generator()
	print (main(io))

Submission status: Time Limit Exceeded

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

def io_generator():
	return input()

#+++++++++++++++++++


def isBitOn(value, n):
	return (value & (2 ** n)) > 0
	
def isMake(l,v):
	if len(l)==0 and v ==0:
		return True
		
	for i in range(2 ** len(l)):
		r=sum([v * (1-2*isBitOn(i,j)) for j,v in enumerate(l)])
		if r == v:
			return True
	return False
	
def isMake2(l,v):
	return False

	
def next(a_xy):
	return (a_xy+1)%2
	
def main(io):
	ft=io()
	goal = list(map(int, io().split()))
	
	isFirstMove=True
	init_pos=[0,0]
	xy=0
	mm=0
	ml=[[],[]]
	for c in ft:
		if isFirstMove and c=='F':
			init_pos[0]+=1
		elif isFirstMove and c=='T':
			isFirstMove=False
			xy = next(xy)
			mm=0
		elif c == 'F':
			mm+=1
		elif c== 'T':
			if mm > 0:
				ml[xy].append(mm)
			xy=next(xy)
			mm=0
	if mm>0:
		ml[xy].append(mm)

	is_debug=False
	if is_debug:
		print(ml)
		print(init_pos)
		print(goal)
	for i in range(2):
		if not isMake(ml[i], goal[i] - init_pos[i]):
			return 'No'
	return 'Yes'

#++++++++++++++++++++

if __name__ == "__main__":
	io= lambda : io_generator()
	print (main(io))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-

DIR = [
	(1, 0),
	(0, -1),
	(-1, 0),
	(0, 1),
]

def main():
	s = raw_input()
	s2 = raw_input()
	x, y = [int(x) for x in s2.split()]
	# print s, x, y

	dp = set([(0,0,0)])
	for instr in s:
		if instr == 'F':
			dp = set([(t[0]+DIR[t[2]][0], t[1]+DIR[t[2]][1], t[2]) for t in dp])
		else:
			dp = set([(t[0], t[1], (t[2]+1)%4) for t in dp]) | set([(t[0], t[1], (t[2]-1+4)%4) for t in dp])

	for i in xrange(4):
		if (x, y, i) in dp:
			print 'Yes'
			return
	print 'No'

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
s = [x == 'F' for x in input()]
gx, gy = [int(s) for s in input().split(' ')]

q = set([((0, 0), 0, 0)])

def conv_d(d):
    if d == 0:
        return (1, 0)
    elif d == 1:
        return (0, 1)
    elif d == 2:
        return (-1, 0)
    else:
        return (0, -1)

while len(q) > 0:
    (x, y), d, c = q.pop()
    if c >= len(s):
        continue
    elif s[c]:
        dx, dy = conv_d(d)
        if c == len(s)-1 and x+dx == gx and y+dy == gy:
            print('Yes')
            exit()
        if c+1 < len(s):
            q.add(((x+dx, y+dy), d, c+1))
    elif c+1 < len(s):
        q.add(((x, y), (d+1)%4, c+1))
        q.add(((x, y), (d-1)%4, c+1))
print('No')

Submission status: Time Limit Exceeded

Solution code:
s = input()
gx, gy = [int(s) for s in input().split(' ')]

q = set([((0, 0), 0, 0)])

def conv_d(d):
    if d == 0:
        return (1, 0)
    elif d == 1:
        return (0, 1)
    elif d == 2:
        return (-1, 0)
    else:
        return (0, -1)

while len(q) > 0:
    (x, y), d, c = q.pop()
    dx, dy = conv_d(d)
    if c >= len(s):
        continue
    elif s[c] == 'F':
        if c == len(s) - 1 and x+dx == gx and y+dy == gy:
            print('Yes')
            exit()
        q.add(((x + dx, y + dy), d, c + 1))
    else:
        q.add(((x, y), (d + 1) % 4, c + 1))
        q.add(((x, y), (d - 1) % 4, c + 1))
print('No')

Submission status: Time Limit Exceeded

Solution code:
s = input()
gx, gy = [int(s) for s in input().split(' ')]

q = [((0, 0), 0, 0)]

def conv_d(d):
    if d == 0:
        return (1, 0)
    elif d == 1:
        return (0, 1)
    elif d == 2:
        return (-1, 0)
    else:
        return (0, -1)

while len(q) > 0:
    (x, y), d, c = q.pop()
    dx, dy = conv_d(d)
    if c >= len(s):
        print('No')
        exit()
    elif s[c] == 'F':
        if c == len(s) - 1 and x+dx == gx and y+dy == gy:
            print('Yes')
            exit()
        q.insert(0, ((x + dx, y + dy), d, c + 1))
    else:
        q.insert(0, ((x, y), (d + 1) % 4, c + 1))
        q.insert(0, ((x, y), (d - 1) % 4, c + 1))

Submission status: Time Limit Exceeded

Solution code:
s = input()
x, y = map(int, input().split())
edge = [[], []]
# delete first edge
firstedge = 0
for c in s:
    if c == 'T': break
    else: firstedge += 1
x -= firstedge
dir = 0
cur = 0
for c in s[firstedge:]:
    if c == 'T':
        if cur > 0:
            edge[dir].append(cur)
            cur = 0
        dir = (dir + 1) % 2
    else:
        cur += 1
if cur > 0:
    edge[dir].append(cur)
xtar = sum(edge[0]) + x
ytar = sum(edge[1]) + y
if xtar < 0 or ytar < 0 or x > sum(edge[0]) or y > sum(edge[1]):
    print('No')
    exit()
# partition dp
dx = [0] * (xtar + 1)
dy = [0] * (ytar + 1)
dx[0], dy[0] = 1, 1
for e in edge[0]:
    for i in range(xtar+1 - 2*e):
        pre = dx.copy()
        if pre[i] == 1:
            dx[i+2*e] = 1
    if dx[xtar]: break
for e in edge[1]:
    for i in range(ytar+1 - 2*e):
        pre = dy.copy()
        if pre[i] == 1:
            dy[i+2*e] = 1
    if dy[ytar]: break
if dx[xtar] and dy[ytar]: print('Yes')
else: print('No')

Submission status: Time Limit Exceeded

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

XY = [[], []]
b = 0
renzoku = 0
for i in range(len(s)) :
    if s[i] == "T" :
        b = (b+1) % 2
        renzoku = 0
    else :
        if renzoku == 0 :
            XY[b].append(1)
            renzoku = 1
        else :
            XY[b][-1] += 1


#print(XY)

g = 10000

X = [[0 for i in range(g*2)] for j in range(len(XY[0]))]
Y = [[0 for i in range(g*2)] for j in range(len(XY[1]))]



if len(XY[0]) > 0 :
    X[0][g+XY[0][0]] = 1
    if s[0] == "T" :
        X[0][g-XY[0][0]] = 1
        
    for i in range(1, len(XY[0])) :
        for j in range(g*2) :
            #print(X)
            if j - XY[0][i] >= 0 and X[i-1][j - XY[0][i]] == 1 :
                X[i][j] = 1
            if j + XY[0][i] <= g*2-1 and X[i-1][j + XY[0][i]] == 1 :
                X[i][j] = 1

if len(XY[1]) > 0 :

    Y[0][g+XY[1][0]] = 1
    Y[0][g-XY[1][0]] = 1
        
    for i in range(1, len(XY[1])) :
        for j in range(20000) :
            if j - XY[1][i] >= 0 and Y[i-1][j - XY[1][i]] == 1 :
                Y[i][j] = 1
            if j + XY[1][i] <= g*2-1 and Y[i-1][j + XY[1][i]] == 1 :
                Y[i][j] = 1

if X == [] :
    X = [[0 for i in range(g*2)]]
if Y == [] :
    Y = [[0 for i in range(g*2)]]

if ((len(XY[0]) == 0 and x == 0) or X[-1][g+x] == 1) and ((len(XY[1]) == 0 and y == 0) or Y[-1][g+y] == 1) :
    print("Yes")
else :
    print("No")

Submission status: Time Limit Exceeded

Solution code:
s = input() + "T"
x, y = map(int, input().split())
X = [[], [0]]
d = 0
t = 0
for i in range(len(s)):
    if s[i] == "F":
        t += 1
    else:
        X[d].append(t)
        d = 1-d
        t = 0
def calc(l):
    if len(l) == 0: return [0] 
    post = [l[0]]
    for i in range(1, len(l)):
        if l[i]:
            pre = post
            post = []
            for j in pre:
                if j+l[i] not in post: post.append(j+l[i])
                if j-l[i] not in post: post.append(j-l[i])
            # print(pre, post)
    return post

if x in calc(X[0]) and y in calc(X[1]):
    print("Yes")
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
s = input() + "T"
x, y = map(int, input().split())
X = [[], [0]]
d = 0
t = 0
for i in range(len(s)):
    if s[i] == "F":
        t += 1
    else:
        X[d].append(t)
        d = 1-d
        t = 0
def calc(l):
    if len(l) == 0: return [0] 
    post = [l[0]]
    for i in range(1, len(l)):
        if l[i]:
            pre = post
            post = []
            for j in pre:
                if j+l[i] not in post: post.append(j+l[i])
                if j-l[i] not in post: post.append(j-l[i])
            # print(pre, post)
    return post

if x in calc(X[0]) and y in calc(X[1]):
    print("Yes")
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
s = input() + "T"
x, y = map(int, input().split())
X = [[], [0]]
d = 0
t = 0
for i in range(len(s)):
    if s[i] == "F":
        t += 1
    else:
        X[d].append(t)
        d = 1-d
        t = 0
def calc(l):
    if len(l) == 0: return [0] 
    post = [l[0]]
    for i in range(1, len(l)):
        if l[i]:
            pre = post
            post = []
            for j in pre:
                post.append(j+l[i])
                post.append(j-l[i])
            # print(pre, post)
    return post

if x in calc(X[0]) and y in calc(X[1]):
    print("Yes")
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
s = input() + "T"
x, y = map(int, input().split())
X = [[], [0]]
d = 0
t = 0
for i in range(len(s)):
    if s[i] == "F":
        t += 1
    else:
        X[d].append(t)
        d = 1-d
        t = 0
def calc(l):
    if len(l) == 0: return [0] 
    post = [l[0]]
    for i in range(1, len(l)):
        pre = post
        post = []
        for j in pre:
            post.append(j+l[i])
            post.append(j-l[i])
    return post

if x in calc(X[0]) and y in calc(X[1]):
    print("Yes")
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
s = input().rstrip()
x, y = map(int, input().split())
movex = []
movey = []

n = len(s)
direc = 1
s = s.split('T')
x -= len(s[0])
for elem in s[1:]:
    if direc == 0:
        movex.append(len(elem))
        direc = 1
    else:
        movey.append(len(elem))
        direc = 0

dpx = [[False]*(2*n+1) for _ in range(len(movex)+1)]
dpy = [[False]*(2*n+1) for _ in range(len(movey)+1)]
# dpx = -len(s), -len(s)+1, ..., -1, 0, 1, ..., len(s)-1, len(s)

dpx[0][n] = True
dpy[0][n] = True

for i in range(len(movex)):
    for j in range(2*n+1):
        if dpx[i][j]:
            if j+movex[i] <= 2*n:
                dpx[i+1][j+movex[i]] = True
            if j-movex[i] >= 0:
                dpx[i+1][j-movex[i]] = True
for i in range(len(movey)):
    for j in range(2*n+1):
        if dpy[i][j]:
            if j+movey[i] <= 2*n:
                dpy[i+1][j+movey[i]] = True
            if j-movey[i] >= 0:
                dpy[i+1][j-movey[i]] = True
# for i in range(len(movex)):
#    for j in range(2*n+1):
#        if j-movex[i] >= 0 and j+movex[i] <= 2*n:
#            dpx[i+1][j] = dpx[i][j-movex[i]] or dpx[i][j+movex[i]]
#        if j-movex[i] < 0:
#            dpx[i+1][j] = dpx[i][j+movex[i]]
#        if j+movex[i] > 2*n:
#            dpx[i+1][j] = dpx[i][j-movex[i]]
# for i in range(len(movey)):
#    for j in range(2*n+1):
#        if j-movey[i] >= 0 and j+movey[i] <= 2*n:
#            dpy[i+1][j] = dpy[i][j-movey[i]] or dpy[i][j+movey[i]]
#        if j-movey[i] < 0:
#            dpy[i+1][j] = dpy[i][j+movey[i]]
#        if j+movey[i] > 2*n:
#            dpy[i+1][j] = dpy[i][j-movey[i]]

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
s = input().rstrip()
x, y = map(int, input().split())
movex = []
movey = []

n = len(s)
direc = 1
s = s.split('T')
x -= len(s[0])
for elem in s[1:]:
    if direc == 0:
        movex.append(len(elem))
        direc = 1
    else:
        movey.append(len(elem))
        direc = 0

dpx = [[False]*(2*n+1) for _ in range(len(movex)+1)]
dpy = [[False]*(2*n+1) for _ in range(len(movey)+1)]
# dpx = -len(s), -len(s)+1, ..., -1, 0, 1, ..., len(s)-1, len(s)

dpx[0][n] = True
dpy[0][n] = True

for i in range(len(movex)):
    for j in range(2*n+1):
        if j-movex[i] >= 0 and j+movex[i] <= 2*n:
            dpx[i+1][j] = dpx[i][j-movex[i]] or dpx[i][j+movex[i]]
        if j-movex[i] < 0:
            dpx[i+1][j] = dpx[i][j+movex[i]]
        if j+movex[i] > 2*n:
            dpx[i+1][j] = dpx[i][j-movex[i]]
for i in range(len(movey)):
    for j in range(2*n+1):
        if j-movey[i] >= 0 and j+movey[i] <= 2*n:
            dpy[i+1][j] = dpy[i][j-movey[i]] or dpy[i][j+movey[i]]
        if j-movey[i] < 0:
            dpy[i+1][j] = dpy[i][j+movey[i]]
        if j+movey[i] > 2*n:
            dpy[i+1][j] = dpy[i][j-movey[i]]

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
s = input().rstrip()
x, y = map(int, input().split())
movex = []
movey = []

direc = 0
first = None
for elem in s.split('T'):
    if direc == 0:
        if first is not None:
            movex.append(len(elem))
        else:
            first = len(elem)
        direc = 1
    else:
        movey.append(len(elem))
        direc = 0
x -= first

n = len(s)
dpx = [[False]*(2*n+1) for _ in range(len(movex)+1)]
dpy = [[False]*(2*n+1) for _ in range(len(movey)+1)]
# dpx = -len(s), -len(s)+1, ..., -1, 0, 1, ..., len(s)-1, len(s)

dpx[0][n] = True
dpy[0][n] = True

for i in range(len(movex)):
    for j in range(2*n+1):
        if j-movex[i] >= 0 and j+movex[i] <= 2*n:
            dpx[i+1][j] = dpx[i][j-movex[i]] or dpx[i][j+movex[i]]
        if j-movex[i] < 0:
            dpx[i+1][j] = dpx[i][j+movex[i]]
        if j+movex[i] > 2*n:
            dpx[i+1][j] = dpx[i][j-movex[i]]
for i in range(len(movey)):
    for j in range(2*n+1):
        if j-movey[i] >= 0 and j+movey[i] <= 2*n:
            dpy[i+1][j] = dpy[i][j-movey[i]] or dpy[i][j+movey[i]]
        if j-movey[i] < 0:
            dpy[i+1][j] = dpy[i][j+movey[i]]
        if j+movey[i] > 2*n:
            dpy[i+1][j] = dpy[i][j-movey[i]]

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

Submission status: Time Limit Exceeded

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

"""
参考：https://img.atcoder.jp/abc082/editorial.pdf
　　　https://atcoder.jp/contests/abc082/submissions/3930644
・計算量改善。-8000～8000全部回してたループを値があるkeyだけ回るようにした。
・それに合わせて、貰うDPを送るDPにした。(自分的にはこっちのが分かりやすいし)
"""

from collections import defaultdict

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

S2 = []
tmp = 0
# 連続するF毎にまとまるように文字列Sを変形させる
for i in range(len(S)):
    if S[i] == 'F':
        tmp += 1
    # T毎に区切る
    else:
        S2.append(tmp)
        tmp = 0
S2.append(tmp)

# 文字列がFのみだとこの後のDPできないので別処理
if len(S2) == 1:
    if X == S2[0] and Y == 0:
        print('Yes')
    else:
        print('No')
    exit()

# dictならマイナスの添字もそのまま使える
dpx = [defaultdict(int) for _ in range(len(S2))]
dpy = [defaultdict(int) for _ in range(len(S2))]
# xの初期化：step0は右移動、step1ではそのまま
dpx[0][S2[0]] = dpx[1][S2[0]] = 1
# yの初期化：step0は何もなし、step1で上下どちらかに移動
dpy[1][S2[1]] = dpy[1][-S2[1]] = 1
for i in range(2, len(S2)):
    # 左右に移動する
    for k, v in dpx[i-1].items():
        if i % 2 == 0:
            # 到達可能な位置から+-した位置に送る
            dpx[i][k-S2[i]] = 1
            dpx[i][k+S2[i]] = 1
        else:
            # yをやる時はxはそのまま
            dpx[i][k] = dpx[i-1][k]
    # 上下に移動する
    for k, v in dpy[i-1].items():
        if i % 2 == 1:
            dpy[i][k-S2[i]] = 1
            dpy[i][k+S2[i]] = 1
        else:
            dpy[i][k] = dpy[i-1][k]
# 最後のstepでXとYが到達可能ならOK
if dpx[len(S2)-1][X] and dpy[len(S2)-1][Y]:
    print('Yes')
else:
    print('No')

Submission status: Time Limit Exceeded

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

"""
参考：https://img.atcoder.jp/abc082/editorial.pdf
・DPをxとyの2つに分けて行う。
　[step][x] = その時xはその状態になれるか
　[step][y] = その時yはその状態になれるか
・x方向とy方向は独立に考えることができる。
"""

from collections import defaultdict

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

S2 = []
tmp = 0
# 連続するF毎にまとまるように文字列Sを変形させる
for i in range(len(S)):
    if S[i] == 'F':
        tmp += 1
    # T毎に区切る
    else:
        S2.append(tmp)
        tmp = 0
S2.append(tmp)

# 文字列がFのみだとこの後のDPできないので別処理
if len(S2) == 1:
    if X == S2[0] and Y == 0:
        print('Yes')
    else:
        print('No')
    exit()

# dictならマイナスの添字もそのまま使える
dpx = [defaultdict(int) for _ in range(len(S2))]
dpy = [defaultdict(int) for _ in range(len(S2))]
# xの初期化：step0は右移動、step1ではそのまま
dpx[0][S2[0]] = dpx[1][S2[0]] = 1
# yの初期化：step0は何もなし、step1で上下どちらかに移動
dpy[1][S2[1]] = dpy[1][-S2[1]] = 1
for i in range(2, len(S2)):
    for j in range(-len(S), len(S)+1):
        # 左右に移動する
        if i % 2 == 0:
            # 前回stepに今回step分を+-して到達可能か見る
            dpx[i][j] = dpx[i-1][j-S2[i]] | dpx[i-1][j+S2[i]]
            # xをやる時はyはそのまま
            dpy[i][j] = dpy[i-1][j]
        # 上下に移動する
        else:
            dpx[i][j] = dpx[i-1][j]
            dpy[i][j] = dpy[i-1][j-S2[i]] | dpy[i-1][j+S2[i]]
# 最後のstepでXとYが到達可能ならOK
if dpx[len(S2)-1][X] and dpy[len(S2)-1][Y]:
    print('Yes')
else:
    print('No')

Submission status: Time Limit Exceeded

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

from collections import defaultdict, deque

S = input()
X, Y = map(int, input().split())
# [x][y][現在の移動距離][現在の向き]をメモする
memo = defaultdict(lambda :defaultdict(lambda :defaultdict(lambda :defaultdict(int))))
len_F = S.count('F')
# ゴールまでの距離と進む予定の距離の偶奇が違えば論外
if (X + Y) % 2 != len_F % 2:
    print('No')
    exit()

def bfs():
    que = deque()
    que.append([0,0,0,'r',len_F])
    while len(que) != 0:
        x, y, cur, dirc, rest = que.popleft()
        # 訪問済
        if memo[x][y][cur][dirc] == 1:
            continue
        # Tの場合は反対側から来たやつも訪問済扱い
        if cur < len(S) and S[cur] == 'T':
            if ((dirc == 'r' or dirc == 'l')
                    and (memo[x][y][cur]['r'] or memo[x][y][cur]['l'])):
                continue
            if ((dirc == 'u' or dirc == 'd')
                    and (memo[x][y][cur]['u'] or memo[x][y][cur]['d'])):
                continue
        memo[x][y][cur][dirc] = 1
        # もうゴールに届かない場合
        if rest < abs(X-x) + abs(Y-y):
            continue
        # 最後までいった時
        if cur == len(S):
            if x == X and y == Y:
                break
            else:
                continue
        # まっすぐ
        if S[cur] == 'F':
            if dirc == 'r': x += 1
            elif dirc == 'l': x -= 1
            elif dirc == 'u': y += 1
            elif dirc == 'd': y -= 1
            if not memo[x][y][cur+1][dirc]:
                que.append([x,y,cur+1,dirc,rest-1])
        # 曲がる
        elif S[cur] == 'T':
            if dirc == 'r' or dirc == 'l':
                que.append([x,y,cur+1,'u',rest])
                que.append([x,y,cur+1,'d',rest])
            elif dirc == 'u' or dirc == 'd': 
                que.append([x,y,cur+1,'r',rest])
                que.append([x,y,cur+1,'l',rest])
bfs()
if any(memo[X][Y][len(S)]):
    print('Yes')
else:
    print('No')