Problem p03488 (python)

Fixed submission:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

s = input()
x, y = MAP()

x_list = []
y_list = []
for i, s_ in enumerate(s.split('T')):
	if i == 0:
		x -= len(s_)
	elif i % 2 == 0:
		x_list.append(len(s_))
	else:
		y_list.append(len(s_))

def check(d, x):
  se =set([0])
  for dx in d:
    se={a+b for a,b in product(se,[-dx,dx])}  # 直積としてDPを計算
  return (x in se)

print('Yes' if check(x_list, x) and check(y_list, y) else 'No')

Buggy submission (verdict: Runtime Error):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

s = input()
x, y = MAP()

if "T" not in s:
	x_list = [len(s)]
	y_list = []
else:
	F = s.split("T")

	x_list = []
	y_list = []
	for i, n in enumerate(F):
		if i%2 == 0:  # x軸方向
			x_list.append(len(n))
		else:
			y_list.append(len(n))

"""
x_listから順に取り出して右か左に動く．
dp[i][x] := i回目の移動後にx座標がxとなっていることができるか
y軸も同様
"""

x -= x_list.pop(0)  # 最初のFの分だけ右に動く
x_sum = sum(x_list)
y_sum = sum(y_list)


if (x_sum-x)%2 != 0:  # パリティ
  print("No")
  sys.exit()
else:
  n_x = (x_sum-abs(x))//2
if (y_sum-y)%2 != 0:
  print("No")
  sys.exit()
else:
  n_y = (y_sum-abs(y))//2

dp_x = [[False]*(abs(n_x)+1) for _ in range(len(x_list)+1)]
dp_y = [[False]*(abs(n_y)+1) for _ in range(len(x_list)+1)]
dp_x[0][0] = True
dp_y[0][0] = True

for i in range(1, len(x_list)+1):
	for j in range(n_x+1):
		if dp_x[i-1][j]:
			dp_x[i][j] = True
			if j+x_list[i-1] < n_x+1:
				dp_x[i][j+x_list[i-1]] = True

for i in range(1, len(y_list)+1):
	for j in range(n_y+1):
		if dp_y[i-1][j]:
			dp_y[i][j] = True
			if j+y_list[i-1] < n_y+1:
				dp_y[i][j+y_list[i-1]] = True

if dp_x[-1][-1] and dp_y[-1][-1]:
	print("Yes")
else:
	print("No")

Buggy submission (verdict: Runtime Error):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

s = input()
x, y = MAP()

F = s.split("T")

x_list = []
y_list = []
for i, n in enumerate(F):
	if i%2 == 0:  # x軸方向
		x_list.append(len(n))
	else:
		y_list.append(len(n))

"""
x_listから順に取り出して右か左に動く．
dp[i][x] := i回目の移動後にx座標がxとなっていることができるか
y軸も同様
"""

x -= x_list.pop(0)  # 最初のFの分だけ右に動く
x_sum = sum(x_list)
y_sum = sum(y_list)


if (x_sum-x)%2 != 0:  # パリティ
  print("No")
  sys.exit()
else:
  n_x = (x_sum-abs(x))//2
if (y_sum-y)%2 != 0:
  print("No")
  sys.exit()
else:
  n_y = (y_sum-abs(y))//2

dp_x = [[False]*(abs(n_x)+1) for _ in range(len(x_list)+1)]
dp_y = [[False]*(abs(n_y)+1) for _ in range(len(x_list)+1)]
dp_x[0][0] = True
dp_y[0][0] = True

for i in range(1, len(x_list)+1):
	for j in range(n_x+1):
		if dp_x[i-1][j]:
			dp_x[i][j] = True
			if j+x_list[i-1] < n_x+1:
				dp_x[i][j+x_list[i-1]] = True

for i in range(1, len(y_list)+1):
	for j in range(n_y+1):
		if dp_y[i-1][j]:
			dp_y[i][j] = True
			if j+y_list[i-1] < n_y+1:
				dp_y[i][j+y_list[i-1]] = True

if dp_x[-1][-1] and dp_y[-1][-1]:
	print("Yes")
else:
	print("No")

Buggy submission (verdict: Runtime Error):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

s = input()
x, y = MAP()

F = s.split("T")
print(F)
x_list = []
y_list = []
for i, n in enumerate(F):
	if i%2 == 0:  # x軸方向
		x_list.append(len(n))
	else:
		y_list.append(len(n))

"""
x_listから順に取り出して右か左に動く．
dp[i][x] := i回目の移動後にx座標がxとなっていることができるか
y軸も同様
"""

if len(x_list) == 0:
	if x == 0 and y == 0:
		print("Yes")
		sys.exit()
	else:
		print("No")
		sys.exit()

x -= x_list.pop(0)  # 最初のFの分だけ右に動く
x_sum = sum(x_list)
y_sum = sum(y_list)


if (x_sum-x)%2 != 0:  # パリティ
  print("No")
  sys.exit()
else:
  n_x = (x_sum-abs(x))//2
if (y_sum-y)%2 != 0:
  print("No")
  sys.exit()
else:
  n_y = (y_sum-abs(y))//2

dp_x = [[False]*(abs(n_x)+1) for _ in range(len(x_list)+1)]
dp_y = [[False]*(abs(n_y)+1) for _ in range(len(x_list)+1)]
dp_x[0][0] = True
dp_y[0][0] = True

for i in range(1, len(x_list)+1):
	for j in range(n_x+1):
		if dp_x[i-1][j]:
			dp_x[i][j] = True
			if j+x_list[i-1] < n_x+1:
				dp_x[i][j+x_list[i-1]] = True

for i in range(1, len(y_list)+1):
	for j in range(n_y+1):
		if dp_y[i-1][j]:
			dp_y[i][j] = True
			if j+y_list[i-1] < n_y+1:
				dp_y[i][j+y_list[i-1]] = True

if dp_x[-1][-1] and dp_y[-1][-1]:
	print("Yes")
else:
	print("No")

Buggy submission (verdict: Runtime Error):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

s = input()
x, y = MAP()

F = s.split("T")
print(F)
x_list = []
y_list = []
for i, n in enumerate(F):
	if i%2 == 0:  # x軸方向
		x_list.append(len(n))
	else:
		y_list.append(len(n))

"""
x_listから順に取り出して右か左に動く．
dp[i][x] := i回目の移動後にx座標がxとなっていることができるか
y軸も同様
"""

if len(x_list) == 0:
	if x == 0 and y == 0:
		print("Yes")
		sys.exit()
	else:
		print("No")
		sys.exit()

x -= x_list.pop(0)  # 最初のFの分だけ右に動く
x_sum = sum(x_list)
y_sum = sum(y_list)


if (x_sum-x)%2 != 0:  # パリティ
  print("No")
  sys.exit()
else:
  n_x = (x_sum-abs(x))//2
if (y_sum-y)%2 != 0:
  print("No")
  sys.exit()
else:
  n_y = (y_sum-abs(y))//2

dp_x = [[False]*(abs(n_x)+1) for _ in range(len(x_list)+1)]
dp_y = [[False]*(abs(n_y)+1) for _ in range(len(x_list)+1)]
dp_x[0][0] = True
dp_y[0][0] = True

for i in range(1, len(x_list)+1):
	for j in range(n_x+1):
		if dp_x[i-1][j]:
			dp_x[i][j] = True
			if j+x_list[i-1] < n_x+1:
				dp_x[i][j+x_list[i-1]] = True

for i in range(1, len(y_list)+1):
	for j in range(n_y+1):
		if dp_y[i-1][j]:
			dp_y[i][j] = True
			if j+y_list[i-1] < n_y+1:
				dp_y[i][j+y_list[i-1]] = True

if dp_x[-1][-1] and dp_y[-1][-1]:
	print("Yes")
else:
	print("No")