Problem p03488 (python)

Fixed submission:
from collections import deque
import sys
sys.setrecursionlimit(10**8)

def dp(dp_l,i,N,xs,cum,now):
    if i == N:
        if now == 0:
            return True
        return False
    if abs(now) > cum[i]:
        return False
    if dp_l[i][abs(now)] != -1:
        return dp_l[i][abs(now)]
    dp_l[i][abs(now)] = dp(dp_l,i+1,N,xs,cum,now+xs[i]) or dp(dp_l,i+1,N,xs,cum,now-xs[i])
    return dp_l[i][abs(now)]

def check():
    S = input()
    x, y = map(int, input().split())
    fs = list(map(len,S.split('T')))
    if len(fs)<3:
        if x != fs[0]:
            return False
        if len(fs)==1:
            if y == 0:
                return True
            else:
                return False
        if y != fs[1] and y != -fs[1]:
            return False
        return True
    xs = fs[2::2]
    ys = fs[1::2]
    xs.sort(reverse = True)
    N = len(xs)
    M = len(ys)
    cum = [0]*(N+1)
    for i in range(N-1,-1,-1):
        cum[i] = cum[i+1]+xs[i]
    dp_l = [[-1]*(cum[0]+1) for _ in range(N)]
    if not dp(dp_l,0,N,xs,cum,fs[0]-x):
        return False
    ys.sort(reverse = True)
    cum = [ys[-1]]*(M+1)
    for i in range(M-1,-1,-1):
        cum[i] = cum[i+1]+ys[i]
    dp_l = [[-1]*(cum[0]+1) for _ in range(M)]
    if not dp(dp_l,0,M,ys,cum,-y):
        return False
    return True
if check():
    print('Yes')
else:
    print('No')

Buggy submission (verdict: Runtime Error):
from collections import deque
def check():
    S = input()
    x, y = map(int, input().split())
    fs = list(map(len,S.split('T')))
    if len(fs)<3:
        if x != fs[0]:
            return False
        if len(fs)==1:
            if y == 0:
                return True
            else:
                return False
        if y != fs[1] and y != -fs[1]:
            return False
        return True
    xs = fs[2::2]
    ys = fs[1::2]
    xs.sort(reverse = True)
    N = len(xs)
    M = len(ys)
    cum = [0]*(N+1)
    for i in range(N-1,-1,-1):
        cum[i] = cum[i+1]+xs[i]
    pos = deque([fs[0]-x])
    for i in range(N):
        l = len(pos)
        if l == 0:
            return False
        for _ in range(l):
            d = pos.popleft()
            if abs(d+xs[i])<=cum[i+1] and d+xs[i] not in pos:
                pos.append(d+xs[i])
            if abs(d-xs[i])<=cum[i+1] and d-xs[i] not in pos:
                pos.append(d-xs[i])
    if 0 not in pos:
        return False
    ys.sort(reverse = True)
    cum = [ys[-1]]*(M+1)
    for i in range(M-1,-1,-1):
        cum[i] = cum[i+1]+ys[i]
    pos = deque([0])
    for i in range(M):
        l = len(pos)
        if l == 0:
            return False
        for _ in range(l):
            d = pos.popleft()
            if abs(d+ys[i]-y)<=cum[i+1] and d+xs[i] not in pos:
                pos.append(d+ys[i])
            if abs(d-ys[i]-y)<=cum[i+1] and d-xs[i] not in pos:
                pos.append(d-ys[i])
    if y not in pos:
        return False
    return True
if check():
    print('Yes')
else:
    print('No')

Buggy submission (verdict: Runtime Error):
from collections import deque
def check():
    S = input()
    x, y = map(int, input().split())
    fs = list(map(len,S.split('T')))
    xs = fs[2::2]
    ys = fs[1::2]
    xs.sort(reverse = True)
    N = len(xs)
    M = len(ys)
    cum = [0]*(N+1)
    for i in range(N-1,-1,-1):
        cum[i] = cum[i+1]+xs[i]
    pos = deque([fs[0]-x])
    for i in range(N):
        l = len(pos)
        if l == 0:
            return False
        for _ in range(l):
            d = pos.popleft()
            if abs(d+xs[i])<=cum[i+1] and d+xs[i] not in pos:
                pos.append(d+xs[i])
            if abs(d-xs[i])<=cum[i+1] and d-xs[i] not in pos:
                pos.append(d-xs[i])
    if 0 not in pos:
        return False
    if len(ys)==0:
        if y == 0:
            return True
        else:
            return False
    ys.sort(reverse = True)
    cum = [ys[-1]]*(M+1)
    for i in range(M-1,-1,-1):
        cum[i] = cum[i+1]+ys[i]
    pos = deque([0])
    for i in range(M):
        l = len(pos)
        if l == 0:
            return False
        for _ in range(l):
            d = pos.popleft()
            if abs(d+ys[i]-y)<=cum[i+1] and d+xs[i] not in pos:
                pos.append(d+ys[i])
            if abs(d-ys[i]-y)<=cum[i+1] and d-xs[i] not in pos:
                pos.append(d-ys[i])
    if y not in pos:
        return False
    return True
if check():
    print('Yes')
else:
    print('No')

Buggy submission (verdict: Runtime Error):
from collections import deque
def check():
    S = input()
    x, y = map(int, input().split())
    fs = list(map(len,S.split('T')))
    xs = fs[::2]
    ys = fs[1::2]
    xs.sort(reverse = True)
    N = len(xs)
    M = len(ys)
    cum = [0]*(N+1)
    for i in range(N-1,-1,-1):
        cum[i] = cum[i+1]+xs[i]
    pos = deque([-x])
    for i in range(N):
        l = len(pos)
        if l == 0:
            return False
        for _ in range(l):
            d = pos.popleft()
            if abs(d+xs[i])<=cum[i+1]:
                pos.append(d+xs[i])
            if abs(d-xs[i])<=cum[i+1]:
                pos.append(d-xs[i])
    if 0 not in pos:
        return False
    ys.sort(reverse = True)
    cum = [ys[-1]]*(M+1)
    for i in range(M-1,-1,-1):
        cum[i] = cum[i+1]+ys[i]
    pos = deque([0])
    for i in range(M):
        l = len(pos)
        if l == 0:
            return False
        for _ in range(l):
            d = pos.popleft()
            if abs(d+ys[i]-y)<=cum[i+1]:
                pos.append(d+ys[i])
            if abs(d-ys[i]-y)<=cum[i+1]:
                pos.append(d-ys[i])
    if y not in pos:
        return False
    return True
if check():
    print('Yes')
else:
    print('No')

Buggy submission (verdict: Runtime Error):
from collections import deque
def check():
    S = input()
    x, y = map(int, input().split())
    fs = list(map(len,S.split('T')))
    xs = fs[::2]
    ys = fs[1::2]
    xs.sort(reverse = True)
    N = len(xs)
    M = len(ys)
    cum = [0]*(N+1)
    for i in range(N-1,-1,-1):
        cum[i] = cum[i+1]+xs[i]
    pos = deque([-x])
    for i in range(N):
        l = len(pos)
        if l == 0:
            return False
        for _ in range(l):
            d = pos.popleft()
            if abs(d+xs[i])<=cum[i+1]:
                pos.append(d+xs[i])
            if abs(d-xs[i])<=cum[i+1]:
                pos.append(d-xs[i])
    if 0 not in pos:
        return False
    ys.sort(reverse = True)
    cum = [ys[-1]]*(M+1)
    for i in range(M-1,-1,-1):
        cum[i] = cum[i+1]+ys[i]
    pos = deque([0])
    for i in range(M):
        l = len(pos)
        if l == 0:
            return False
        for _ in range(l):
            d = pos.popleft()
            if abs(d+ys[i])<=cum[i+1]+abs(y):
                pos.append(d+ys[i])
            if abs(d-ys[i])<=cum[i+1]+abs(y):
                pos.append(d-ys[i])
    if y not in pos:
        return False
    return True
if check():
    print('Yes')
else:
    print('No')

Buggy submission (verdict: Runtime Error):
from collections import deque
def check():
    S = input()
    x, y = map(int, input().split())
    fs = list(map(len,S.split('T')))
    xs = fs[::2]
    ys = fs[1::2]
    xs.sort(reverse = True)
    N = len(xs)
    M = len(ys)
    cum = [xs[-1]]*N
    for i in range(N-2,-1,-1):
        cum[i] = cum[i+1]+xs[i]
    pos = deque([-x])
    for i in range(N):
        l = len(pos)
        if l == 0:
            return False
        for _ in range(l):
            d = pos.popleft()
            if abs(d)<=cum[i]:
                pos.append(d+xs[i])
                pos.append(d-xs[i])
    if 0 not in pos:
        return False
    ys.sort(reverse = True)
    cum = [ys[-1]]*M
    for i in range(M-2,-1,-1):
        cum[i] = cum[i+1]+ys[i]
    pos = deque([0])
    for i in range(M):
        l = len(pos)
        if l == 0:
            return False
        for _ in range(l):
            d = pos.popleft()
            if abs(d)<=cum[i]:
                pos.append(d+ys[i])
                pos.append(d-ys[i])
    if y not in pos:
        return False
    return True
if check():
    print('Yes')
else:
    print('No')