Problem:


Score : 100 points

Problem Statement

You are given strings s and t.
Find one longest string that is a subsequence of both s and t.

Notes

A subsequence of a string x is the string obtained by removing zero or more characters from x and concatenating the remaining characters without changing the order.

Constraints

s and t are strings consisting of lowercase English letters.

1 \leq |s|, |t| \leq 3000

Input

Input is given from Standard Input in the following format:

s
t

Output

Print one longest string that is a subsequence of both s and t.
If there are multiple such strings, any of them will be accepted.

Sample Input 1

axyb
abyxb

Sample Output 1

axb

The answer is axb or ayb; either will be accepted.

Sample Input 2

aa
xayaz

Sample Output 2

aa

Sample Input 3

a
z

Sample Output 3

The answer is  (an empty string).

Sample Input 4

abracadabra
avadakedavra

Sample Output 4

aaadara



Sample input:
axyb
abyxb


Sample output:
axb

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
from functools import lru_cache
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp():
    '''
    一つの整数
    '''
    return int(input())
def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))
def inp_str():
    '''
    一行の文字をlistで取得
    '''
    return list(input())[:-1]
def inpl_str():
    '''
    一行に複数の文字
    '''
    return list(input().split())

class Angle():
    DIAGONAL = 0
    UP = 1
    LEFT = 2

s = inp_str()
t = inp_str()
n = len(s)
m = len(t)
class node():
    def __init__(self):
        self.value = 0
        # self.angle = None
        self.ans=""
dp = [[node() for j in range(m+1)] for i in range(n+1)]
# for i in range(1,n + 1):
#     dp[i][0].angle = Angle.UP
# for j in range(1,m + 1):
#     dp[0][j].angle = Angle.LEFT
for i in range(n):
    for j in range(m):
        if s[i] == t[j]:
            dp[i + 1][j + 1].value = dp[i][j].value + 1
            dp[i + 1][j + 1].ans = dp[i][j].ans + s[i]
        elif dp[i][j + 1].value > dp[i + 1][j].value: #UP
            dp[i + 1][j + 1].ans = dp[i][j + 1].ans
            dp[i + 1][j + 1].value = dp[i][j + 1].value
        else:  # LEFT
            dp[i + 1][j + 1].ans = dp[i + 1][j].ans
            dp[i + 1][j + 1].value = dp[i + 1][j].value

            
# print(dp[n][m].value)
# for i in range(n+1):
#     for j in range(m+1):
#         print(dp[i][j].value,end="")
#     print("")
# print("")
# print("")
# for i in range(n+1):
#     for j in range(m+1):
#         print(dp[i][j].ans,end="")
#     print("")
print(dp[n][m].ans)

Submission status: Time Limit Exceeded

Solution code:
s,t = input(),input()
n,m=len(s),len(t)
dp = [[0]*(n+1) for _ in range(m+1)]

for i in range(m):
    for j in range(n):
        if s[j] == t[i]:
            dp[i+1][j+1] = max(dp[i][j]+1,dp[i+1][j+1])
        
        dp[i+1][j+1] = max(dp[i+1][j+1],dp[i+1][j], dp[i][j+1])

ans = ""
count = 0
while count != dp[-1][-1]:
    if dp[m][n] == dp[m-1][n]:
        m -= 1
    elif dp[m][n] == dp[m][n-1]:
        n -= 1
    else:
        ans += t[m-1]
        count += 1
        m -= 1
        n -= 1

print(ans[::-1])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
from functools import lru_cache
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp():
    '''
    一つの整数
    '''
    return int(input())
def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))
def inp_str():
    '''
    一行の文字をlistで取得
    '''
    return list(input())[:-1]
def inpl_str():
    '''
    一行に複数の文字
    '''
    return list(input().split())

class Angle():
    DIAGONAL = 0
    UP = 1
    LEFT = 2

s = inp_str()
t = inp_str()
n = len(s)
m = len(t)
class node():
    def __init__(self):
        self.value = 0
        # self.angle = None
        self.ans=""
dp = [[node() for j in range(m+1)] for i in range(n+1)]
# for i in range(1,n + 1):
#     dp[i][0].angle = Angle.UP
# for j in range(1,m + 1):
#     dp[0][j].angle = Angle.LEFT
for i in range(n):
    for j in range(m):
        same = dp[i][j].value + 1 if s[i] == t[j] else -1
        up = dp[i][j+1].value
        left = dp[i+1][j].value
        option = [same, up, left]
        max_index = option.index(max(option))
        dp[i + 1][j + 1].value = max(option)
        # dp[i + 1][j + 1].angle = max_index
        if max_index == Angle.DIAGONAL:
            dp[i + 1][j + 1].ans = dp[i][j].ans + s[i]
        elif max_index == Angle.LEFT:
            dp[i + 1][j + 1].ans = dp[i + 1][j].ans
        else:
            dp[i + 1][j + 1].ans = dp[i][j+1].ans

            
# print(dp[n][m].value)
# for i in range(n+1):
#     for j in range(m+1):
#         print(dp[i][j].value,end="")
#     print("")
# print("")
# print("")
# for i in range(n+1):
#     for j in range(m+1):
#         print(dp[i][j].ans,end="")
#     print("")
print(dp[n][m].ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
from functools import lru_cache
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp():
    '''
    一つの整数
    '''
    return int(input())
def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))
def inp_str():
    '''
    一行の文字をlistで取得
    '''
    return list(input())[:-1]
def inpl_str():
    '''
    一行に複数の文字
    '''
    return list(input().split())

class Angle():
    DIAGONAL = 0
    UP = 1
    LEFT = 2

s = inp_str()
t = inp_str()
n = len(s)
m = len(t)
class node():
    def __init__(self):
        self.value = 0
        self.angle = None
        self.ans=""
dp = [[node() for j in range(m+1)] for i in range(n+1)]
for i in range(1,n + 1):
    dp[i][0].angle = Angle.UP
for j in range(1,m + 1):
    dp[0][j].angle = Angle.LEFT
for i in range(n):
    for j in range(m):
        same = dp[i][j].value + 1 if s[i] == t[j] else -1
        up = dp[i][j+1].value
        left = dp[i+1][j].value
        option = [same, up, left]
        max_index = option.index(max(option))
        dp[i + 1][j + 1].value = max(option)
        dp[i + 1][j + 1].angle = max_index
        if max_index == Angle.DIAGONAL:
            dp[i + 1][j + 1].ans = dp[i][j].ans + s[i]
        elif max_index == Angle.LEFT:
            dp[i + 1][j + 1].ans = dp[i + 1][j].ans
        else:
            dp[i + 1][j + 1].ans = dp[i][j+1].ans

            
# print(dp[n][m].value)
# for i in range(n+1):
#     for j in range(m+1):
#         print(dp[i][j].value,end="")
#     print("")
# print("")
# print("")
# for i in range(n+1):
#     for j in range(m+1):
#         print(dp[i][j].ans,end="")
#     print("")
print(dp[n][m].ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
from functools import lru_cache
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp():
    '''
    一つの整数
    '''
    return int(input())
def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))
def inp_str():
    '''
    一行の文字をlistで取得
    '''
    return list(input())[:-1]
def inpl_str():
    '''
    一行に複数の文字
    '''
    return list(input().split())

class Angle():
    DIAGONAL = 0
    UP = 1
    LEFT = 2

s = inp_str()
t = inp_str()
n = len(s)
m = len(t)
class node():
    def __init__(self):
        self.value = 0
        self.angle = None
dp = [[node() for j in range(m+1)] for i in range(n+1)]
for i in range(1,n + 1):
    dp[i][0].angle = Angle.UP
for j in range(1,m + 1):
    dp[0][j].angle = Angle.LEFT
for i in range(n):
    for j in range(m):
        same = dp[i][j].value + 1 if s[i] == t[j] else -1
        up = dp[i][j+1].value
        left = dp[i+1][j].value
        option = [same, up, left]
        max_index = option.index(max(option))
        dp[i + 1][j + 1].value = max(option)
        dp[i + 1][j + 1].angle = max_index
# print(dp[n][m].value)
# for i in range(n+1):
#     for j in range(m+1):
#         print(dp[i][j].value,end="")
#     print("")
# print("")
# for i in range(n+1):
#     for j in range(m+1):
#         print(dp[i][j].angle,end="")
#     print("")
i = n
j = m
ans=[]
while dp[i][j].angle != None:
    if dp[i][j].angle == Angle.DIAGONAL:
        ans.append(s[i-1])
        i -= 1
        j -= 1
    elif dp[i][j].angle == Angle.UP:
        i -= 1
    else:
        j -= 1
print("".join(reversed(ans)))

Submission status: Time Limit Exceeded

Solution code:
s=str(input())
t=str(input())
n,m=len(s),len(t)
ans=''
dp=[[0]*(m+1) for _ in range(n+1)]
for i in range(n):
  for j in range(m):
    if s[i]==t[j]:
      dp[i+1][j+1]=max(dp[i][j]+1,dp[i+1][j+1])
    else:
      dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1])
while m>0 and n>0:
  if s[n-1]==t[m-1]:ans=s[n-1]+ans;n-=1;m-=1
  elif dp[n][m]==dp[n-1][m]:n-=1
  else:m-=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# python3だとTLE,pypy3だとAC
def main():
    s = input()
    t = input()
    dp = [[0 for _ in range(len(t)+1)] for _ in range(len(s)+1)]
    for i, cs in enumerate(s, start=1):
        for j, ct in enumerate(t, start=1):
            if cs == ct:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    ans = ""
    i = len(s)
    j = len(t)
    while i > 0 and j > 0:
        if dp[i][j] == dp[i-1][j]:
            i -= 1
        elif dp[i][j] == dp[i][j-1]:
            j -= 1
        else:
            i -= 1
            j -= 1
            ans = s[i] + ans

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    s = input()
    t = input()
    dp = [[[0, ""] for _ in range(len(t)+1)] for _ in range(len(s)+1)]
    for i, cs in enumerate(s, start=1):
        for j, ct in enumerate(t, start=1):
            if cs == ct:
                dp[i][j][0] = dp[i-1][j-1][0] + 1
                dp[i][j][1] = dp[i-1][j-1][1] + cs
            else:
                dp[i][j][0] = max(dp[i-1][j][0], dp[i][j-1][0])
                dp[i][j][1] = dp[i-1][j][1] if dp[i][j][0] == dp[i -
                                                                 1][j][0] else dp[i][j-1][1]
    print(dp[-1][-1][-1])


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()

dp = [[0]*(len(t)+1) for _ in range(len(s)+1)]

for i in range(len(s)):
    for j in range(len(t)):
        if s[i] == t[j]:
            dp[i+1][j+1] = dp[i][j] + 1
        else:
            dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])

ans = ""
i = len(s)
j = len(t)
while i > 0 and j > 0:
    if dp[i][j] == dp[i-1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j-1]:
        j -= 1
    else:
        ans += s[i-1]
        i -= 1
        j -= 1
print(ans[::-1])

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
lens = len(s)+1
lent = len(t)+1
dps = [""]*lens
for i in range(lens):
    dps[i] = [""]*lent

for i in range(1,lens):
    for j in range(1,lent):
        if s[i-1] == t[j-1]:
            dps[i][j] = dps[i-1][j-1] + s[i-1]
        else:
            if len(dps[i-1][j]) > len(dps[i][j-1]):
                dps[i][j] = dps[i-1][j]
            else:
                dps[i][j] = dps[i][j-1]

print(dps[lens-1][lent-1])

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
lens = len(s)+1
lent = len(t)+1
dp = [0]*lens
for i in range(lens):
    dp[i] = [0]*lent
dps = [""]*lens
for i in range(lens):
    dps[i] = [""]*lent

for i in range(1,lens):
    for j in range(1,lent):
        if s[i-1] == t[j-1]:
            dp[i][j] = dp[i-1][j-1]+1
            dps[i][j] = dps[i-1][j-1] + s[i-1]
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])
            if len(dps[i-1][j]) > len(dps[i][j-1]):
                dps[i][j] = dps[i-1][j]
            else:
                dps[i][j] = dps[i][j-1]

print(dps[lens-1][lent-1])

Submission status: Time Limit Exceeded

Solution code:
s,t=input(),input()
m,n=len(s),len(t)
l=[[0 for i in range(n+1)] for j in range(m+1)]
for i in range(1,m+1):
    for j in range(1,n+1):
        if s[i-1]==t[j-1]:
            l[i][j]=l[i-1][j-1]+1
        else:
            l[i][j]=max(l[i-1][j],l[i][j-1])
pos=l[m][n]
i,j,lcs=m,n,['']*(pos+1)
while i>0 and j>0:
    if s[i-1] == t[j-1]:
        lcs[pos-1]=s[i-1]
        i,j,pos=i-1,j-1,pos-1
    elif l[i-1][j]>l[i][j-1]:
        i-=1
    else:
        j-=1
print(''.join(lcs))

Submission status: Time Limit Exceeded

Solution code:
def main():
    s = input()
    t = input()

    n = len(s)
    l = len(t)
    dp = [['']*(l+1) for _ in range(n+1)]
    for i in range(0, n):
        for j in range(l):
            if s[i]==t[j]:
                dp[i+1][j+1]=dp[i][j]+s[i]
            else:
                if(len(dp[i+1][j])>len(dp[i][j+1])):dp[i+1][j+1]=dp[i+1][j]
                else:dp[i+1][j+1]=dp[i][j+1]
    print(dp[n][l])
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()

dp = [['']*(len(t)+1)]*(len(s)+1)

for i in range(0, len(s)):
    for j in range(0, len(t)):
        if s[i] == t[j]:
            dp[i+1][j+1] += s[i]
        else:
            if len(dp[i+1][j]) >= len(dp[i][j+1]):
                dp[i+1][j+1] = dp[i+1][j]
            else:
                dp[i+1][j+1] = dp[i][j+1]

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

Submission status: Time Limit Exceeded

Solution code:
def test(s):
  list_s = []
  for i in range(2 ** len(s)):
    list_test = []
    for j in range(len(s)):
      if(i >> j) & 1 == 1:
        list_test.append(s[j])

    list_s.append(list_test)

  return list_s

def main():
  s = list(input())
  t = list(input())

  list_s = test(s)
  list_t = test(t)

  lcs = list(map(list, set(map(tuple, list_s)) & set(map(tuple, list_t))))
  lcs = list(lcs)
  
  max = 0
  num = ['']
  for i in lcs:
    if(len(i) > max):
      max = len(i)
      num.append(i)

  print(''.join(num[-1]))

if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
dp = ['']*(len(t)+1)
for i, ss in enumerate(s):
    newdp = dp[:]
    for j, tt in enumerate(t):
        if ss==tt:
            newdp[j+1] = dp[j] + ss
        else:
            if len(newdp[j]) > len(dp[j+1]):
                newdp[j+1] = newdp[j]
            else:
                newdp[j+1] = dp[j+1]
    dp = newdp

print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
dp = ['']*(len(t)+1)
for i in range(len(s)):
    newdp = dp[:]
    for j in range(len(t)):
        if s[i]==t[j]:
            newdp[j+1] = dp[j] + s[i]
        else:
            if len(newdp[j]) > len(dp[j+1]):
                newdp[j+1] = newdp[j]
            else:
                newdp[j+1] = dp[j+1]
    dp = newdp

print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
dp = [['']*(len(t)+1) for _ in range(len(s)+1)]
for i in range(len(s)):
    for j in range(len(t)):
        if s[i]==t[j]:
            dp[i+1][j+1] = dp[i][j] + s[i]
        else:
            if len(dp[i+1][j]) > len(dp[i][j+1]):
                dp[i+1][j+1] = dp[i+1][j]
            else:
                dp[i+1][j+1] = dp[i][j+1]

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

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
N = len(s)
M = len(t)
dp = [list([0] * (M + 1)) for _ in range(N + 1)]
prev = [[[-1, -1]] * (M + 1) for _ in range(N + 1)]
#print(prev)
for i in range(N):
    for j in range(M):
        if dp[i + 1][j] > dp[i][j + 1]:
            dp[i + 1][j + 1] = dp[i + 1][j];
            prev[i + 1][j + 1] = [i + 1, j]
        else:
            dp[i + 1][j + 1] = dp[i][j + 1];
            prev[i + 1][j + 1] = [i, j + 1]

        if s[i] == t[j] and dp[i][j] + 1 > dp[i + 1][j + 1]:
            dp[i + 1][j + 1] = dp[i][j] + 1
            prev[i + 1][j + 1] = [i, j]
# print(dp[N][M])
x, y = N, M
ans = ''
while True:
    x0, y0 = prev[x][y]
    if x0 == -1 and y0 == -1:
        break
    if x0 + 1 == x and y0 + 1 == y:
        ans = s[x0] + ans
    x, y = x0, y0
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s=raw_input().strip()
t=raw_input().strip()
n=len(s)
m=len(t)
z=[[0]*(m+1) for _ in xrange(n+1)]
for i in xrange(n):
    for j in xrange(m):
        if s[i]==t[j]:
            z[i+1][j+1]=z[i][j]+1
        else:
            z[i+1][j+1]=max(z[i+1][j],z[i][j+1])
i=n-1
j=m-1
a=[]
while i>=0 and j>=0:
    if s[i]==t[j]:
        a.append(s[i])
        i-=1
        j-=1
    elif z[i][j+1]>z[i+1][j]:
        i-=1
    else:
        j-=1
print ''.join(a[::-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 # 998244353
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    S = input()
    T = input()
    m = len(S)
    n = len(T)
    dp = [[-INF] * (n + 1) for _ in range(m + 1)]
    dp[0][0] = 0
    prev = [[None] * (n + 1) for _ in range(m + 1)]
    prev[0][0] = (-1, -1, '')

    for i in range(m):
        dp[i + 1][0] = 0
        prev[i + 1][0] = (i, 0, '')
    for j in range(n):
        dp[0][j + 1] = 0
        prev[0][j + 1] = (0, j, '')

    for i in range(m):
        for j in range(n):
            if dp[i + 1][j + 1] < dp[i][j + 1]:
                dp[i + 1][j + 1] = dp[i][j + 1]
                prev[i + 1][j + 1] = (i, j + 1, '')
            if dp[i + 1][j + 1] < dp[i + 1][j]:
                dp[i + 1][j + 1] = dp[i + 1][j]
                prev[i + 1][j + 1] = (i + 1, j , '')
            if S[i] == T[j] and dp[i + 1][j + 1] < dp[i][j] + 1:
                dp[i + 1][j + 1] = dp[i][j] + 1
                prev[i + 1][j + 1] = (i, j, S[i])

    i, j = m, n
    res = []
    while (i, j) != (0, 0):
        i, j, c = prev[i][j]
        res.append(c)

    print(''.join(res[::-1]))
resolve()

Submission status: Time Limit Exceeded

Solution code:
import bisect
import collections
import sys

sys.setrecursionlimit(10 ** 8)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

S = readline().rstrip()
T = readline().rstrip()
if len(S) < len(T):
    S, T = T, S


def pretty(ss):
    buf = []
    while ss is not None:
        s, ss = ss
        buf.append(s)
    buf.reverse()
    return "".join(buf)


def solve():
    index = collections.defaultdict(list)
    for i, sc in enumerate(S):
        index[sc].append(i)
    dp = [None] * len(T)
    for i, tc in enumerate(T):
        if tc not in index:
            continue
        dn = list(dp)
        ii = index[tc]
        if dn[0] is None or dn[0][0] > ii[0]:
            dn[0] = (ii[0], [chr(tc), None])
        for j in range(1, len(T)):
            if dp[j - 1] is None:
                break
            k = bisect.bisect_right(ii, dp[j - 1][0])
            if k < len(ii) and (dn[j] is None or dn[j][0] > ii[k]):
                dn[j] = (ii[k], [chr(tc), dp[j - 1][1]])
        dp = dn
    for i in range(len(T) - 1, -1, -1):
        if dp[i] is not None:
            return pretty(dp[i][1])
    return ""


if __name__ == "__main__":
    print(solve())

Submission status: Time Limit Exceeded

Solution code:
import bisect
import collections
import sys

sys.setrecursionlimit(10 ** 8)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

S = readline().rstrip()
T = readline().rstrip()
if len(S) < len(T):
    S, T = T, S


def solve():
    index = collections.defaultdict(list)
    for i, sc in enumerate(S):
        index[sc].append(i)
    dp = [None] * len(T)
    for i, tc in enumerate(T):
        if tc not in index:
            continue
        dn = list(dp)
        ii = index[tc]
        if dn[0] is None or dn[0][0] > ii[0]:
            dn[0] = (ii[0], chr(tc))
        for j in range(1, len(T)):
            if dp[j - 1] is None:
                break
            k = bisect.bisect_right(ii, dp[j - 1][0])
            if k < len(ii) and (dn[j] is None or dn[j][0] > ii[k]):
                dn[j] = (ii[k], dp[j - 1][1] + chr(tc))
        dp = dn
    for i in range(len(T) - 1, -1, -1):
        if dp[i] is not None:
            return dp[i][1]
    return ""


if __name__ == "__main__":
    print(solve())

Submission status: Time Limit Exceeded

Solution code:
s,t=input(),input()
m,n=len(s),len(t)
c=[[0]*(n+1) for _ in range(m+1)]
fro=[['']*(n+1) for _ in range(m+1)]
for i in range(1,m+1):
    for j in range(1,n+1):
        if s[i-1]==t[j-1]:
            c[i][j]=c[i-1][j-1]+1
            fro[i][j]='upper_left'
        elif c[i-1][j]>=c[i][j-1]:
            c[i][j]=c[i-1][j]
            fro[i][j]='above'
        else:
            c[i][j]=c[i][j-1]
            fro[i][j]='left'
x=''
a,b=m,n
while a>0 and b>0:
    if fro[a][b]=='upper_left':
        x+=s[a-1]
        a-=1;b-=1
    elif fro[a][b]=='above':
        a-=1
    else:
        b-=1
print(x[::-1])

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
len_s = len(s)
len_t = len(t)

# dp[i][j] = sのi-1文字目,tのj-1文字目まででの最長共通部分列の長さ
dp = [[0]*(len_t+1) for i in range(len_s+1)]
# 遷移記録用（0,1が両方-1ならその文字を追加する）
prevs = [[0]*(len_t+1) for i in range(len_s+1)]
prevt = [[0]*(len_t+1) for i in range(len_s+1)]
for i in range(len_s+1) :
    for j in range(len_t+1) :
        # どちらかが空文字列の場合
        if i == 0 or j == 0 :
            dp[i][j] = 0
            continue
        # i-1文字目とj-1文字目が一致する場合
        if s[i-1] == t[j-1] :
            dp[i][j] = dp[i-1][j-1] + 1
            prevs[i][j] = -1
            prevt[i][j] = -1
        # 一致しない場合
        else : 
            if dp[i-1][j] >= dp[i][j-1] :
                if dp[i-1][j] > dp[i][j] :
                    dp[i][j] = dp[i-1][j]
                    prevs[i][j] = -1
            else :
                if dp[i][j-1] > dp[i][j] :
                    dp[i][j] = dp[i][j-1]
                    prevt[i][j] = -1

ans = 0
si = len_s
ti = len_t
ans = ['' for i in range(dp[len_s][len_t])]
index = dp[len_s][len_t] - 1
# 遷移をたどっていく
for i in range(10**18) :
    if prevs[si][ti] == -1 and prevt[si][ti] == -1 :
        ans[index] = s[si-1]
        index -= 1
    st = si ; tt = ti
    si += prevs[st][tt] ; ti += prevt[st][tt]
    if si == st and ti == tt :
        break

print(*ans, sep='')

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
len_s = len(s)
len_t = len(t)

# dp[i][j] = sのi-1文字目,tのj-1文字目まででの最長共通部分列の長さ
dp = [[-1]*(len_t+1) for i in range(len_s+1)]
# 遷移記録用（0,1が両方-1ならその文字を追加する）
prev = [[[0]*2 for j in range((len_t+1))] for i in range(len_s+1)]
for i in range(len_s+1) :
    for j in range(len_t+1) :
        # どちらかが空文字列の場合
        if i == 0 or j == 0 :
            dp[i][j] = 0
            continue
        # i-1文字目とj-1文字目が一致する場合
        if s[i-1] == t[j-1] :
            dp[i][j] = dp[i-1][j-1] + 1
            prev[i][j][0] = -1
            prev[i][j][1] = -1
        # 一致しない場合
        else : 
            if dp[i-1][j] >= dp[i][j-1] :
                if dp[i-1][j] > dp[i][j] :
                    dp[i][j] = dp[i-1][j]
                    prev[i][j][0] = -1
            else :
                if dp[i][j-1] > dp[i][j] :
                    dp[i][j] = dp[i][j-1]
                    prev[i][j][1] = -1

ans = 0
si = len_s
ti = len_t
ans = ['' for i in range(dp[len_s][len_t])]
index = dp[len_s][len_t] - 1
# 遷移をたどっていく
for i in range(10**18) :
    if prev[si][ti][0] == -1 and prev[si][ti][1] == -1 :
        ans[index] = s[si-1]
        index -= 1
    st = si ; tt = ti
    si += prev[st][tt][0] ; ti += prev[st][tt][1]
    if si == st and ti == tt :
        break

print(*ans, sep='')

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()

#dp[i+1][j+1]:Sのi文字目までとTのj文字目まででのLCSの長さ

dp = [[0 for j in range(len(t)+1)] for i in range(len(s)+1)]

for i in range(len(s)):
    for j in range(len(t)):
        if s[i] == t[j]:
            dp[i+1][j+1] = max(dp[i][j]+1, dp[i+1][j], dp[i][j+1])
        else:
            dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])

res = ""
i = len(s)
j = len(t)

while i > 0 and j > 0:
    if dp[i][j] == dp[i-1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j-1]:
        j -= 1
    else:
        res = s[i-1] + res
        i -= 1
        j -= 1

print(res)

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()

#dp[i+1][j+1]:Sのi文字目までとTのj文字目まででのLCSの長さ

dp = [["" for j in range(len(t)+1)] for i in range(len(s)+1)]

for i in range(len(s)):
    for j in range(len(t)):
        if s[i] == t[j]:
            dp[i+1][j+1] = max(dp[i][j]+s[i], dp[i+1][j], dp[i][j+1], key=len)
        else:
            dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1], key=len)

print(dp[len(s)][len(t)])

Submission status: Time Limit Exceeded

Solution code:
import sys
from io import StringIO
import unittest

def resolve():
    s = list(input())
    t = list(input())

    dp = [[0 for _ in range(len(t) + 1)] for __ in range(len(s) + 1)]

    # 長さを求める
    for i in range(len(s)):
        for j in range(len(t)):
            if s[i] == t[j]:
                dp[i + 1][j + 1] = max(dp[i][j] + 1, dp[i + 1][j], dp[i][j + 1])
            else:
                dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1])

    ans = ''
    i += 1
    j += 1

    # 復元する
    while i >= 0 and j >= 0:
        if dp[i][j] == dp[i - 1][j - 1]:
            i -= 1
            j -= 1
        elif dp[i][j] == dp[i - 1][j]:
            i -= 1
        elif dp[i][j] == dp[i][j - 1]:
            j -= 1
        else:
            ans = s[i - 1] + ans
            i -= 1
            j -= 1

    print(ans)

class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """axyb
abyxb"""
        output = """axb"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """aa
xayaz"""
        output = """aa"""
        self.assertIO(input, output)
    def test_入力例_3(self):
        input = """a
z"""
        output = """"""
        self.assertIO(input, output)
    def test_入力例_4(self):
        input = """abracadabra
avadakedavra"""
        output = """aaadara"""
        self.assertIO(input, output)

if __name__ == "__main__":
    # unittest.main()
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
from io import StringIO
import unittest

def resolve():
    s = list(input())
    t = list(input())

    dp = [['' for _ in range(len(t) + 1)] for __ in range(len(s) + 1)]

    for i in range(len(s)):
        for j in range(len(t)):
            a = len(dp[i][j]) + 1
            b = len(dp[i + 1][j])
            c = len(dp[i][j + 1])

            if s[i] == t[j]:
                max_abc = max(a, b, c)
                if a == max_abc:
                    dp[i + 1][j + 1] = dp[i][j] + s[i]
                elif b == max_abc:
                    dp[i + 1][j + 1] = dp[i + 1][j]
                elif c == max_abc:
                    dp[i + 1][j + 1] = dp[i][j + 1]
            else:
                max_bc = max(b, c)
                if b == max_bc:
                    dp[i + 1][j + 1] = dp[i + 1][j]
                else:
                    dp[i + 1][j + 1] = dp[i][j + 1]

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

class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """axyb
abyxb"""
        output = """axb"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """aa
xayaz"""
        output = """aa"""
        self.assertIO(input, output)
    def test_入力例_3(self):
        input = """a
z"""
        output = """"""
        self.assertIO(input, output)
    def test_入力例_4(self):
        input = """abracadabra
avadakedavra"""
        output = """aaadara"""
        self.assertIO(input, output)

if __name__ == "__main__":
    # unittest.main()
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
s=input()
t=input()
ns,nt=len(s),len(t)
dp=np.zeros((ns+1,nt+1),np.int64)
# dp=[[0]*(ns+1) for _ in range(nt+1)]
# dp[i+1][j+1]:sのi文字目まで、tのj文字目まで考えた時の最長
for i in range(ns):
      for j in range(nt):
            if s[i]==t[j]:
                  dp[i+1][j+1]=dp[i][j]+1
            dp[i+1][j+1]=max(dp[i+1][j+1],dp[i+1][j],dp[i][j+1])
lg=dp[-1][-1]
ans=[]
#print(dp)
i,j=ns,nt
while i>0 and j>0:
      if dp[i][j]==dp[i][j-1]:
            j-=1
      elif dp[i][j]==dp[i-1][j]:
            i-=1
      else:
            i-=1
            j-=1
            ans.append(s[i])
s=''
for _ in range(lg):
      s+=ans.pop()
print(s)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# vim: set fileencoding=utf-8

# pylint: disable=unused-import, invalid-name, missing-docstring, bad-continuation


"""Module docstring
"""

import sys


def solve(s, t):
    v = [0] * (len(s) + 1)
    dp = [v]
    for _, ti in enumerate(t, 1):
        u, v = v, v.copy()
        dp.append(v)
        ll, ul = 0, 0
        for j, sj in enumerate(s, 1):
            uj = u[j]
            if sj == ti:
                v[j] = 1 + ul
                ll = 1 + ul
            else:
                if ll > uj:
                    v[j] = ll
                else:
                    ll = uj
            ul = uj
    i = len(t)
    j = len(s)
    k = dp[i][j]
    selected = []
    while k > 0:
        if dp[i - 1][j] == k:
            i -= 1
        elif dp[i][j - 1] == k:
            j -= 1
        else:
            selected.append(t[i - 1])
            k -= 1
            i -= 1
            j -= 1
    return "".join(selected[::-1])


def solve_errichto(s, t):
    # dp the max total length so far
    dp = [[(0, (0, 0))] * (len(t) + 1) for _ in range(len(s) + 1)]
    for i, si in enumerate(s):
        for j, tj in enumerate(t):
            if si == tj:
                if dp[i + 1][j + 1][0] < dp[i][j][0] + 1:
                    dp[i + 1][j + 1] = (dp[i][j][0] + 1, (i, j))
            if dp[i + 1][j][0] < dp[i][j][0]:
                dp[i + 1][j] = (dp[i][j][0], (i, j))
            if dp[i][j + 1][0] < dp[i][j][0]:
                dp[i][j + 1] = (dp[i][j][0], (i, j))
    best = (0, (0, 0))
    for i, row in enumerate(dp):
        for j, v in enumerate(row):
            if v[0] > best[0]:
                best = (v[0], (i, j))
    result = []
    i, j = best[1]
    while i > 0 and j > 0:
        prev = dp[i][j][1]
        if prev == (i - 1, j - 1):
            # assert s[i - 1] == t[j - 1]
            result.append(s[i - 1])
        i, j = prev
    result.reverse()
    return "".join(result)


def do_job():
    "Do the work"
    s = input()
    t = input()
    result = solve_errichto(s, t)
    print(result)


def print_output(testcase, result) -> None:
    "Formats and print result"
    if result is None:
        result = "IMPOSSIBLE"
    print("Case #{}: {}".format(testcase + 1, result))


def main(argv=None):
    "Program wrapper."
    if argv is None:
        argv = sys.argv[1:]
    do_job()
    return 0


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    sys.exit(main())