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 main():
    s = input().split("T")
    x, y = map(int, input().split())
    xs = []
    x -= len(s[0])
    for i in range(2, len(s), 2):
        xs.append(len(s[i]))
    ys = []
    for i in range(1, len(s), 2):
        ys.append(len(s[i]))
    
    ok = False
    for i in range(2**len(xs)):
        tmp = 0
        for j in range(len(xs)):
            if i&1:
                tmp += xs[0]
            else:
                tmp -= xs[0]
            i >>= 1
        if tmp == x:
            ok = True
            break
    if ok:
        ok = False
        for i in range(2**len(ys)):
            tmp = 0
            for j in range(len(ys)):
                if i&1:
                    tmp += ys[0]
                else:
                    tmp -= ys[0]
                i >>= 1
            if tmp == y:
                ok = True
                break
    if ok:
        print("Yes")
    else:
        print("No")

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

# def can_reach(x, default_pos, x_moves):
#     for tries in range(2**len(x_moves)):  # x_moves は最大 4000, 2**100 で既に 10**30 なのでぜんぜん間に合わない。
#         result = default_pos
#         for digit in range(len(x_moves)):
#             result += (x_moves[digit] if tries & (1<<digit) else -x_moves[digit])
#         if result == x:
#             return True
#     return False

# def can_reach(x_aim, default_pos, x_moves):  # ソートして貪欲？
#     for i in sorted(x_moves, reverse=True):
#         if x_aim > default_pos:
#             default_pos += i
#         else:
#             default_pos -= i
#     if default_pos == x_aim:
#         return True
#     else:
#         return False

# def can_reach(x_aim, default_pos, x_moves):  # dp → TLE
#     def dp(i, pos):
#         if i == 0:
#             if pos == default_pos: return True
#             else: return False
#         else:
#             return dp(i-1, pos - x_moves[i-1])  or dp(i-1, pos + x_moves[i-1])

#     return dp(len(x_moves), x_aim)

# def can_reach(x_aim, default_pos, x_moves):  # dp with table
#     dp = [[False for _ in range(20000)] for _ in range(len(x_moves)+1)]  # 20000 * 8000 = O(10**8) ぐらい
#     def read_dp(i, j):
#         return dp[i][j+10000]
#     def write_dp(i, j, k):
#         dp[i][j+10000] = k
#     write_dp(0, default_pos, True)
#     for i in range(len(x_moves)):
#         for j in range(20000):
#             if dp[i][j] == True:
#                 dp[i+1][j+x_moves[i]] = True
#                 dp[i+1][j-x_moves[i]] = True
#     return read_dp(len(x_moves), x_aim)
    

def can_reach(x_aim, default_pos, x_moves):  # dp with dict
    dp = [default_pos]
    for i in x_moves:
        new_dp = []
        for j in dp:
            new_dp.append(j+i)
            new_dp.append(j-i)
        dp = new_dp
    return x_aim in dp


def main(): 
    s = SI()
    x, y = LI()

    x_moves = []
    y_moves = []
    moving_x = True
    for i in s.split('T'):
        if moving_x:
            x_moves.append(len(i))
        else:
            y_moves.append(len(i))
        moving_x = not moving_x

    if can_reach(x, x_moves[0], x_moves[1:]) and can_reach(y, 0, y_moves):
        print('Yes')
    else:
        print('No')


main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

# def can_reach(x, default_pos, x_moves):
#     for tries in range(2**len(x_moves)):  # x_moves は最大 4000, 2**100 で既に 10**30 なのでぜんぜん間に合わない。
#         result = default_pos
#         for digit in range(len(x_moves)):
#             result += (x_moves[digit] if tries & (1<<digit) else -x_moves[digit])
#         if result == x:
#             return True
#     return False

# def can_reach(x_aim, default_pos, x_moves):  # ソートして貪欲？
#     for i in sorted(x_moves, reverse=True):
#         if x_aim > default_pos:
#             default_pos += i
#         else:
#             default_pos -= i
#     if default_pos == x_aim:
#         return True
#     else:
#         return False

# def can_reach(x_aim, default_pos, x_moves):  # dp → TLE
#     def dp(i, pos):
#         if i == 0:
#             if pos == default_pos: return True
#             else: return False
#         else:
#             return dp(i-1, pos - x_moves[i-1])  or dp(i-1, pos + x_moves[i-1])

#     return dp(len(x_moves), x_aim)

def can_reach(x_aim, default_pos, x_moves):  # dp with table
    dp = [[False for _ in range(20000)] for _ in range(len(x_moves)+1)]
    def read_dp(i, j):
        return dp[i][j+10000]
    def write_dp(i, j, k):
        dp[i][j+10000] = k
    write_dp(0, default_pos, True)
    for i in range(len(x_moves)):
        for j in range(20000):
            if dp[i][j] == True:
                dp[i+1][j+x_moves[i]] = True
                dp[i+1][j-x_moves[i]] = True
    return read_dp(len(x_moves), x_aim)
    

def main(): 
    s = SI()
    x, y = LI()

    x_moves = []
    y_moves = []
    moving_x = True
    for i in s.split('T'):
        if moving_x:
            x_moves.append(len(i))
        else:
            y_moves.append(len(i))
        moving_x = not moving_x

    if can_reach(x, x_moves[0], x_moves[1:]) and can_reach(y, 0, y_moves):
        print('Yes')
    else:
        print('No')

main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

# def can_reach(x, default_pos, x_moves):
#     for tries in range(2**len(x_moves)):  # x_moves は最大 4000, 2**100 で既に 10**30 なのでぜんぜん間に合わない。
#         result = default_pos
#         for digit in range(len(x_moves)):
#             result += (x_moves[digit] if tries & (1<<digit) else -x_moves[digit])
#         if result == x:
#             return True
#     return False

# def can_reach(x_aim, default_pos, x_moves):  # ソートして貪欲？
#     for i in sorted(x_moves, reverse=True):
#         if x_aim > default_pos:
#             default_pos += i
#         else:
#             default_pos -= i
#     if default_pos == x_aim:
#         return True
#     else:
#         return False

def can_reach(x_aim, default_pos, x_moves):  # dp
    def dp(i, pos):
        if i == 0:
            if pos == default_pos: return True
            else: return False
        else:
            return dp(i-1, pos - x_moves[i-1])  or dp(i-1, pos + x_moves[i-1])

    return dp(len(x_moves), x_aim)

def main(): 
    s = SI()
    x, y = LI()

    x_moves = []
    y_moves = []
    moving_x = True
    for i in s.split('T'):
        if moving_x:
            x_moves.append(len(i))
        else:
            y_moves.append(len(i))
        moving_x = not moving_x

    if can_reach(x, x_moves[0], x_moves[1:]) and can_reach(y, 0, y_moves):
        print('Yes')
    else:
        print('No')


main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

def can_reach(x, default_pos, x_moves):
    for tries in range(2**len(x_moves)):
        result = default_pos
        for digit in range(len(x_moves)):
            result += (x_moves[digit] if tries & (1<<digit) else -x_moves[digit])
        if result == x:
            return True
    return False

def main(): 
    s = SI()
    x, y = LI()

    x_moves = []
    y_moves = []
    moving_x = True
    for i in s.split('T'):
        if moving_x:
            x_moves.append(len(i))
        else:
            y_moves.append(len(i))
        moving_x = not moving_x

    if can_reach(x, x_moves[0], x_moves[1:]) and can_reach(y, 0, y_moves):
        print('Yes')
    else:
        print('No')


main()

Submission status: Time Limit Exceeded

Solution code:
s = input()
X, Y = map(int, input().split())
fs = s.split("T")
nsx = list(map(len, fs[0::2]))
nsy = list(map(len, fs[1::2]))
xs = set()
q = [(nsx[0], 1)]
while q:
  x, i = q.pop()
  if i == len(nsx):
    xs.add(x)
  else:
    q.append((x+nsx[i], i+1))
    q.append((x-nsx[i], i+1))
ys = set()
q = [(0, 0)]
while q:
  y, i = q.pop()
  if i == len(nsy):
    ys.add(y)
  else:
    q.append((y+nsy[i], i+1))
    q.append((y-nsy[i], i+1))
#print(xs, ys)
if X in xs and Y in ys:
  print("Yes")
else:
  print("No")

Submission status: Time Limit Exceeded

Solution code:
_MAXN = 8000

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

move_cnt = 0
change_cnt = 0
x_move = []
y_move = []
for i in range(len(s)):
    if s[i] == 'F':
        move_cnt += 1
    else:
        if change_cnt % 2 == 0:
            x_move.append(move_cnt)
        else:
            y_move.append(move_cnt)
        change_cnt += 1
        move_cnt = 0
if change_cnt % 2 == 0:
    x_move.append(move_cnt)
else:
    y_move.append(move_cnt)

x_dp = [[False]*_MAXN*2 for i in range(_MAXN//2+1)]
y_dp = [[False]*_MAXN*2 for i in range(_MAXN//2+1)]
x_dp[0][0] = True
y_dp[0][0] = True

for i in range(len(x_move)):
    for j in range(-_MAXN,_MAXN):
        if x_dp[i][j] == True:
            if j - x_move[i] > -_MAXN:
                x_dp[i+1][j-x_move[i]] = True
            if j + x_move[i] < _MAXN:
                x_dp[i+1][j+x_move[i]] = True

for i in range(len(y_move)):
    for j in range(-_MAXN,_MAXN):
        if y_dp[i][j] == True:
            if j - y_move[i] > -_MAXN:
                y_dp[i+1][j-y_move[i]] = True
            if j + y_move[i] < _MAXN:
                y_dp[i+1][j+y_move[i]] = True

if x_dp[len(x_move)][x] and y_dp[len(y_move)][y]:
    print('Yes')
else:
    print('No')

Submission status: Time Limit Exceeded

Solution code:
s=input()+'T'
x,y=map(int,input().split())
if 'T' in s:
  pos=s.index('T')
  x-=pos
  s=s[pos+1:]
arr=s.split('T')
xarr=[]
yarr=[]
for i in range(len(arr)):
  l=len(arr[i])
  if l==0:
    continue
  if i%2==0:
    yarr.append(l)
  else:
    xarr.append(l)
x+=sum(xarr)
y+=sum(yarr)
if x%2==1 or y%2==1:
  print('No')
else:
  #DP for xarr,yarr
  xdp=[0]*8005
  xdp[0]=1
  for val in xarr:
    for i in range(8004,-1,-1):
      if i-val<0:
        break
      if xdp[i-val]==1:
        xdp[i]=1
  ydp=[0]*8005
  ydp[0]=1
  for val in yarr:
    for i in range(8004,-1,-1):
      if i-val<0:
        break
      if ydp[i-val]==1:
        ydp[i]=1
  if xdp[x//2]==0:
    print('No')
  else:
    if ydp[y//2]==0:
      print('No')
    else:
      print('Yes')

Submission status: Time Limit Exceeded

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

import sys  # {{{
import os
import time
import re
from pydoc import help
import string
import math
from operator import itemgetter
from collections import Counter
from collections import deque
from collections import defaultdict as dd
import fractions
from heapq import heappop, heappush, heapify
import array
from bisect import bisect_left, bisect_right, insort_left, insort_right
from copy import deepcopy as dcopy
import itertools
# }}}

# pre-defined{{{
sys.setrecursionlimit(10**7)
INF = 10**20
GOSA = 1.0 / 10**10
MOD = 10**9+7
ALPHABETS = [chr(i) for i in range(ord('a'), ord('z')+1)]  # can also use string module
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def DP(N, M, first): return [[first] * M for n in range(N)]
def DP3(N, M, L, first): return [[[first] * L for n in range(M)] for _ in range(N)]
from inspect import currentframe
# }}}

def local_input():# {{{
    from pcm.utils import set_stdin
    import sys
    from pathlib import Path
    parentdir = Path(os.path.dirname(__file__)).parent
    inputfile = parentdir.joinpath('test/sample-1.in')
    if len(sys.argv) == 1:
        set_stdin(inputfile)
# }}}

def solve():
    s = input().split('T')
    goal = list(map(int,input().split()))
    
    stack = deque()
    stack.append([0,0,'right',0])

    while stack:
        a = stack.popleft()
        if a[3] == len(s):
            break

        if a[2] == 'right':
            a[0] += len(s[a[3]])
            stack.append([a[0],a[1],'up',a[3]+1])
            stack.append([a[0],a[1],'down',a[3]+1])
        elif a[2] == 'left':
            a[0] -= len(s[a[3]])
            stack.append([a[0],a[1],'up',a[3]+1])
            stack.append([a[0],a[1],'down',a[3]+1])
        elif a[2] == 'up':
            a[1] += len(s[a[3]])
            stack.append([a[0],a[1],'left',a[3]+1])
            stack.append([a[0],a[1],'right',a[3]+1])
        else:
            a[1] -= len(s[a[3]])
            stack.append([a[0],a[1],'left',a[3]+1])
            stack.append([a[0],a[1],'right',a[3]+1])

    
    while stack:
        a = stack.pop()
        if a[:2] == goal:
            print('Yes')
            exit()
    
    print('No')

    return 0

if __name__ == "__main__":# {{{
    try:
        local_input()
        def dump(*args):
            names = {id(v):k for k,v in currentframe().f_back.f_locals.items()}
            print(', '.join(names.get(id(arg),'???')+' => '+repr(arg) for arg in args), file=sys.stderr)
    except:
        def dump(*args):
            pass

    solve()

# vim: set foldmethod=marker:}}}

Submission status: Time Limit Exceeded

Solution code:


def check(goal, dist_data, start):
    dp = [[0 for i in range(17000)] for i in range(len(dist_data) + 1)]
    dp[0][start + 8500] = 1

    for i in range(1, len(dist_data) + 1):
        for j in range(len(dp[i - 1])):
            if dp[i - 1][j]:
                dp[i][j + dist_data[i - 1]] = 1
                dp[i][j - dist_data[i - 1]] = 1

    return dp[len(dist_data)][goal + 8500]


def main():
    data = input()
    goal = list(map(int, input().split()))
    data = data.split('T')
    move_dist = [len(ele) for ele in data]

    x_data = move_dist[2::2]
    y_data = move_dist[1::2]

    if check(goal[0], x_data, move_dist[0]) and check(goal[1], y_data, 0):
        print('Yes')
    else:
        print('No')


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
s=input()
x,y=map(int,input().split())
ct=0
XY=[]
for i in range(len(s)):
  if s[i]=="F":
    ct+=1
  else:
    XY.append(ct)
    ct=0
XY.append(ct)
x-=XY[0]
X=XY[2::2]
Y=XY[1::2]


def chk(Z,z):
  tot,nz=sum(Z),len(Z)
  if tot==0:
    if z==0:
      return True
    else:
      return False
  elif abs(z)>tot:
    return False
  else:
    DP=[[False]*(2*tot+1) for _ in range(nz+1)]
    DP[0][tot]=True
    for i in range(nz):
      zz=Z[i]
      for j in range(2*tot+1):
        if j+zz<2*tot+1 and DP[i][j+zz]==True:
          DP[i+1][j]=True
        if j-zz>=0 and DP[i][j-zz]==True:
          DP[i+1][j]=True
    return DP[nz][z+tot]

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

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy as dc
S=list(map(len,input().split("T")))
x,y=map(int,input().split())
x=abs(x-S[0])
y=abs(y)
L=S[2::2]
R=S[1::2]
sumL=sum(L)
sumR=sum(R)
flag=0    
if sumL>=x and sumR>=y and (sumL-x)%2==0 and (sumR-y)%2==0 and flag==0:
    setL={0}
    setR={0}
    setL1={0}
    setR1={0}
    gL=(sumL-x)//2
    gR=(sumR-y)//2
    if gL==0:
        flag=1
    else:
        for i in L:
            setL=dc(setL1)
            for j in setL:
                k=i+j
                if k<gL:
                    setL1.add(k)
                elif k==gL:
                    flag=1
                    break
            if flag==1:
                break
    if flag==1:
        if gR==0:
            flag=2
        else:
            for i in R:
                for j in setR:
                    setR=dc(setR1)
                    k=i+j
                    if k<gR:
                        setR1.add(k)
                    elif k==gR:
                        flag=2
                        break
                if flag==2:
                    break
if flag==2:
    print("Yes")
else:
    print("No")

Submission status: Time Limit Exceeded

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

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

def solve(S: str, X: int, Y: int):
    is_x_ok = False
    is_y_ok = False

    dp = collections.defaultdict(bool)
    S2 = S.split("T")
    dp[0,len(S2[0])] = True

    maxx = len(S2[0])
    for i,s in enumerate(S2[0::2]):
        if i > 0:
            dx = len(s)
            maxx += dx
            for x in range(-maxx,maxx+1):
                if (i-1,x-dx) in dp or (i-1,x+dx) in dp:
                    dp[i,x] = True

    if dp[len(S2[0::2])-1,X]:
        is_x_ok = True

    dp = collections.defaultdict(bool)

    if len(S2) > 1:
        dp[0,len(S2[1])] = True
        dp[0,-len(S2[1])] = True

        maxy = len(S2[1])
        for i,s in enumerate(S2[1::2]):
            if i > 0:
                dy = len(s)
                maxy += dy
                for y in range(-maxy,maxy+1):
                    if (i-1,y-dy) in dp or (i-1,y+dy) in dp:
                        dp[i,y] = True

        if dp[len(S2[1::2])-1,Y]:
            is_y_ok = True
    elif Y == 0:
        is_y_ok = True

    if is_x_ok and is_y_ok:
        print(YES)
    else:
        print(NO)



# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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:
#!/usr/bin/env python3
import sys
import collections

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

def solve(S: str, X: int, Y: int):
    is_x_ok = False
    is_y_ok = False

    dp = collections.defaultdict(bool)
    S2 = S.split("T")
    dp[0,len(S2[0])] = True

    maxx = len(S2[0])
    for i,s in enumerate(S2[0::2]):
        if i > 0:
            dx = len(s)
            maxx += dx
            for x in range(-maxx,maxx+1):
                dp[i,x] = dp[i-1,x+dx] or dp[i-1,x-dx]

    if dp[len(S2[0::2])-1,X]:
        is_x_ok = True

    dp = collections.defaultdict(bool)

    if len(S2) > 1:
        dp[0,len(S2[1])] = True
        dp[0,-len(S2[1])] = True

        maxy = len(S2[1])
        for i,s in enumerate(S2[1::2]):
            if i > 0:
                dy = len(s)
                maxy += dy
                for y in range(-maxy,maxy+1):
                    dp[i,y] = dp[i-1,y+dy] or dp[i-1,y-dy]

        if dp[len(S2[1::2])-1,Y]:
            is_y_ok = True
    elif Y == 0:
        is_y_ok = True

    if is_x_ok and is_y_ok:
        print(YES)
    else:
        print(NO)



# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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:
#!/usr/bin/env python3
import sys
import collections

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

def solve(S: str, X: int, Y: int):
    is_x_ok = False
    is_y_ok = False

    dp = collections.defaultdict(bool)
    S2 = S.split("T")
    dp[0,len(S2[0])] = True

    for i,s in enumerate(S2[0::2]):
        if i > 0:
            dx = len(s)
            for x in range(-8000,8001):
                dp[i,x] = dp[i-1,x+dx] or dp[i-1,x-dx]

    if dp[len(S2[0::2])-1,X]:
        is_x_ok = True

    dp = collections.defaultdict(bool)

    if len(S2) > 1:
        dp[0,len(S2[1])] = True
        dp[0,-len(S2[1])] = True

        for i,s in enumerate(S2[1::2]):
            if i > 0:
                dy = len(s)
                for y in range(-8000,8001):
                    dp[i,y] = dp[i-1,y+dy] or dp[i-1,y-dy]

        if dp[len(S2[1::2])-1,Y]:
            is_y_ok = True
    elif Y == 0:
        is_y_ok = True

    if is_x_ok and is_y_ok:
        print(YES)
    else:
        print(NO)



# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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:
import sys
from itertools import product as prd
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
MOD = 1000000007
def POW(x, y): return pow(x, y, MOD)
def INV(x, m=MOD): return pow(x, m - 2, m)
def DIV(x, y, m=MOD): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()

S = input()
X,Y=LI()

while S and S[0] == 'F':
    S = S[1:]
    X -= 1
isX = True
cur = 0
xs = []
ys = []
for i in range(len(S)):
    if S[i] == 'T':
        if cur:
            if isX: xs.append(cur)
            else: ys.append(cur)
        isX = not isX
        cur = 0
    elif S[i] == 'F': cur += 1

if cur:
    if isX: xs.append(cur)
    else: ys.append(cur)
sumxs = sum(xs)
sumys = sum(ys)

if abs(X) > sumxs or abs(Y) > sumys:
    print('No')
    exit()

memo1 = [[0]*(sumxs*2+1) for i in range(len(xs)+1)]
memo2 = [[0]*(sumys*2+1) for i in range(len(ys)+1)]

memo1[0][0] = 1
memo2[0][0] = 1
for i, j in prd(range(1, len(xs)+1), range(-sumxs, sumxs+1)):
    memo1[i][j] = memo1[i-1][j+xs[i-1]] or memo1[i-1][j-xs[i-1]]

for i, j in prd(range(1, len(ys)+1), range(-sumys, sumys+1)):
    memo2[i][j] = memo2[i-1][j+ys[i-1]] or memo2[i-1][j-ys[i-1]]

print('Yes' if memo1[len(xs)][X] and memo2[len(ys)][Y] else 'No')

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
MOD = 1000000007
def POW(x, y): return pow(x, y, MOD)
def INV(x, m=MOD): return pow(x, m - 2, m)
def DIV(x, y, m=MOD): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()

S = input()
X,Y=LI()

while S and S[0] == 'F':
    S = S[1:]
    X -= 1

isX = True
cur = 0
xs = []
ys = []
for i in range(len(S)):
    if S[i] == 'T':
        if cur:
            if isX:
                xs.append(cur)
            else:
                ys.append(cur)
        isX = not isX
        cur = 0
    elif S[i] == 'F':
        cur += 1

if cur:
    if isX:
        xs.append(cur)
    else:
        ys.append(cur)

memo1 = {}
def dp1(x, i):
    if i < 0: return x == 0
    if (x, i) in memo1: return memo1[(x,i)]
    res = dp1(x - xs[i], i-1) or dp1(x + xs[i], i-1)
    memo1[(x,i)] = res
    return res

memo2 = {}
def dp2(x, i):
    if i < 0: return x == 0
    if (x, i) in memo2: return memo2[(x,i)]
    res = dp2(x - ys[i], i-1) or dp2(x + ys[i], i-1)
    memo2[(x,i)] = res
    return res


# print(xs, ys)
print('Yes' if dp1(X, len(xs)-1) and dp2(Y, len(ys)-1) else 'No')

Submission status: Time Limit Exceeded

Solution code:
#from numpy import*
#from scipy import*
from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby
from operator import mul
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial
from copy import deepcopy
import sys
#input=sys.stdin.readline  #危険！基本オフにしろ！
sys.setrecursionlimit(10**6)

def main():
    *s,=map(len,input().split("T"))
    x,y=map(int,input().split())
    start=s[0]
    n=s[2::2]
    m=s[1::2]
#    print(n,m)
#    print(start)
    dx=deque()
    dy=deque()
    dx.append(start)
    dy.append(0)
    for i in range(len(n)):
        tmp=deque()
        for j in deepcopy(dx):
            tmp.appendleft(j+n[i])
            tmp.appendleft(j-n[i])
        dx=tmp
#    print(dx)
    for i in range(len(m)):
        tmp=deque()
        for j in deepcopy(dy):
            tmp.appendleft(j+m[i])
            tmp.appendleft(j-m[i])
        dy=tmp
#    print(dy)
    if x in dx and y in dy:
        print("Yes")
    else:
        print("No")


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#from numpy import*
#from scipy import*
from collections import* #defaultdict Counter deque
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby
from operator import mul
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial
from copy import deepcopy
import sys
#input=sys.stdin.readline  #危険！基本オフにしろ！
sys.setrecursionlimit(10**6)

#enumerate input

def main():
    *s,=map(len,input().split("T"))
    x,y=map(int,input().split())
    start=str(s[0])
    n=[0]+s[2::2]
    m=[0]+s[1::2]
    flag1=0
    flag2=0
#    print(n,m)
    for i in range(2**len(n)):
        if x==eval(start+"".join(["+","-"][i>>j&1]+str(n[j-1])for j in range(len(n)))):
            flag1=1
            break
    for i in range(2**len(m)):
        if y==eval("".join(["+","-"][i>>j&1]+str(m[j-1])for j in range(len(m)))):
            flag2=1
            break
    if flag1 and flag2:
        print("Yes")
    else:
        print("No")
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
s = input()
x, y = map(int, input().split())
a = 0
t = [[0], [0]]
n = 0
for i in range(len(s)):
    if s[i] == 'F':
        t[n][-1] += 1
    else:
        n = 1 - n
        t[n].append(0)
flag = [False, False]
z = [x, y]
for k in range(2):
    tt = t[k]
    zk = z[k]
    p = sum(tt)
    if zk > p or zk < -p:
        flag = False
        break
    dp = [[False for _ in range(2 * p + 1)] for i in range(2)]
    i = 1
    if k == 0:
        dp[0][p + tt[0]] = True
    else:
        dp[0][p + tt[0]] = True
        dp[0][p - tt[0]] = True
    if len(tt) > 1:
        for tj in tt[1:]:
            for j in range(tj):
                dp[i][j] = dp[1 - i][j + tj]
            for j in range(tj, 2 * p + 1 - tj):
                dp[i][j] = dp[1 - i][j + tj] or dp[1 - i][j - tj]
            for j in range(2 * p + 1 - tj, 2 * p + 1):
                dp[i][j] = dp[1 - i][j - tj]
            i = 1 - i
    if dp[1 - len(tt) % 2][zk + p]:
        flag = True
    else:
        flag = False
        break
if flag:
    print('Yes')
else:
    print('No')

Submission status: Time Limit Exceeded

Solution code:
s = input()
x, y = map(int, input().split())
a = 0
t = [[0], [0]]
n = 0
for i in range(len(s)):
    if s[i] == 'F':
        t[n][-1] += 1
    else:
        n = 1 - n
        t[n].append(0)
flag = [False, False]
z = [x, y]
for k in range(2):
    tt = t[k]
    zk = z[k]
    if k == 0:
        p = [tt[0]]
    else:
        p = [tt[0], -tt[0]]
    if len(tt) > 1:
        for i in tt[1:]:
            pp = []
            for j in p:
                pp.append(j + i)
                pp.append(j - i)
            p = pp
    if zk in p:
        flag = True
    else:
        flag = False
        break
if flag:
    print('Yes')
else:
    print('No')

Submission status: Time Limit Exceeded

Solution code:
s = input()
x, y = map(int, input().split())
a = 0
t = [[0], [0]]
n = 0
for i in range(len(s)):
    if s[i] == 'F':
        t[n][-1] += 1
    else:
        n = 1 - n
        t[n].append(0)
flag = [False, False]
for k in range(2):
    tt = t[k]
    z = [x, y]
    if k == 0:
        p = [tt[0]]
    else:
        p = [tt[0], -tt[0]]
    for i in range(1, len(tt)):
        pp = []
        for j in range(len(p)):
            pp.append(p[j] + tt[i])
            pp.append(p[j] - tt[i])
        p = pp
    if z[k] in p:
        flag[k] = True
if flag[0] and flag[1]:
    print('Yes')
else:
    print('No')