Problem:
 Score : 900 points    Problem Statement Takahashi has decided to give a string to his mother.  The value of a string T is the length of the longest common subsequence of T and T' , where T' is the string obtained by reversing T .
That is, the value is the longest length of the following two strings that are equal: a subsequence of T (possibly non-contiguous), and a subsequence of T' (possibly non-contiguous).  Takahashi has a string S . He wants to give her mother a string of the highest possible value, so he would like to change at most K characters in S to any other characters in order to obtain a string of the highest possible value.
Find the highest possible value achievable.      Constraints  1 \leq |S| \leq 300  0 \leq K \leq |S|  S consists of lowercase English letters.  K is an integer.         Input Input is given from Standard Input in the following format:  S  K       Output Print the highest possible value achievable.        Sample Input 1 abcabcabc
1      Sample Output 1 7  Changing the first character to c results in cbcabcabc .
Let this tring be T , then one longest common subsequence of T and T' is cbabcbc , whose length is 7 .       Sample Input 2 atcodergrandcontest
3      Sample Output 2 15

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")



s = input()
K = int(input())
n = len(s)
dp = [[[0]*(K+1) for _ in range(n+2-i)] for i in range(n+1)]
for i in range(n):
    for j in range(K+1):
        dp[i][1][j] = 1
for l in range(2, n+1):
    for i in range(n-l+1):
        for k in range(K+1):

            if s[i]==s[i+l-1]:
                dp[i][l][k] = dp[i+1][l-2][k] + 2
            else:
                dp[i][l][k] = max(dp[i+1][l-1][k], dp[i][l-1][k])
                if k>=1:
                    dp[i][l][k] = max(dp[i][l][k], dp[i+1][l-2][k-1]+2)
ans = max(dp[0][i][j] for i in range(n+2) for j in range(K+1))
print(ans)

Solution (Python):

"""

https://atcoder.jp/contests/agc021/tasks/agc021_d

ある部分でcutしたとする。
前半と後半のLCSを求めたとすると、交差した後のLCSの長さも同じ
→左からindex iまでと右からindex jまでのLCSを求めればいい (i < j)
あとは、普通のLCSと同様のdpでいける

dp[i][j][k] = 左からi番目の文字までと、右からindex jの文字までのk回替えた際のLCS長さ
あとは2倍すれば大体行ける？
i+1 == jでは、2倍すればおk
i+1 < j では、真ん中の文字を使えるので、2倍して1足す

"""

import sys
S = input()
S = " "+S
K = int(input())
N = len(S)-1
if N == 1:
    print (1)
    sys.exit()
elif N == 2:
    if S[1] == S[2] or K > 0:
        print (2)
    else:
        print (1)
    sys.exit()

dp = [[[0] * (K+1) for i in range(N+2)]]
ans = 0

for i in range(1,N+1):

    dp.append( [[0] * (K+1) for i in range(N+2)] )

    for j in range(N,i,-1):

        for k in range(K+1):

            
            if S[i] == S[j]:
                dp[i][j][k] = max( dp[i][j][k] , dp[i-1][j+1][k] + 1)
            else:
                dp[i][j][k] = max( dp[i][j][k] , dp[i-1][j][k] , dp[i][j+1][k] )
                if k != 0:
                    dp[i][j][k] = max(dp[i][j][k] , dp[i-1][j+1][k-1] + 1)

            if i+1 == j:
                ans = max(ans , dp[i][j][k] * 2)
            else:
                ans = max(ans , dp[i][j][k] * 2 + 1)

    dp[i-1] = []

print (ans)

Solution (Python):
import sys
input = sys.stdin.buffer.readline

S = list(input().rstrip())
K = int(input())

L = len(S)

def main():
    if K >= L//2:
        ans = L
    else:
        dp = [[[0]*(K+1) for _ in range(L+1)] for _ in range(L+1)]

        ans = 0
        for ind in reversed(range(L)):
            
            s = S[ind]
            for i in range(ind):
                for k in reversed(range(K+1)):
                    if S[i] == s:
                        dp[i+1][L-ind][k] = dp[i][L-ind-1][k] + 1
                    else:
                        dp[i+1][L-ind][k] = max(dp[i][L-ind][k], dp[i+1][L-ind-1][k])
                        dp[i+1][L-ind][k] = min(dp[i+1][L-ind][k], min(i+1, L-ind))
                        if k < K and dp[i+1][L-ind][k] == dp[i][L-ind-1][k]:
                            dp[i+1][L-ind][k+1] = max(dp[i+1][L-ind][k+1], dp[i+1][L-ind][k]+1)
                            dp[i+1][L-ind][k+1] = min(dp[i+1][L-ind][k+1], min(i+1, L-ind))
            for k in range(K+1):
                ans = max(ans, 2*dp[ind][L-ind][k])
                ans = max(ans, 2*dp[ind][L-ind-1][k] + 1)
            dp.pop()
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
def examA():
    N = I()
    ans = 0
    print(ans)
    return


def examB():
    def norm2(vec):
        return math.sqrt(vec[0] ** 2 + vec[1] ** 2)
    
    def ConvexHull(point_list):
        pos2idx = {point_list[i]: i for i in range(len(point_list))}
        y_val = defaultdict(list)
        x_list = sorted(list(set([p[0] for p in point_list])))
        for x, y in point_list:
            y_val[x].append(y)

        upper = [(x_list[0], max(y_val[x_list[0]]))]
        lower = [(x_list[0], min(y_val[x_list[0]]))]
        prev = float('inf')
        for xi in x_list[1:]:
            x0, y0 = upper[-1]
            x1, y1 = xi, max(y_val[xi])
            if (y1 - y0) / (x1 - x0) < prev:
                upper.append((x1, y1))
                prev = (y1 - y0) / (x1 - x0)
            else:
                while True:
                    x0, y0 = upper[-1]
                    if len(upper) == 1:
                        upper.append((x1, y1))
                        break
                    x00, y00 = upper[-2]
                    if (y1 - y0) / (x1 - x0) > (y1 - y00) / (x1 - x00):
                        upper.pop()
                    else:
                        prev = (y1 - y0) / (x1 - x0)
                        upper.append((x1, y1))
                        break

        prev = -float('inf')
        for xi in x_list[1:]:
            x0, y0 = lower[-1]
            x1, y1 = xi, min(y_val[xi])
            if (y1 - y0) / (x1 - x0) > prev:
                lower.append((x1, y1))
                prev = (y1 - y0) / (x1 - x0)
            else:
                while True:
                    x0, y0 = lower[-1]
                    if len(lower) == 1:
                        lower.append((x1, y1))
                        break
                    x00, y00 = lower[-2]
                    if (y1 - y0) / (x1 - x0) < (y1 - y00) / (x1 - x00):
                        lower.pop()
                    else:
                        prev = (y1 - y0) / (x1 - x0)
                        lower.append((x1, y1))
                        break

        
        

        upper_idx, lower_idx = [pos2idx[xy] for xy in upper], [pos2idx[xy] for xy in lower]
        if upper_idx[-1] == lower_idx[-1]:
            upper_idx.pop()
        CH_idx = upper_idx
        CH_idx.extend(reversed(lower_idx))
        if CH_idx[0] == CH_idx[-1] and len(CH_idx) > 1:
            CH_idx.pop()
        return CH_idx

    N = I()
    P = [[]for _ in range(N)]
    D = defaultdict(int)
    for i in range(N):
        x,y = LI()
        P[i] = (x,y)
        D[(x,y)] = i
    C = ConvexHull(P)
    ans = [0]*N
    if len(C)==2:
        for c in C:
            ans[c] = 0.5
        for v in ans:
            print(v)
        return
    
    for i,c in enumerate(C):
        s, t, u = C[i - 1], C[i], C[(i + 1) % len(C)]
        x0, y0 = P[s]
        x1, y1 = P[t]
        x2, y2 = P[u]
        vec0 = (y0 - y1, x1 - x0)
        vec1 = (y1 - y2, x2 - x1)
        ans[t] =  math.acos((vec0[0] * vec1[0] + vec0[1] * vec1[1]) / (norm2(vec0) * norm2(vec1))) / (2 * math.pi)
    for v in ans:
        print(v)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    S = SI()
    N = len(S)
    K = I()
    if K>150:
        K = 150
    dp = [[[0]*(K+1) for _ in range(N)] for i in range(N)]
    for i in range(N):
        for j in range(K+1):
            dp[i][i][j] = 1
    for i in range(2,N+1):
        for k in range(K+1):
            for l,r in enumerate(range(i-1,N)):
                if S[l]==S[r]:
                    dp[l][r][k] = dp[l+1][r-1][k] + 2
                else:
                    if k>0:
                        dp[l][r][k] = max(dp[l+1][r][k],dp[l][r-1][k],dp[l+1][r-1][k-1]+2)
                    else:
                        dp[l][r][k] = max(dp[l + 1][r][k], dp[l][r - 1][k])
    ans = max(dp[0][-1])
    
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

from decimal import Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examD()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Solution (Python):
def get_ind(l, r):
    mod = 3
    return OFFSET * (l % mod) + r

s = input()
n = len(s)
k = int(input())

dp = [[0] * ((n + 1) * 3) for i in range(k + 1)]
OFFSET = n + 1


for i in range(n):
    dp[0][get_ind(i, i + 1)] = 1


for length in range(2, n + 1):
    for l in range(n + 1):
        for ki in range(k + 1):
            r = l + length
            if r > n:
                break
            if s[l] == s[r - 1]:
                dp[ki][get_ind(l, r)] = max(2 + dp[ki][get_ind(l + 1, r - 1)], dp[ki][get_ind(l, r)])
            else:
                dp[ki][get_ind(l, r)] = max(dp[ki][get_ind(l + 1, r)], dp[ki][get_ind(l, r - 1)], dp[ki][get_ind(l, r)])
                if ki - 1 >= 0:
                    dp[ki][get_ind(l, r)] = max(dp[ki - 1][get_ind(l + 1, r - 1)] + 2, dp[ki][get_ind(l, r)])

ans = 0
for i in range(k + 1):
    for j in range(3 * (n + 1)):
        ans = max(ans, dp[i][j])
print(ans)

Solution (Python):
def main():
    s = input()
    n = len(s)
    k = int(input())
    
    dp = [[[1]*(n-i) for i in range(n)] for _ in range(k+1)]

    if n == 1:
        print(1)
        return
    dp2 = dp[0][1]
    for i in range(n-1):
        if s[i] == s[i+1]:
            dp2[i] = 2
    if k > 0:
        for cnt in range(1, k+1):
            dp2 = dp[cnt][1]
            for i in range(n-1):
                dp2[i] = 2

    for cnt in range(k):
        dp2 = dp[cnt]
        dp4 = dp[cnt+1]
        for d in range(2, n):
            dp3 = dp2[d]
            dp5 = dp2[d-1]
            dp6 = dp2[d-2]
            dp7 = dp4[d]
            for left in range(n-d):
                right = left+d
                plus = (s[left] == s[right])*2
                dp3[left] = max(
                    dp3[left], dp5[left],
                    dp5[left+1], dp6[left+1]+plus)
                dp7[left] = max(
                    dp7[left], dp3[left], dp6[left+1]+2)
    dp2 = dp[k]
    for d in range(2, n):
        dp3 = dp2[d]
        dp4 = dp2[d-1]
        dp5 = dp2[d-2]
        for left in range(n-d):
            right = left+d
            plus = (s[left] == s[right])*2
            dp3[left] = max(
                dp3[left], dp4[left], dp4[left+1], dp5[left+1]+plus)
    print(dp[-1][-1][0])


main()

Solution (Python):
def main():
    s = input()
    n = len(s)
    k = int(input())
    
    dp = [[[1]*(n-i) for i in range(n)] for _ in range(k+1)]

    if n == 1:
        print(1)
        return
    dp2 = dp[0][1]
    for i in range(n-1):
        if s[i] == s[i+1]:
            dp2[i] = 2
    if k > 0:
        for cnt in range(1, k+1):
            dp2 = dp[cnt][1]
            for i in range(n-1):
                dp2[i] = 2

    for cnt in range(k):
        dp2 = dp[cnt]
        for d in range(2, n):
            dp3 = dp2[d]
            for left in range(n-d):
                right = left+d
                plus = (s[left] == s[right])*2
                dp3[left] = max(
                    dp3[left], dp2[d-1][left],
                    dp2[d-1][left+1], dp2[d-2][left+1]+plus)
                dp[cnt+1][d][left] = max(
                    dp[cnt+1][d][left], dp3[left], dp2[d-2][left+1]+2)
    dp2 = dp[k]
    for d in range(2, n):
        dp3 = dp2[d]
        for left in range(n-d):
            right = left+d
            plus = (s[left] == s[right])*2
            dp3[left] = max(
                dp3[left], dp2[d-1][left], dp2[d-1][left+1], dp2[d-2][left+1]+plus)
    print(dp[-1][-1][0])


main()

Solution (Python):
def main():
    s = input()
    n = len(s)
    k = int(input())
    
    dp = [[[1]*(n-i) for i in range(n)] for _ in range(k+1)]

    for i in range(n-1):
        if s[i] == s[i+1]:
            dp[0][1][i] = 2
    if k > 0:
        for cnt in range(1, k+1):
            for i in range(n-1):
                dp[cnt][1][i] = 2

    for cnt in range(k):
        for d in range(2, n):
            for left in range(n-d):
                right = left+d
                plus = (s[left] == s[right])*2
                dp[cnt][d][left] = max(
                    dp[cnt][d][left], dp[cnt][d-1][left],
                    dp[cnt][d-1][left+1], dp[cnt][d-2][left+1]+plus)
                dp[cnt+1][d][left] = max(
                    dp[cnt+1][d][left], dp[cnt][d][left], dp[cnt][d-2][left+1]+2)
    for d in range(2, n):
        for left in range(n-d):
            right = left+d
            plus = (s[left] == s[right])*2
            dp[k][d][left] = max(
                dp[k][d][left], dp[k][d-1][left], dp[k][d-1][left+1], dp[k][d-2][left+1]+plus)
    print(dp[-1][-1][0])


main()

Solution (Python):
import sys

readline = sys.stdin.buffer.readline

ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))

def solve():
  s = list(ns())
  ls = len(s)
  lk = ni()
  dp = [[[0]*ls for _ in range(ls)] for i in range(2)]
  ans = 0
  for i in range(ls):
    dp[0][i][i] = 1
  for k in range(lk+1):
    v = k & 1
    for dis in range(1, ls):
      for i in range(ls - dis):
        j = i + dis
        dp[v][i][j] = 0
        if s[i] == s[j]:
          dp[v][i][j] = dp[v][i+1][j-1] + 2
        elif k:
          dp[v][i][j] = dp[v^1][i+1][j-1] + 2
        dp[v][i][j] = max(dp[v][i][j], dp[v][i+1][j], dp[v][i][j-1])
    ans = max(ans, dp[v][0][-1])

  print(ans)
  return

solve()

Solution (Python):
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)

Solution (Python):
import sys
readline = sys.stdin.readline

S = list(map(ord, readline().strip()))
N = len(S)
S = [None] + S + [None]
K = int(readline())

if N == 1:
    ans = 1
elif N == 2:
    ans = 1
    if S[1] == S[2]:
        ans = 2
    if K:
        ans = 2
else:
    dp1 = [[0]*(K+1) for _ in range(N+2)]
    dp2 = [[0]*(K+1) for _ in range(N+2)]
    for i in range(1, N+1):
        dp1[i][0] = 1
    for i in range(1, N):
        dp2[i][0] = 1
        if S[i] == S[i+1]:
            dp2[i][0] = 2    
        elif K:    
            dp2[i][1] = 2
    for s in range(3, N+1):
        dp3 = [[0]*(K+1) for _ in range(N+2)]
        for i in range(1, N-s+2):
            j = i+s-1    
            if S[i] == S[j]:
                for k in range(K+1):
                    dp3[i][k] = max(dp2[i+1][k], dp2[i][k], 2+dp1[i+1][k])
            else:
                dp3[i][0] = max(dp2[i+1][0], dp2[i][0], dp2[i+1][0])
                for k in range(1, K+1):
                    dp3[i][k] = max(dp2[i+1][k], dp2[i][k], dp1[i+1][k], 2+dp1[i+1][k-1])
        '''
        dp1 = [k[:] for k in dp2]
        dp2 = [k[:] for k in dp3]
        '''
        dp1 = dp2[:]
        dp2 = dp3[:]
    ans = max(dp3[1][k] for k in range(K+1))
print(ans)
'''
MLEした
dp = [[[0]*(K+1) for _ in range(N+2)] for _ in range(N+2)]
for i in range(1, N+1):
    dp[i][i][0] = 1
for i in range(1, N):
    dp[i][i+1][0] = 1
    if S[i] == S[i+1]:
        dp[i][i+1][0] = 2    
    elif K:    
        dp[i][i+1][1] = 2
for s in range(3, N+1):
    for i in range(1, N-s+2):
        j = i+s-1
        if S[i] == S[j]:
            for k in range(K+1):
                dp[i][j][k] = max(dp[i+1][j][k], dp[i][j-1][k], 2+dp[i+1][j-1][k])
        else:
            dp[i][j][0] = max(dp[i+1][j][0], dp[i][j-1][0], dp[i+1][j-1][0])
            for k in range(1, K+1):
                dp[i][j][k] = max(dp[i+1][j][k], dp[i][j-1][k], dp[i+1][j-1][k], 2+dp[i+1][j-1][k-1], dp[i+1][j-1][k])
print(max(dp[1][N][k] for k in range(K+1)))
'''

Solution (Python):
import sys
readline = sys.stdin.readline

S = list(map(ord, readline().strip()))
N = len(S)
S = [None] + S + [None]
K = int(readline())

if N == 1:
    ans = 1
elif N == 2:
    ans = 1
    if S[1] == S[2]:
        ans = 2
    if K:
        ans = 2
else:
    dp1 = [[0]*(K+1) for _ in range(N+2)]
    dp2 = [[0]*(K+1) for _ in range(N+2)]
    for i in range(1, N+1):
        dp1[i][0] = 1
    for i in range(1, N):
        dp2[i][0] = 1
        if S[i] == S[i+1]:
            dp2[i][0] = 2    
        elif K:    
            dp2[i][1] = 2
    for s in range(3, N+1):
        dp3 = [[0]*(K+1) for _ in range(N+2)]
        for i in range(1, N-s+2):
            j = i+s-1    
            if S[i] == S[j]:
                for k in range(K+1):
                    dp3[i][k] = max(dp2[i+1][k], dp2[i][k], 2+dp1[i+1][k])
            else:
                dp3[i][0] = max(dp2[i+1][0], dp2[i][0], dp2[i+1][0])
                for k in range(1, K+1):
                    dp3[i][k] = max(dp2[i+1][k], dp2[i][k], dp1[i+1][k], 2+dp1[i+1][k-1])
        dp1 = [k[:] for k in dp2]
        dp2 = [k[:] for k in dp3]
    ans = max(dp3[1][k] for k in range(K+1))
print(ans)
'''
MLEした
dp = [[[0]*(K+1) for _ in range(N+2)] for _ in range(N+2)]
for i in range(1, N+1):
    dp[i][i][0] = 1
for i in range(1, N):
    dp[i][i+1][0] = 1
    if S[i] == S[i+1]:
        dp[i][i+1][0] = 2    
    elif K:    
        dp[i][i+1][1] = 2
for s in range(3, N+1):
    for i in range(1, N-s+2):
        j = i+s-1
        if S[i] == S[j]:
            for k in range(K+1):
                dp[i][j][k] = max(dp[i+1][j][k], dp[i][j-1][k], 2+dp[i+1][j-1][k])
        else:
            dp[i][j][0] = max(dp[i+1][j][0], dp[i][j-1][0], dp[i+1][j-1][0])
            for k in range(1, K+1):
                dp[i][j][k] = max(dp[i+1][j][k], dp[i][j-1][k], dp[i+1][j-1][k], 2+dp[i+1][j-1][k-1], dp[i+1][j-1][k])
print(max(dp[1][N][k] for k in range(K+1)))
'''

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

"""
・reversed LCS = 最大長の回文
・(長さ、始点、変更コスト) -> opt value
"""

S = np.frombuffer(readline().rstrip(),'S1')
N = len(S)
K = int(readline())

dp = [None] * (N+1) 
dp[0] = None 
dp[1] = np.zeros((N,K+10),np.int32); dp[1][:,0] = 1
if N >= 2:
    dp[2] = np.zeros((N-1,K+10),np.int32)
    dp[2][:,0] = 1+(S[:-1]==S[1:])
    dp[2][:,1] = 2

for n in range(3,N+1):
    arr = np.zeros((N-n+1,K+10),np.int32)
    
    np.maximum(arr,dp[n-1][:-1],out=arr)
    np.maximum(arr,dp[n-1][1:],out=arr)
    
    match = (S[:-n+1]==S[n-1:])
    np.maximum(arr,match[:,None]*(dp[n-2][1:-1]+2),out=arr)
    
    np.maximum(arr[:,1:],dp[n-2][1:-1,:-1]+2,out=arr[:,1:])
    
    dp[n] = arr

answer = dp[-1][0][:K+1].max()
print(answer)

Solution (Python):
S = input()
K = int(input())
N = len(S)


if K * 2 >= N-1:
    print(N)
    exit()

dp = [[[0 for _ in range(K+1)] for _ in range(N)] for _ in range(N)]
for i in range(N):
    for k in range(K+1):
        dp[i][i][k] = 1

for _j in range(1, N):
    for i in range(N):
        j = i + _j
        if j < N:
            for k in range(K+1):
                dp[i][j][k] = max(dp[i][j][k], dp[i+1][j][k], dp[i][j-1][k])
                if _j == 1:
                    if S[i] == S[j]:
                        dp[i][j][k] = 2
                    else:
                        if k+1 <= K:
                            dp[i][j][k+1] = 2
                else:
                    if S[i] == S[j]:
                        dp[i][j][k] = max(dp[i][j][k], dp[i+1][j-1][k] + 2)
                    else:
                        if k+1 <= K:
                            dp[i][j][k+1] = max(dp[i][j][k], dp[i+1][j-1][k] + 2)

print(max(dp[0][N-1]))

Solution (Python):
def solve(s, k):
    n = len(s)
    if k >= n // 2:
        return n
    dpp = [[1] * (k + 1), [0] * (k + 1)]
    for r in range(1, n):
        dpc = [[0] * (k + 1) for _ in range(r + 2)]
        dpc[r] = [1] * (k + 1)
        for l in range(r - 1, -1, -1):
            dpl, dpl1 = dpc[l], dpp[l + 1]
            if s[l] == s[r]:
                dpc[l] = [c + 2 for c in dpl1]
            else:
                dppl, dpcl1 = dpp[l], dpc[l + 1]
                dpl[0] = max(dppl[0], dpcl1[0])
                for p in range(1, k + 1):
                    dpl[p] = max(dppl[p], dpcl1[p], dpl1[p - 1] + 2)
        dpp = dpc

    return dpp[0][k]


print(solve(input(), int(input())))

Solution (Python):
def solve(s, k):
    n = len(s)
    pdp = [[0] * (k + 1) for _ in range(n + 1)]
    for l in range(n - 1, -1, -1):
        dp = [[0] * (k + 1) for _ in range(n + 1)]
        for r in range(l, n):
            dpr, dpr1 = dp[r], pdp[r - 1]
            inc = 1 if l == r else 2
            is_same = s[l] == s[r]
            for p in range(k + 1):
                if is_same:
                    dpr[p] = dpr1[p] + inc
                else:
                    if p:
                        dpr[p] = max(pdp[r][p], dp[r - 1][p], dpr1[p - 1] + inc)
                    else:
                        dpr[p] = max(pdp[r][p], dp[r - 1][p])
        pdp = dp

    return pdp[-2][k]


print(solve(input(), int(input())))