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



Sample input:
abcabcabc
1


Sample output:
7

Submission status: Wrong Answer

Solution code:
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+1-i+1)] 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):
#             print(l, i, i+l, j)
            if s[i]==s[i+l-1]:
                dp[i][l][k] = dp[i+1][l-1][k] + 2
            else:
                dp[i][l][k] = max(dp[i+1][l][k], dp[i][l-1][k])
                if k>=1:
                    dp[i][l][k] = max(dp[i][l][k], dp[i+1][l-1][k-1]+2)
ans = max(dp[0][i][j] for i in range(n+2) for j in range(K+1))
print(ans)

Submission status: Wrong Answer

Solution code:
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+1-i+1)] 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):
#             print(l, i, i+l, j)
            if s[i]==s[i+l-1]:
                dp[i][l][k] = dp[i+1][l-1][k] + 2
            else:
                dp[i][l][k] = max(dp[i+1][l][k], dp[i][l-1][k])
                if k>=1:
                    dp[i][l][k] = max(dp[i][l][k], dp[i+1][l-1][k-1]+2)
ans = max(dp[0][n][j] for j in range(K+1))
print(ans)

Submission status: Wrong Answer

Solution code:
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):
#             print(l, i, i+l, j)
            if s[i]==s[i+l-1]:
                dp[i][l][k] = dp[i+1][l-1][k] + 2
            else:
#                 print(i,l,k)
                dp[i][l][k] = max(dp[i+1][l][k], dp[i][l-1][k])
                if k>=1:
                    dp[i][l][k] = max(dp[i][l][k], dp[i+1][l-1][k-1]+2)
ans = max(dp[0][n][j] for j in range(K+1))
print(ans)

Submission status: Wrong Answer

Solution code:

"""

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足す

"""

S = input()
S = " "+S
K = int(input())
N = len(S)-1

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

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

    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)

print (ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline

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

L = len(S)

def main():
    dp = [[[0]*(K+1) for _ in range(L+1)] for _ in range(L+1)]

    ans = 0
    for ind in reversed(range(L)):
        # [0, ind), [ind, L-1]
        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+1][L-ind-1][k] and dp[i+1][L-ind][k] == dp[i][L-ind][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)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline

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

L = len(S)

def main():
    dp = [[[0]*(K+1) for _ in range(L+1)] for _ in range(L+1)]

    ans = 0
    for ind in reversed(range(L)):
        # [0, ind), [ind, L-1]
        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:
                        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)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline

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

L = len(S)

def main():
    dp = [[[0]*(K+1) for _ in range(L+1)] for _ in range(L+1)]

    ans = 0
    for ind in reversed(range(L)):
        # [0, ind), [ind, L-1]
        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], max(i+1, L-ind))
                    if k < 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], max(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)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline

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

L = len(S)

def main():
    dp = [[[0]*(K+1) for _ in range(L+1)] for _ in range(L+1)]

    ans = 0
    for ind in reversed(range(L)):
        # [0, ind), [ind, L-1]
        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], max(i+1, L-ind))
                    if k < 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], max(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)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline

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

L = len(S)

def main():
    dp = [[[0]*(K+1) for _ in range(L+1)] for _ in range(L+1)]

    ans = 0
    for ind in reversed(range(L)):
        # [0, ind), [ind, L-1]
        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], max(i+1, L-ind))
                    if k < 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)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline

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

L = len(S)

def main():
    dp = [[[0]*(K+1) for _ in range(L+1)] for _ in range(L+1)]

    ans = 0
    for ind in reversed(range(L)):
        # [0, ind), [ind, L-1]
        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])
                    if k < K:
                        dp[i+1][L-ind][k+1] = max(dp[i+1][L-ind][k+1], dp[i+1][L-ind][k]+1)
        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)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

# 参考 https://atcoder.jp/contests/agc021/submissions/8392122
def examB():
    def norm2(vec):
        return math.sqrt(vec[0] ** 2 + vec[1] ** 2)
    # any 2 points must have different position.
    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

        # return upper, lower
        # return [pos2idx[xy] for xy in upper], [pos2idx[xy] for xy in lower]

        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
    #print(C)
    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>100:
        K = 100
    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(dp)
    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
"""

Submission status: Wrong Answer

Solution code:
s = input()
n = len(s)
k = int(input())

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

# 長さ1のときの初期化
for i in range(n):
    dp[0][i][i + 1] = 1

# 長さ2~nのときのDP
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][l][r] = max(2 + dp[ki][l + 1][r - 1], dp[ki][l][r])
            else:
                dp[ki][l][r] = max(dp[ki][l + 1][r], dp[ki][l][r - 1], dp[ki][l][r])
                if ki - 1 >= 0:
                    dp[ki][l][r] = max(dp[ki - 1][l + 1][r - 1] + 2, dp[ki - 1][l + 1][r - 1] + 2, dp[ki][l][r])

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

Submission status: Wrong Answer

Solution code:
s = input()
n = len(s)
k = int(input())


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

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

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

Submission status: Wrong Answer

Solution code:
def main():
    s = input()
    n = len(s)
    k = int(input())
    # dp[左端][左端からの右端の距離][使った回数]
    dp = [[[1]*(k+1) for _ in [0]*(n-i)] for i in range(n)]

    for i in range(n-1):
        if s[i] == s[i+1]:
            dp[i][1][0] = 2
    if k > 0:
        for i in range(n-1):
            dp[i][1][1] = 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[left][d][cnt] = max(
                    dp[left][d][cnt], dp[left][d-1][cnt],
                    dp[left+1][d-1][cnt], dp[left+1][d-2][cnt]+plus)
                dp[left][d][cnt+1] = max(
                    max(dp[left][d][cnt:cnt+2]), dp[left+1][d-2][cnt]+2)
    for d in range(2, n):
        for left in range(n-d):
            right = left+d
            plus = (s[left] == s[right])*2
            dp[left][d][k] = max(
                dp[left][d][k], dp[left][d-1][k], dp[left+1][d-1][k], dp[left+1][d-2][k]+plus)
    print(dp[0][-1][-1])


main()

Submission status: Wrong Answer

Solution code:
def main():
    s = input()
    n = len(s)
    k = int(input())
    # dp[左端][左端からの右端の距離][使った回数]
    dp = [[[1]*(k+1) for _ in [0]*(n-i)] for i in range(n)]

    for i in range(n-1):
        if s[i] == s[i+1]:
            dp[i][1][0] = 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[left][d][cnt] = max(
                    dp[left][d][cnt], dp[left][d-1][cnt],
                    dp[left+1][d-1][cnt], dp[left+1][d-2][cnt]+plus)
                dp[left][d][cnt+1] = max(
                    max(dp[left][d][cnt:cnt+2]), dp[left+1][d-2][cnt]+2)
    for d in range(2, n):
        for left in range(n-d):
            right = left+d
            plus = (s[left] == s[right])*2
            dp[left][d][k] = max(
                dp[left][d][k], dp[left][d-1][k], dp[left+1][d-1][k], dp[left+1][d-2][k]+plus)
    print(dp[0][-1][-1])


main()

Submission status: Wrong Answer

Solution code:
def main():
    s = input()
    n = len(s)
    k = int(input())
    # dp[左端][左端からの右端の距離][使った回数]
    dp = [[[2]*(k+1) for _ in [0]*(n-i)] for i in range(n)]

    for i in range(n):
        for cnt in range(k+1):
            dp[i][0][cnt] = 1

    for i in range(n-1):
        if s[i] != s[i+1]:
            dp[i][1][0] = 1

    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[left][d][cnt] = max(
                    dp[left][d][cnt], dp[left][d-1][cnt],
                    dp[left+1][d-1][cnt], dp[left+1][d-2][cnt]+plus)
                dp[left][d][cnt+1] = max(
                    max(dp[left][d][cnt:cnt+2]), dp[left+1][d-2][cnt]+2)
    for d in range(2, n):
        for left in range(n-d):
            right = left+d
            plus = (s[left] == s[right])*2
            dp[left][d][k] = max(
                dp[left][d][k], dp[left][d-1][k], dp[left+1][d-1][k], dp[left+1][d-2][k]+plus)
    print(dp[0][-1][-1])


main()

Submission status: Wrong Answer

Solution code:
def main():
    s = input()
    n = len(s)
    k = int(input())
    # dp[左端][左端からの右端の距離][使った回数]
    dp = [[[2]*(k+1) for _ in [0]*(n-i)] for i in range(n)]

    for i in range(n):
        for cnt in range(k+1):
            dp[i][0][cnt] = 1

    for i in range(n-1):
        if s[i] != s[i+1]:
            dp[i][1][0] = 1

    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[left][d][cnt] = max(
                    dp[left][d][cnt], dp[left][d-1][cnt],
                    dp[left+1][d-1][cnt], dp[left+1][d-2][cnt]+plus)
                dp[left][d][cnt+1] = max(
                    max(dp[left][d][cnt:cnt+2]), dp[left+1][d-2][cnt]+2)
    for d in range(2, n):
        for left in range(n-d):
            right = left+d
            plus = (s[left] == s[right])*2
            dp[left][d][k] = max(
                dp[left][d][k], dp[left][d-1][k], dp[left+1][d-2][k]+plus)
    print(dp[0][-1][-1])


main()

Submission status: Wrong Answer

Solution code:
def main():
    s = input()
    n = len(s)
    k = int(input())
    # dp[左端][左端からの右端の距離][使った回数]
    dp = [[[2]*(k+1) for _ in [0]*(n-i)] for i in range(n)]

    for i in range(n):
        for cnt in range(k+1):
            dp[i][0][cnt] = 1

    for i in range(n-1):
        if s[i] != s[i+1]:
            dp[i][1][0] = 1

    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[left][d][cnt] = max(
                    dp[left][d][cnt], dp[left][d-1][cnt], dp[left+1][d-2][cnt]+plus)
                dp[left][d][cnt+1] = max(
                    max(dp[left][d][cnt:cnt+2]), dp[left+1][d-2][cnt]+2)
    for d in range(2, n):
        for left in range(n-d):
            right = left+d
            plus = (s[left] == s[right])*2
            dp[left][d][k] = max(
                dp[left][d][k], dp[left][d-1][k], dp[left+1][d-2][k]+plus)
    print(dp[0][-1][-1])


main()

Submission status: Wrong Answer

Solution code:
s = input()
n = len(s)
K = int(input())

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
		if i < n-1 and s[i] == s[i+1]:
			dp[i][i+1][k] = 2

for k in range(K+1):
	for x in range(1, n):
		for i in range(n-x):
			j = i+x
			dp[i][j][k] = max(dp[i][j][k-1], dp[i+1][j][k], dp[i][j-1][k])
			if s[i] == s[j] and x > 1:
				dp[i][j][k] = max(dp[i][j][k], dp[i+1][j-1][k] + 2)
			elif k > 0 and x > 1:
				dp[i][j][k] = max(dp[i][j][k], dp[i+1][j-1][k-1] + 2)

print(dp[0][n-1][K])

Submission status: Wrong Answer

Solution code:
import sys
s = input()
n = len(s)
K = int(input())

dp = [[[0 for _ in range(K+1)] for _ in range(n)] for _ in range(n)]
for i in range(n):
	dp[i][i][0] = 1
	if i < n-1 and s[i] == s[i+1]:
		dp[i][i+1][0] = 2

for k in range(K+1):
	for x in range(1, n):
		for i in range(n-x):
			j = i+x
			dp[i][j][k] = max(dp[i][j][k-1], dp[i+1][j][k], dp[i][j-1][k])
			if s[i] == s[j] and x > 1:
				dp[i][j][k] = max(dp[i][j][k], dp[i+1][j-1][k] + 2)
			elif k > 0:
				dp[i][j][k] = max(dp[i][j][k], dp[i+1][j-1][k-1] + 2)

print(dp[0][n-1][K])

Submission status: Wrong Answer

Solution code:
import sys
s = input()
n = len(s)
K = int(input())

dp = [[[0 for _ in range(K+1)] for _ in range(n)] for _ in range(n)]
for i in range(n):
	dp[i][i][0] = 1
	if i < n-1:
		dp[i][i+1][0] = 2

for k in range(K+1):
	for x in range(1, n):
		for i in range(n-x):
			j = i+x
			dp[i][j][k] = max(dp[i][j][k-1], dp[i+1][j][k], dp[i][j-1][k])
			if s[i] == s[j] and x > 1:
				dp[i][j][k] = max(dp[i][j][k], dp[i+1][j-1][k] + 2)
			elif k > 0:
				dp[i][j][k] = max(dp[i][j][k], dp[i+1][j-1][k-1] + 2)

print(dp[0][n-1][K])

Submission status: Wrong Answer

Solution code:
s = input()
ls = len(s)
lk = int(input())
if lk*2 >= ls: print(ls); exit(0)
lk *= 2
dp = [[[0]*(lk+1) for _ in range(ls+1)] for i in range(ls+1)]
for k in range(lk+1):
  for i in range(ls):
    for j in range(ls):
      if s[i] == s[-j-1]:
        dp[i+1][j+1][k] = max(dp[i+1][j+1][k], dp[i][j][k] + 1)
      else:
        dp[i+1][j+1][k] = max(dp[i+1][j+1][k], dp[i+1][j][k], dp[i][j+1][k], (k > 0)*(dp[i][j][k-1] + 1))
print(max(dp[ls][ls]))

Submission status: Wrong Answer

Solution code:
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)

Submission status: Wrong Answer

Solution code:
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)
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)

Submission status: Wrong Answer

Solution code:
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)
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)
  else:
    ans= max(dp[sfl][sll][K]*2+1,dp[sfl][sll-1][max(0,K-1)]*2+2,ans)
print(ans)

Submission status: Wrong Answer

Solution code:
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)
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][min(sll-1,K)]*2+2,ans)
  else:
    ans= max(dp[sfl][sll][K]*2+1,dp[sfl][sll-1][min(sll-1,K-1)]*2+2,ans)
print(ans)

Submission status: Wrong Answer

Solution code:
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)
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)
  else:
    ans= max(dp[sfl][sll][K]*2+1,dp[sfl][sll-1][K-1]*2+2,ans)
print(ans)

Submission status: Wrong Answer

Solution code:
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)
for center in range(1,n-1):
  flg = 0
  sf = s[:center]
  sl = t[:n-center-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])
  ans= max(dp[sfl][sll][K]*2+1,dp[sfl][sll-1][K]*2+2,ans)
print(ans)