Problem p03430 (python)

Fixed submission:
s = input()
K = int(input())
n = len(s)
t = s[::-1]
if 2*K+1 >= n:
  print(n)
  exit()
dp = [[[0 for i in range(K+1)] for j in range(n+1)] for k in range(n+1)]
if n == 2 and K == 0:
  if s == t:
    print(2)
    exit()
  else:
    print(1)
    exit()
ans = min(2*K+1,n)
for center in range(1,n-1):
  flg = 0
  sf = s[:center]
  sl = t[:n-center-1]
  if s[center] == s[center+1]:
    flg = 1
  sfl = len(sf)
  sll = len(sl)
  for j in range(1,sll+1):
    dp[sfl][j][0] = max(dp[sfl-1][j][0],dp[sfl][j-1][0])
    if sf[-1] != sl[j-1]:
      for k in range(1,K+1):
        dp[sfl][j][k] = max(dp[sfl-1][j-1][k-1]+1,dp[sfl-1][j][k],dp[sfl][j-1][k])
    if sf[-1] == sl[j-1]:
      dp[sfl][j][0] = max(dp[sfl][j][0],dp[sfl-1][j-1][0]+1)
      for k in range(1,K+1):
        dp[sfl][j][k] = max(dp[sfl-1][j-1][k-1]+1,dp[sfl-1][j-1][k]+1,dp[sfl-1][j][k],dp[sfl][j-1][k])
  if flg:
    ans= max(dp[sfl][sll][K]*2+1,dp[sfl][sll-1][K]*2+2,ans)
  elif K > 0:
    ans= max(dp[sfl][sll][K]*2+1,dp[sfl][sll-1][K-1]*2+2,ans)
  else:
    ans= max(dp[sfl][sll][K]*2+1,ans)
print(ans)

Buggy submission (verdict: Runtime Error):
s = input()
K = int(input())
n = len(s)
t = s[::-1]
if 2*K+1 >= n:
  print(n)
  exit()
dp = [[[0 for i in range(K+1)] for j in range(n+1)] for k in range(n+1)]
if n == 2 and k == 0:
  if s == t:
    print(2)
  else:
    print(1)
    exit()
ans = min(2*K+1,n)
for center in range(1,n-1):
  flg = 0
  sf = s[:center]
  sl = t[:n-center-1]
  if s[center] == s[center+1]:
    flg = 1
  sfl = len(sf)
  sll = len(sl)
  for j in range(1,sll+1):
    dp[sfl][j][0] = max(dp[sfl-1][j][0],dp[sfl][j-1][0])
    if sf[-1] != sl[j-1]:
      for k in range(1,K+1):
        dp[sfl][j][k] = max(dp[sfl-1][j-1][k-1]+1,dp[sfl-1][j][k],dp[sfl][j-1][k])
    if sf[-1] == sl[j-1]:
      dp[sfl][j][0] = max(dp[sfl][j][0],dp[sfl-1][j-1][0]+1)
      for k in range(1,K+1):
        dp[sfl][j][k] = max(dp[sfl-1][j-1][k-1]+1,dp[sfl-1][j-1][k]+1,dp[sfl-1][j][k],dp[sfl][j-1][k])
  if flg:
    ans= max(dp[sfl][sll][K]*2+1,dp[sfl][sll-1][K]*2+2,ans)
  elif K > 0:
    ans= max(dp[sfl][sll][K]*2+1,dp[sfl][sll-1][K-1]*2+2,ans)
  else:
    ans= max(dp[sfl][sll][K]*2+1,ans)
print(ans)

Buggy submission (verdict: Runtime Error):
s = input()
K = int(input())
n = len(s)
t = s[::-1]
if 2*K+1 >= n:
  print(n)
  exit()
dp = [[[0 for i in range(K+1)] for j in range(n+1)] for k in range(n+1)]

ans = min(2*K+1,n)
flg2 = 0
for center in range(1,n-1):
  flg = 0
  sf = s[:center]
  sl = t[:n-center-1]
  if s[center] == s[center+1]:
    flg = 1
  sfl = len(sf)
  sll = len(sl)
  for j in range(1,sll+1):
    dp[sfl][j][0] = max(dp[sfl-1][j][0],dp[sfl][j-1][0])
    if sf[-1] != sl[j-1]:
      for k in range(1,K+1):
        dp[sfl][j][k] = max(dp[sfl-1][j-1][k-1]+1,dp[sfl-1][j][k],dp[sfl][j-1][k])
    if sf[-1] == sl[j-1]:
      dp[sfl][j][0] = max(dp[sfl][j][0],dp[sfl-1][j-1][0]+1)
      for k in range(1,K+1):
        dp[sfl][j][k] = max(dp[sfl-1][j-1][k-1]+1,dp[sfl-1][j-1][k]+1,dp[sfl-1][j][k],dp[sfl][j-1][k])
  if ans < max(dp[sfl][sll][K]*2+1,dp[sfl][sll-1][K]*2+1+flg):
    flg2 = flg
  ans= max(dp[sfl][sll][K]*2+1,dp[sfl][sll-1][K]*2+1+flg,ans)
if flg2 == 1:
  print(2/0)
print(ans)

Buggy submission (verdict: Runtime Error):
s = input()
K = int(input())
n = len(s)
t = s[::-1]
dp = [[[0 for i in range(K+1)] for j in range(n+1)] for k in range(n+1)]
ansls = min(2*K+1,n)
for center in range(1,n-1):
  flg = 0
  sf = s[:center]
  sl = t[:n-center-1]
  if s[center] == s[center+1]:
    flg = 1
  sfl = len(sf)
  sll = len(sl)
  for j in range(1,sll+1):
    dp[sfl][j][0] = max(dp[sfl-1][j][0],dp[sfl][j-1][0])
    if sf[-1] != sl[j-1]:
      for k in range(1,min(K,sll)+1):
        dp[sfl][j][k] = max(dp[sfl-1][j-1][k-1]+1,dp[sfl-1][j][k],dp[sfl][j-1][k])
    if sf[-1] == sl[j-1]:
      dp[sfl][j][0] = max(dp[sfl][j][0],dp[sfl-1][j-1][0]+1)
      for k in range(1,min(K,sll)+1):
        dp[sfl][j][k] = max(dp[sfl-1][j-1][k-1]+1,dp[sfl-1][j-1][k]+1,dp[sfl-1][j][k],dp[sfl][j-1][k])
  ans= max(dp[sfl][sll][min(K,sll)]*2+1,dp[sfl][sll-1][min(K,sll)]*2+1+flg,ans)
print(max(ansls))