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: Time Limit Exceeded

Solution code:
def main():
    s = input()
    n = len(s)
    k = int(input())
    # dp[使った回数][左端からの距離][左端]
    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()

Submission status: Time Limit Exceeded

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 cnt in range(1, k+1):
            for i in range(n-1):
                dp[i][1][cnt] = 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: Time Limit Exceeded

Solution code:
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()
  if lk * 2 >= ls:
    print(ls)
    return
  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()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
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]*(lk+1) for _ in range(ls)] for i in range(ls)]
  for i in range(ls):
    dp[i][i][0] = 1
  for k in range(lk+1):
    for dis in range(1, ls):
      for i in range(ls - dis):
        j = i + dis
        if s[i] == s[j]:
          dp[i][j][k] = dp[i+1][j-1][k] + 2
        elif k:
          dp[i][j][k] = dp[i+1][j-1][k-1] + 2
        dp[i][j][k] = max(dp[i][j][k], dp[i+1][j][k], dp[i][j-1][k])

  print(max(dp[0][ls-1]))
  return

solve()

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

s = ns()
ls = len(s)
lk = ni()
dp = [[[0]*(lk+1) for _ in range(ls)] for i in range(ls)]
for i in range(ls):
  dp[i][i][0] = 1
for k in range(lk+1):
  for dis in range(1, ls):
    for i in range(ls - dis):
      j = i + dis
      if s[i] == s[j]:
        dp[i][j][k] = dp[i+1][j-1][k] + 2
      elif k:
        dp[i][j][k] = dp[i+1][j-1][k-1] + 2
      dp[i][j][k] = max(dp[i][j][k], dp[i+1][j][k], dp[i][j-1][k])
      
print(max(dp[0][ls-1]))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


s = S()
n = len(s)
k = I()
dp = defaultdict(lambda:1)
for diff in range(1, n):
    for l in range(n):
        for m in range(k + 1):
            r = l + diff
            if r >= n:
                continue
            if r - l == 1:
                dp[(l, r, m)] = 2 if s[l] == s[r] or m else 1
            elif s[l] == s[r]:
                dp[(l, r, m)] = dp[(l + 1, r - 1, m)] + 2
            else:
                dp[(l, r, m)] = max(dp[(l, r, m)], dp[(l + 1, r, m)], dp[(l, r - 1, m)])
                if m:
                    dp[(l, r, m)] = max(dp[(l, r, m)], dp[(l + 1, r - 1, m - 1)] + 2)

print(dp[(0, n - 1, k)])

Submission status: Time Limit Exceeded

Solution code:
s = list(map(ord, list(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]:
        if dp[i+1][j+1][k] < dp[i][j][k] + 1:
          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: Time Limit Exceeded

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

# MLE対策
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]))

Submission status: Time Limit Exceeded

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

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]))

Submission status: Time Limit Exceeded

Solution code:
s = input()
k = int(input())
n = len(s)
dp = [[[0]*(n+1) for i in range(n+1)] for j in range(n+1)]
for j in range(k+1):
    for i in range(n):
        dp[i][i+1][j] = 1
for j in range(2,n+1):
  for i in range(n+1-j):
    for l in range(k+1):
      jj = i+j
      if s[i] == s[jj-1]:
        dp[i][jj][l] = dp[i+1][jj-1][l]+2
      else:
        dp[i][jj][l] = max(dp[i+1][jj][l],dp[i][jj-1][l])
        if l-1>=0:
          dp[i][jj][l] = max(dp[i][jj][l],dp[i+1][jj-1][l-1]+2)
ans = 0
for i in range(k+1):
  ans = max(ans,dp[0][n][i])
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
# coding=utf-8

def lcs(s1,s2):
    table = []
    for _ in range(310):
        table.append([0 for _ in range(310)])

    for y in range(1,len(s1)+1):
        for x in range(1,len(s2)+1):
            match = 0
            if s1[y-1]==s2[x-1]:
                match = 1

            v1 = table[y-1][x-1]+match
            v2 = table[y-1][x]
            v3 = table[y][x-1]
            table[y][x] = max(v1,v2,v3)
    return table[len(s1)][len(s2)]

def log(s,s2):
    return
    print("---")
    print("s :"+"".join(s))
    print("s2:"+"".join(s2))

s = list(input())
k = int(input())
s2 = s[::-1]
log(s,s2)

ab = set(s)

for i in range(k):
    idx = -1
    char = ""
    r = -1
    for j in range(len(s)):
        for x in ab:
            t = s[:]
            t[j] = x
            t2 = t[::-1]
            if lcs(t,t2)>r:
                r = lcs(t,t2)
                idx = j
                char = x

    s[idx] = char
    s2 = s[::-1]
    log(s,s2)


print(lcs(s,s2))

Submission status: Memory Limit Exceeded

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][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()

Submission status: Memory Limit Exceeded

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

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

# 長さ1のときの初期化
for i in range(n):
    dp[0][i * OFFSET + 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 * OFFSET + r] = max(2 + dp[ki][(l + 1) * OFFSET + r - 1], dp[ki][l * OFFSET + r])
            else:
                dp[ki][l * OFFSET + r] = max(dp[ki][(l + 1) * OFFSET + r], dp[ki][l * OFFSET + r - 1], dp[ki][l * OFFSET + r])
                if ki - 1 >= 0:
                    dp[ki][l * OFFSET + r] = max(dp[ki - 1][(l + 1) * OFFSET + r - 1] + 2, dp[ki][l * OFFSET + r])

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

Submission status: Memory Limit Exceeded

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


s = S()
n = len(s)
k = I()
dp = [[[1] * (k + 1) for _ in range(n)] for _ in range(n)]
for diff in range(1, n):
    for l in range(n):
        for m in range(k + 1):
            r = l + diff
            if r >= n:
                continue
            if r - l == 1:
                dp[l][r][m] = 2 if s[l] == s[r] or m else 1
            elif s[l] == s[r]:
                dp[l][r][m] = dp[l + 1][r - 1][m] + 2
            else:
                dp[l][r][m] = max(dp[l][r][m], dp[l + 1][r][m], dp[l][r - 1][m])
                if m:
                    dp[l][r][m] = max(dp[l][r][m], dp[l + 1][r - 1][m - 1] + 2)

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

Submission status: Memory Limit Exceeded

Solution code:
def getdp(i, j, k):
    if i < 0: return -1
    if j > k: return 0
    if j == k: return 1
    if dp[i][j][k] != -1: return dp[i][j][k]
    res = -1
    if s[j] == s[k]: res = max(res, getdp(i, j+1, k-1)+2)
    else: res = max(res, getdp(i-1, j+1, k-1)+2, getdp(i, j+1, k), getdp(i, j, k-1))
    dp[i][j][k] = res
    return res

input = raw_input
range = xrange
s = input()
n = len(s)
k = int(input())
dp = [[[-1]*n for j in range(n)] for i in range(k+1)] # score [j..k], i more free slots
print(getdp(k, 0, n-1))

Submission status: Accepted

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-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)

Submission status: Accepted

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

"""

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)

Submission status: Accepted

Solution code:
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)):
            # [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][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()

Submission status: Accepted

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>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(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: Accepted

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

# 長さ1のときの初期化
for i in range(n):
    dp[0][get_ind(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][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)

Submission status: Accepted

Solution code:
def main():
    s = input()
    n = len(s)
    k = int(input())
    # dp[使った回数][左端からの距離][左端]
    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()

Submission status: Accepted

Solution code:
def main():
    s = input()
    n = len(s)
    k = int(input())
    # dp[使った回数][左端からの距離][左端]
    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()

Submission status: Accepted

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)
    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)