Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
INF = 10 ** 20

m, n = map(int, input().split())
manju_lst = [int(input()) for i in range(m)]
manju_lst.sort(reverse=True)

acc = 0
cum_sum = [0]
for manju in manju_lst:
  acc += manju
  cum_sum.append(acc)

clst = []
elst = []

for i in range(n):
  c, e = map(int, input().split())
  clst.append(c)
  elst.append(e)

dp = [[INF] * (m + 1) for _ in range(n)]
for i in range(n):
  dp[i][0] = 0

#dp[x][y]...x種類目までの箱でy個以下売る時の最小コスト
#dp[x][y] = min(dp[x - 1][y], dp[x - 1][y - cx] + ex) if (y - cx >= 0) else min(dp[x - 1][y], dp[x - 1][y + 1])

for x in range(n):
  cx = clst[x]
  ex = elst[x]
  for y in range(m, 0, -1):
    if y >= cx:
      dp[x][y] = min(dp[x - 1][y], dp[x - 1][y - cx] + ex)
    else:
      dp[x][y] = min(dp[x - 1][y], dp[x][y + 1])

print(max([cum_sum[x] - dp[n - 1][x] for x in range(m + 1)]))


Fixed submission:
INF = 10 ** 20

def main():
  m, n = map(int, input().split())
  manju_lst = [int(input()) for i in range(m)]
  manju_lst.sort(reverse=True)
  
  acc = 0
  cum_sum = [0]
  for manju in manju_lst:
    acc += manju
    cum_sum.append(acc)
  
  clst = []
  elst = []
  
  for i in range(n):
    c, e = map(int, input().split())
    clst.append(c)
    elst.append(e)
  
  dp = [[INF] * (m + 1) for _ in range(n + 1)]
  for i in range(n + 1):
    dp[i][0] = 0
  #dp[x][y]...x種類目までの箱でy個まで売る時の最小コスト
  #dp[x][y] = min(dp[x - 1][y], dp[x - 1][y - cx] + ex) if (y - cx >= 0) else min(dp[x - 1][y], (dp[x - 1][y + 1] if (y + 1 <= m) else ex))
  
  for x in range(1, n + 1):
    cx = clst[x - 1]
    ex = elst[x - 1]
    predp = dp[x - 1]
    for y in range(m, 0, -1):
      predp_y = predp[y]
  
      if y >= cx:
        comp = predp[y - cx] + ex
      elif y + 1 <= m:
        comp = dp[x][y + 1]
      else:
        comp = ex
  
      if predp_y <= comp:
        dp[x][y] = predp_y
      else:
        dp[x][y] = comp
  
  dpn = dp[n]
  print(max([cum_sum[x] - dpn[x] for x in range(m + 1)]))

main()
Buggy python submission (verdict: Runtime Error):
n = int(input())
A = [int(input()) for i in range(n)] * 2
dp = [[-1 for i in range(n * 2)] for j in range(n * 2)]

def dfs(i,j):
  #if (j - i > n - 1):undefined
  if dp[i][j] != -1:
    pass
  elif (j - i == n - 1):
    dp[i][j] = 0
  elif (j - i) % 2 == 0:
    if A[i - 1] > A[j + 1]:
      dp[i][j] = dfs(i - 1, j)
    else:
      dp[i][j] = dfs(i, j + 1)
  else:
    dp[i][j] = max(dfs(i - 1, j) + A[i - 1], dfs(i, j + 1) + A[j + 1])
  return dp[i][j]
ans = 0
for i in range(n):
  for j in range(i,2 * n):
    ans = max(ans, dfs(i,i) + A[i])
print(ans)


Fixed submission:
import sys

sys.setrecursionlimit(10000)

n = int(input())
A = [int(input()) for i in range(n)] * 3
dp = [[-1 for i in range(n * 2)] for j in range(n * 2)]

def dfs(i,j):
  #if (j - i > n - 1):undefined
  if dp[i][j] != -1:
    pass
  elif (j - i == n - 1):
    dp[i][j] = 0
  elif (j - i) % 2 == 0:
    if A[i - 1] > A[j + 1]:
      dp[i][j] = dfs(i - 1, j)
    else:
      dp[i][j] = dfs(i, j + 1)
  else:
    dp[i][j] = max(dfs(i - 1, j) + A[i - 1], dfs(i, j + 1) + A[j + 1])
  return dp[i][j]
ans = 0
for i in range(n):
  ans = max(ans, dfs(i,i) + A[i])
print(ans)

Buggy python submission (verdict: Runtime Error):
n = int(input())
A = [int(input()) for i in range(n)] * 3
dp = [[-1 for i in range(n * 2)] for j in range(n * 2)]

def dfs(i,j):
  #if (j - i > n - 1):undefined
  if dp[i][j] != -1:
    pass
  elif (j - i == n - 1):
    dp[i][j] = 0
  elif (j - i) % 2 == 0:
    if A[i - 1] > A[j + 1]:
      dp[i][j] = dfs(i - 1, j)
    else:
      dp[i][j] = dfs(i, j + 1)
  else:
    dp[i][j] = max(dfs(i - 1, j) + A[i - 1], dfs(i, j + 1) + A[j + 1])
  return dp[i][j]
ans = 0
for i in range(n):
  ans = max(ans, dfs(i,i) + A[i])
print(ans)


Fixed submission:
import sys

sys.setrecursionlimit(10000)

n = int(input())
A = [int(input()) for i in range(n)] * 3
dp = [[-1 for i in range(n * 2)] for j in range(n * 2)]

def dfs(i,j):
  #if (j - i > n - 1):undefined
  if dp[i][j] != -1:
    pass
  elif (j - i == n - 1):
    dp[i][j] = 0
  elif (j - i) % 2 == 0:
    if A[i - 1] > A[j + 1]:
      dp[i][j] = dfs(i - 1, j)
    else:
      dp[i][j] = dfs(i, j + 1)
  else:
    dp[i][j] = max(dfs(i - 1, j) + A[i - 1], dfs(i, j + 1) + A[j + 1])
  return dp[i][j]
ans = 0
for i in range(n):
  ans = max(ans, dfs(i,i) + A[i])
print(ans)
Buggy python submission (verdict: Runtime Error):
INF = 10 ** 20
def minimum_cost(rest, init, dic):
  if rest in dic:
    return dic[rest]

  if rest == ():
    return 0

  ret = INF
  for nex in rest:
    nex_init = init + acc[nex]
    ret = min(ret, minimum_cost(tuple(i for i in rest if i != nex), nex_init, dic) +\
                   acc[nex] - (cums[nex][nex_init] - cums[nex][init]))
  dic[rest] = ret
  return ret

n, m = map(int, input().split())
acc = [0] * m
cums = [[0] for _ in range(m)]
for _ in range(n):
  acc[int(input()) - 1] += 1
  for i in range(m):
    cums[i].append(acc[i])

dic = {}
print(minimum_cost(tuple(i for i in range(m)), 0, dic))


Fixed submission:
def main():
  INF = 10 ** 20
  def minimum_cost(rest, h, init, dic):
    if h in dic:
      return dic[h]
  
    if not h:
      return 0
  
    ret = INF
    for nex in rest:
      accnex = acc[nex]
      cumsnex = cums[nex]
      nex_init = init + accnex
      nex_rest = rest[:]
      nex_rest.remove(nex)
      nex_h = h - 2 ** nex
      tmp =  minimum_cost(nex_rest, nex_h, nex_init, dic) +\
                     accnex - (cumsnex[nex_init] - cumsnex[init])
      if ret > tmp:
        ret = tmp
    dic[h] = ret
    return ret
  
  n, m = map(int, input().split())
  acc = [0] * m
  cums = [[0] for _ in range(m)]
  for _ in range(n):
    acc[int(input()) - 1] += 1
    for i in range(m):
      cums[i].append(acc[i])
  
  dic = {}
  h = sum([2 ** i for i in range(m)])
  print(minimum_cost([i for i in range(m)], h, 0, dic))

main()

Buggy python submission (verdict: Runtime Error):
def main():
  INF = 10 ** 20
  def minimum_cost(rest, init, dic):
    if rest in dic:
      return dic[rest]
  
    if rest == ():
      return 0
  
    ret = INF
    for nex in rest:
      accnex = acc[nex]
      cumsnex = cums[nex]
      nex_init = init + accnex
      tmp =  minimum_cost(tuple([i for i in rest if i != nex]), nex_init, dic) +\
                     accnex - (cumsnex[nex_init] - cumsnex[init])
      if ret > tmp:
        ret = tmp
    dic[rest] = ret
    return ret
  
  n, m = map(int, input().split())
  acc = [0] * m
  cums = [[0] for _ in range(m)]
  for _ in range(n):
    acc[int(input()) - 1] += 1
    for i in range(m):
      cums[i].append(acc[i])
  
  dic = {}
  print(minimum_cost(tuple(i for i in range(m)), 0, dic))

main()


Fixed submission:
def main():
  INF = 10 ** 20
  def minimum_cost(rest, h, init, dic):
    if h in dic:
      return dic[h]
  
    if not h:
      return 0
  
    ret = INF
    for nex in rest:
      accnex = acc[nex]
      cumsnex = cums[nex]
      nex_init = init + accnex
      nex_rest = rest[:]
      nex_rest.remove(nex)
      nex_h = h - 2 ** nex
      tmp =  minimum_cost(nex_rest, nex_h, nex_init, dic) +\
                     accnex - (cumsnex[nex_init] - cumsnex[init])
      if ret > tmp:
        ret = tmp
    dic[h] = ret
    return ret
  
  n, m = map(int, input().split())
  acc = [0] * m
  cums = [[0] for _ in range(m)]
  for _ in range(n):
    acc[int(input()) - 1] += 1
    for i in range(m):
      cums[i].append(acc[i])
  
  dic = {}
  h = sum([2 ** i for i in range(m)])
  print(minimum_cost([i for i in range(m)], h, 0, dic))

main()
Buggy python submission (verdict: Runtime Error):
from heapq import heappush, heappop
from itertools import permutations
INF = 10 ** 20

while True:
  n, m, p, a, b = map(int, input().split())
  if n == 0:
    break
  a -= 1
  b -= 1
  tlst = list(map(int, input().split()))
  edges = [[] for _ in range(m)]
  for _ in range(p):
    x, y, z = map(int, input().split())
    x -= 1
    y -= 1
    edges[x].append((z, y))
    edges[y].append((z, x))
  def search(lst):
    que = []
    heappush(que, (0, 0, a))
    costs = [[INF] * m for _ in range(n + 1)]
    costs[0][a] = 0
    while que and lst:
      total, num, city = heappop(que)
      if num >= n:
        continue
      speed = lst[num]
      for dist, to in edges[city]:
        next_total = total + dist / speed
        if costs[num][to] > next_total:
          costs[num][to] = next_total
          heappush(que, (next_total, num + 1, to))
    ret = min(costs[i][b] for i in range(n + 1))
    return ret
  
  ans = INF
  for lst in permutations(tlst, n):
    ans = min(ans, search(lst))
  if ans == INF:
    print("Impossible")
  else:
    print(ans)


Fixed submission:
INF = 10 ** 20

def search(rest, now, goal, dp, edges):
  if now == goal:
    return 0
  if rest == ():
    return INF

  if (rest, now) in dp:
    return dp[(rest, now)]

  ret = INF
  for i, t in enumerate(rest):
    for dist, to in edges[now]:
      tmp = search(tuple(v for j, v in enumerate(rest) if i != j), to, goal, dp, edges) + dist / t
      if ret > tmp:
        ret = tmp
  dp[(rest, now)] = ret
  return ret

def main():
  while True:
    n, m, p, a, b = map(int, input().split())
    if n == 0:
      break
    a -= 1
    b -= 1
    tlst = list(map(int, input().split()))
    edges = [[] for _ in range(m)]
    for _ in range(p):
      x, y, z = map(int, input().split())
      x -= 1
      y -= 1
      edges[x].append((z, y))
      edges[y].append((z, x))
    tlst.sort()
    rest = tuple(tlst)
    dp = {}
    ans = search(rest, a, b, dp, edges)
    if ans == INF:
      print("Impossible")
    else:
      print(ans)
main()
Buggy python submission (verdict: Runtime Error):
INIT = 100

query = []
ans = []
while True:
  q = int(input())
  if q == 0:
    break
  query.append(q)
MAX = max(query)

table = [INIT] * (MAX + 1)
table[0] = 0
all_item = [i * (i + 1) * (i + 2) // 6 for i in range(1, 181)]
odd_item = [i for i in all_item if i % 2]
eve_item = [i for i in all_item if not i % 2]

for v in odd_item:
  for j in range(v, MAX + 1):
    if table[j] > table[j - v] + 1:
      table[j] = table[j - v] + 1

for q in query:
  ans.append(table[q])

for v in eve_item:
  for j in range(v, MAX + 1):
    if table[j] > table[j - v] + 1:
      table[j] = table[j - v] + 1

for i, q in enumerate(query):
  print(table[q], ans[i])


Fixed submission:
def main():
  INIT = 100
  
  query = []
  ans = []
  while True:
    q = int(input())
    if q == 0:
      break
    query.append(q)
  MAX = max(query)
  
  table = [INIT] * (MAX + 1)
  table[0] = 0
  all_item = [i * (i + 1) * (i + 2) // 6 for i in range(1, 181)]
  odd_item = [i for i in all_item if i % 2]
  eve_item = [i for i in all_item if not i % 2]
  
  for v in odd_item:
    for j in range(v, MAX + 1):
      tjv = table[j - v]
      if table[j] > tjv + 1:
        table[j] = tjv + 1
  
  for q in query:
    ans.append(table[q])
  
  for v in eve_item:
    for j in range(v, MAX + 1):
      tjv = table[j - v]
      if table[j] > tjv + 1:
        table[j] = tjv + 1
  
  for i, q in enumerate(query):
    print(table[q], ans[i])

main()
Buggy python submission (verdict: Time Limit Exceeded):
while True:
  n = int(input())
  if n == 0:
    break
  wlst = list(map(int, input().split()))
  dp = [[0] * n for _ in range(n + 1)]
  
  def check(left1, right1, left2, right2, cnt):
    if left1 > right1 and left2 > right2: return cnt
    if left1 > right1:return dp[right2 - left2 + 1][left2] + cnt
    if left2 > right2:return dp[right1 - left1 + 1][left1] + cnt
    ret = cnt + dp[right1 - left1 + 1][left1] + dp[right2 - left2 + 1][left2]
    if abs(wlst[right1] - wlst[left2]) <= 1:
      ret = max(ret, check(left1, right1 - 1, left2 + 1, right2, cnt + 1))
    if right1 - left1 + 1 >= 2 and dp[2][right1 - 1]:
      ret = max(ret, check(left1, right1 - 2, left2, right2, cnt + 1))
    if right2 - left2 + 1 >= 2 and dp[2][left2]:
      ret = max(ret, check(left1, right1, left2 + 2, right2, cnt + 1))
    return ret
  
  for length in range(2, n + 1):
    for left in range(n - length + 1):
      for k in range(length - 1):
        dp[length][left] = max(dp[length][left], check(left, left + k, left + k + 1, left + length - 1, 0))
  
  print(dp[n][0] * 2)



Fixed submission:
def main():
  while True:
    n = int(input())
    if n == 0:
      break
    wlst = list(map(int, input().split()))
    connect = [[None] * n for _ in range(n)]
    for i in range(n):
      for j in range(n):
        connect[i][j] = abs(wlst[i] - wlst[j]) <= 1
    
    max_lst = [[False] * (n + 1) for _ in range(n + 1)]
    for i in range(n + 1):
      max_lst[0][i] = True
    
    dp = [[0] * n for _ in range(n + 1)]
    
    def check(length, left):
      ret = dp[length - 1][left]
      for k in range(length - 1, 0, -2):
        if not max_lst[length - k - 1][left + k]:continue
        if connect[left + k - 1][left + length - 1]:
          temp = length - k + 1 + dp[k - 1][left]
          if ret < temp:
            ret = temp
      return ret
    
    for length in range(2, n + 1):
      for left in range(n - length + 1):
        dp[length][left] = check(length, left)
        if dp[length][left] == length:
          max_lst[length][left] = True
    
    print(dp[n][0])

main()
Buggy python submission (verdict: Runtime Error):
while True:
  n = int(input())
  if n == 0:
    break
  days = [[] for _ in range(30)]
  for i in range(n):
    hima = list(map(int, input().split()))
    for d in hima[1:]:
      days[d].append(i)

  par_lst = [i for i in range(n)]
  
  def get_par(x):
    if x == par_lst[x]:
      return x
    ret = get_par(par_lst[x])
    par_lst[x] = ret
    return ret

  for i, lst in enumerate(days, start=1):
    par = get_par(0)
    for i in range(n):
      if get_par(i) != par:
        break
    else:
      print(i)
      break

    if lst:
      par = get_par(lst[0])
      for num in lst:
        par_lst[get_par(num)] = par
  else:
    print(-1)


Fixed submission:
while True:
  n = int(input())
  if n == 0:
    break
  days = [[] for _ in range(31)]
  for i in range(n):
    hima = list(map(int, input().split()))
    for d in hima[1:]:
      days[d].append(i)
  
  tos = [{i} for i in range(n)]
  end = {i for i in range(n)}
  for i in range(31):
    gather = set()
    for to in days[i]:
      gather = gather | tos[to]
    if gather == end:
      print(i)
      break
    for to in days[i]:
      tos[to] = gather
  else:
    print(-1)
Buggy python submission (verdict: Runtime Error):
dic = {"C":0, "C#":1, "D":2, "D#":3,
       "E":4, "F":5, "F#":6, "G":7,
       "G#":8, "A":9, "A#":10, "B":11}
t = int(input())
for _ in range(t):
  n, m = map(int, input().split())
  t_lst = [-100] + list(map(lambda x:dic[x],input().split()))
  s_lst = list(map(lambda x:dic[x],input().split()))
  s_lst.reverse()
  
  def search(t_index, s_index):
    if s_index == m: return t_index == 0
    if t_index <= 0 or t_index > n: return False
    base = t_lst[t_index]
    proc = s_lst[s_index]
    diff = (proc - base) % 12
    if diff == 1  and search(t_index - 2, s_index + 1) or\
       diff == 0  and search(t_index - 1, s_index + 1) or\
       diff == 11 and search(t_index + 1, s_index + 1): return True
    return False
  
  print("Yes" if search(n, 0) or search(n - 1, 0) else "No")


Fixed submission:
dic = {"C":0, "C#":1, "D":2, "D#":3,
       "E":4, "F":5, "F#":6, "G":7,
       "G#":8, "A":9, "A#":10, "B":11}
t = int(input())
for _ in range(t):
  n, m = map(int, input().split())
  t_lst = [-100] + list(map(lambda x:dic[x],input().split()))
  s_lst = list(map(lambda x:dic[x],input().split()))
  s_lst.reverse()
  
  def search(stack):
    t_index, s_index = stack.pop()
    if s_index == m: return t_index == 0
    if t_index <= 0 or t_index > n: return False
    base = t_lst[t_index]
    proc = s_lst[s_index]
    diff = (proc - base) % 12
    if diff == 1  :stack.append((t_index - 2, s_index + 1))
    if diff == 0  :stack.append((t_index - 1, s_index + 1))
    if diff == 11 :stack.append((t_index + 1, s_index + 1))
    return False
  stack = [(n, 0), (n - 1, 0)]
  while stack:
    if search(stack):
      print("Yes")
      break
  else:
    print("No")
Buggy python submission (verdict: Runtime Error):
dic = {}
for num1 in range(ord("a"), ord("z") + 1):
  c1 = chr(num1)
  dic[c1] = []
  for num2 in range(ord("a"), ord("z") + 1):
    c2 = chr(num2)
    for num3 in range(ord("a"), ord("z") + 1):
      c3 = chr(num3)
      dic[c1].append(c1 + c2 + c3 + "a")

print("?" + dic["a"].pop())
used = set()
while True:
  s = input()
  if s in used or s[0] != "a":
    print("!OUT")
    break
  used.add(s)
  print(dic[s[-1]].pop())


Fixed submission:
dic = {}
for num1 in range(ord("a"), ord("z") + 1):
  c1 = chr(num1)
  dic[c1] = []
  for num2 in range(ord("a"), ord("z") + 1):
    c2 = chr(num2)
    for num3 in range(ord("a"), ord("z") + 1):
      c3 = chr(num3)
      dic[c1].append(c1 + c2 + c3 + "a")

print("?" + dic["a"].pop())
used = set()
while True:
  s = input()
  if s in used or s[0] != "a":
    print("!OUT")
    break
  used.add(s)
  print("?" + dic[s[-1]].pop())
Buggy python submission (verdict: Time Limit Exceeded):
n, m = map(int, input().split())
pros = sorted([list(map(int, input().split())) for _ in range(m)])
index = 0
covered = 0
right = 0
ans = 0
while True:
  a, b = pros[index]
  if a > covered + 1:
    covered = right
    ans += 1
    continue
  else:
    right = max(right, b)
    index += 1

  if covered == n:
    print(ans)
    break

  if index == m:
    covered = right
    ans += 1
    print(ans if covered == n else "Impossible")
    break



Fixed submission:
n, m = map(int, input().split())
pros = sorted([list(map(int, input().split())) for _ in range(m)])
index = 0
covered = 0
right = 0
ans = 0
while True:
  a, b = pros[index]
  if a > covered + 1:
    if covered == right:
      print("Impossible")
      break
    covered = right
    ans += 1
    continue
  else:
    right = max(right, b)
    index += 1

  if covered == n:
    print(ans)
    break

  if index == m:
    covered = right
    ans += 1
    print(ans if covered == n else "Impossible")
    break
Buggy python submission (verdict: Runtime Error):
c = {"1":"", "2":"k", "3":"s", "4":"t", "5":"n",
     "6":"h","7":"m", "8":"y", "9":"r", "0":"w"}
m = {"T":"a", "L":"i", "U":"u", "R":"e", "D":"o"}
s = input()
ans = ""
for i in range(0, len(s), 2):
  if com == "0U":ans += "nn"
  else:ans += c[com[0]] + m[com[1]]
print(ans)


Fixed submission:
c = {"1":"", "2":"k", "3":"s", "4":"t", "5":"n",
     "6":"h","7":"m", "8":"y", "9":"r", "0":"w"}
m = {"T":"a", "L":"i", "U":"u", "R":"e", "D":"o"}
s = input()
ans = ""
for i in range(0, len(s), 2):
  com = s[i:i+2]
  if com == "0U":ans += "nn"
  else:ans += c[com[0]] + m[com[1]]
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n, m = map(int, input().split())
s = input()
left = right = 0
base = ord("a") - 1
score = ord(s[0]) - base
mem = set()
for _ in range(m):
  com = input()
  if com == "L++":
    score //= 27
    left += 1
  elif com == "L--":
    left -= 1
    score = score * 27 + ord(s[left]) - base
  elif com == "R++":
    right += 1
    score += 27 ** (right - left) * (ord(s[right]) - base)
  elif com == "R--":
    score -= 27 ** (right - left) * (ord(s[right]) - base)
    right -= 1
  if score not in mem:mem.add(score)
print(len(mem))


Fixed submission:
def main():
  n, m = map(int, input().split())
  s = input()
  mem = set()
  base = ord("a") - 1
  mod1 = 1000000007
  mod2 = 2147483647
  h1 = [0]
  h2 = [0]
  for c in s:
    h1.append((h1[-1] * 27 + ord(c) - base) % mod1)
    h2.append((h2[-1] * 27 + ord(c) - base) % mod2)
  pow_mem1 = {0:1}
  pow_mem2 = {0:1}
  def my_pow1(x):
    if x in pow_mem1:return pow_mem1[x]
    pow_mem1[x] = my_pow1(x - 1) * 27 % mod1
    return pow_mem1[x]

  def my_pow2(x):
    if x in pow_mem2:return pow_mem2[x]
    pow_mem2[x] = my_pow2(x - 1) * 27 % mod2
    return pow_mem2[x]
  
  left = right = 1
  for _ in range(m):
    com = input()
    if com == "L++":
      left += 1
    if com == "L--":
      left -= 1
    if com == "R++":
      right += 1
    if com == "R--":
      right -= 1
    x = (h1[right] - h1[left - 1] * my_pow1(right - left + 1)) % mod1
    y = (h2[right] - h2[left - 1] * my_pow2(right - left + 1)) % mod2
    mem.add((x, y))

  print(len(mem))

main()

Buggy python submission (verdict: Runtime Error):
def main():
  n, m = map(int, input().split())
  s = input()
  left = right = 0
  mem = set()
  for _ in range(m):
    com = input()
    if com == "L++":
      left += 1
    elif com == "L--":
      left -= 1
    elif com == "R++":
      right += 1
    elif com == "R--":
      right -= 1
    mem.add(s[left:right + 1])
  print(len(mem))

main()


Fixed submission:
def main():
  n, m = map(int, input().split())
  s = input()
  mem = set()
  base = ord("a") - 1
  mod1 = 1000000007
  mod2 = 2147483647
  h1 = [0]
  h2 = [0]
  for c in s:
    h1.append((h1[-1] * 27 + ord(c) - base) % mod1)
    h2.append((h2[-1] * 27 + ord(c) - base) % mod2)
  pow_mem1 = {0:1}
  pow_mem2 = {0:1}
  def my_pow1(x):
    if x in pow_mem1:return pow_mem1[x]
    pow_mem1[x] = my_pow1(x - 1) * 27 % mod1
    return pow_mem1[x]

  def my_pow2(x):
    if x in pow_mem2:return pow_mem2[x]
    pow_mem2[x] = my_pow2(x - 1) * 27 % mod2
    return pow_mem2[x]
  
  left = right = 1
  for _ in range(m):
    com = input()
    if com == "L++":
      left += 1
    if com == "L--":
      left -= 1
    if com == "R++":
      right += 1
    if com == "R--":
      right -= 1
    x = (h1[right] - h1[left - 1] * my_pow1(right - left + 1)) % mod1
    y = (h2[right] - h2[left - 1] * my_pow2(right - left + 1)) % mod2
    mem.add((x, y))

  print(len(mem))

main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
  n = int(input())
  words = []
  scores = []
  for _ in range(n):
    word, score = input().split()
    words.append(word)
    scores.append(int(score))
  mp = ["#" * 6] + ["#" + input() + "#" for _ in range(4)] + ["#" * 6]
  t = int(input())
  
  def search(word):
    used = [[False] * 6 for _ in range(6)]
    vec = ((1, 0), (1, -1), (0, -1), (-1, -1), (-1, 0), (-1, 1), (0, 1), (1, 1))
    
    def _search(word, pos, x, y):
      if pos == len(word) - 1:return 1
      used[y][x] = True
      ret = 0
      for dx, dy in vec:
        nx, ny = x + dx, y + dy
        if not used[ny][nx] and mp[ny][nx] == word[pos + 1]:
          ret += _search(word, pos + 1, nx, ny)
      used[y][x] = False
      return ret
    
    ret = 0
    for y in range(1, 5):
      for x in range(1, 5):
        if mp[y][x] == word[0]:ret += _search(word, 0, x, y)  
    return ret
  
  values = []
  weights = []
  for word, score in zip(words, scores):
    cnt = search(word)
    for _ in range(cnt):
      values.append(score)
      weights.append(len(word))
  
  dp = [0] * (t + 1)
  for v, w in zip(values, weights):
    for x in range(max(-1, t - w), -1, -1):
      dp[x + w] = max(dp[x + w], dp[x] + v)
  print(max(dp)) 

main()


Fixed submission:
def main():
  n = int(input())
  lst = []
  for _ in range(n):
    word, score = input().split()
    lst.append((word, int(score)))
  mp = ["#" * 6] + ["#" + input() + "#" for _ in range(4)] + ["#" * 6]
  t = int(input())
  
  def search(word):
    used = [[False] * 6 for _ in range(6)]
    vec = ((1, 0), (1, -1), (0, -1), (-1, -1), (-1, 0), (-1, 1), (0, 1), (1, 1))
    
    def _search(word, pos, x, y):
      if pos == len(word) - 1:return 1
      used[y][x] = True
      ret = 0
      for dx, dy in vec:
        nx, ny = x + dx, y + dy
        if not used[ny][nx] and mp[ny][nx] == word[pos + 1]:
          ret += _search(word, pos + 1, nx, ny)
      used[y][x] = False
      return ret
    
    ret = 0
    for y in range(1, 5):
      for x in range(1, 5):
        if mp[y][x] == word[0]:ret += _search(word, 0, x, y)  
    return ret
  
  items = []
  for word, score in lst:
    cnt = search(word)
    acc = 1
    weight = len(word)
    while cnt >= acc:
      cnt -= acc
      items.append((score * acc, weight * acc))
      acc *= 2
    if cnt:
      items.append((score * cnt, weight * cnt))
  
  dp = [0] * (t + 1)
  for v, w in items:
    for x in range(t - w, -1, -1):
      if dp[x + w] < dp[x] + v:dp[x + w] = dp[x] + v
  print(max(dp)) 

main()