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:
import sys
readline = sys.stdin.readline

S = readline().rstrip()
T = readline().rstrip()

# dp[i][j] = Sをi文字目、Tをj文字目まで進めたときの最長
# S[i] == S[j]のとき
# dp[i][j] = dp[i - 1][j - 1] + 1
# S[i] != S[j]のとき
# dp[i][j] = max(dp[i - 1][j],dp[i][j - 1])

# その際、自分がどこから来たか？を記録する
# dp[i - 1][j] > dp[i][j - 1]であれば
# route[i][j] = (i,j)を記録

dp = [[0] * (len(T) + 1) for i in range(len(S) + 1)]
route = [[(0,0)] * (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] = dp[i][j] + 1
      route[i + 1][j + 1] = (i,j)
    else:
      if dp[i][j + 1] > dp[i + 1][j]:
        dp[i + 1][j + 1] = dp[i][j + 1]
        route[i + 1][j + 1] = (i,j + 1)
      else:
        dp[i + 1][j + 1] = dp[i + 1][j]
        route[i + 1][j + 1] = (i + 1,j)

# routeのとびさきの文字を追加していく
x,y = len(S),len(T)
ans = ""
while x != 0 and y != 0:
  if S[x - 1] == T[y - 1]:
    ans += S[x - 1]
  x,y = route[x][y]

print(ans[::-1])

Submission status: Time Limit Exceeded

Solution code:
s=input()
t=input()
res=[]
for i in range(0,len(s)+1):
    r=[]
    for j in range(0,len(t)+1):
        r.append(0)
    res.append(r)
    
for i in range(1,len(s)+1):
    for j in range(1,len(t)+1):
        if s[i-1]==t[j-1]:
            res[i][j]=res[i-1][j-1]+1
        else:
            res[i][j]=max(res[i-1][j-1], res[i-1][j], res[i][j-1])
            
#print(res)
LCS=[]
S_LCS=''
for i in range(0,min(len(s),len(t))+1):
    LCS.append('')
i = len(s)
j = len(t)
index=min(len(s),len(t))+1
while i > 0 and j > 0: 
    if s[i-1] == t[j-1]:
        LCS[index-1] = s[i-1]  
        i-=1
        j-=1 
        index-=1       

    elif res[i-1][j] > res[i][j-1]: 
        i-=1 
    else:
        j-=1 
        
for i in range(0,len(LCS)):
    S_LCS+=LCS[i]

print(S_LCS)

Submission status: Time Limit Exceeded

Solution code:
s=input()
t=input()
n=len(s)
m=len(t)

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

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

    else:
      dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j])

#print(dp[n][m])

ans=''
while n>=0 and m>=0:
  if dp[n][m]==dp[n-1][m]:
    n-=1

  elif dp[n][m]==dp[n][m-1]:
    m-=1

  else:
    n-=1
    m-=1
    ans+=s[n]

print(ans[::-1])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

####################################################
# LCS(longest common sequence)
# 部分列で最長の共通のもの
####################################################

# dp[i+1][j+1]:= s の i 文字目までと t の j 文字目まででの LCS の長さ

def main():
    S = input()
    T = input()
    ls = len(S)
    lt = len(T)

    dp = [[0]*(lt+1) for _ in range(ls+1)]
    for i in range(ls):
        for j in range(lt):
            dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1], dp[i][j]+ (S[i]==T[j]))
#    print(dp)
#    print(dp[ls][lt])

    # 復元
    res = ''
    i, j = ls, lt
    while (i > 0 and j > 0):
        # (i-1, j) -> (i, j) と更新されていた場合
        if dp[i][j] == dp[i-1][j]:
            i-=1   # DP の遷移を遡る
        # (i, j-1) -> (i, j) と更新されていた場合
        elif dp[i][j] == dp[i][j-1]:
            j-=1   # DP の遷移を遡る
        # (i-1, j-1) -> (i, j) と更新されていた場合
        else:
            res = S[i-1] + res
            # このとき s[i-1] == t[j-1] なので、t[j-1] + res でも OK
            i-=1
            j-=1   # DP の遷移を遡る
    print(res)

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)]
ans=[[[-1,0,0] for _ in range(len(t)+1)] for _ in range(len(s)+1)]

for i,c in enumerate(s):
    for j,d in enumerate(t):
        if c==d:
            dp[i+1][j+1]=dp[i][j]+1
            ans[i+1][j+1]=[i,i,j]
        else:
            dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j])
            ans[i+1][j+1]=ans[i][j+1] if dp[i+1][j+1]==dp[i][j+1] else ans[i+1][j]

i=len(s)
j=len(t)
ss=['']*dp[i][j]
l=dp[i][j]-1
while i>0 and j>0:
    x,i,j=ans[i][j]
    if x>-1:
        ss[l]=s[x]
        l-=1

print(''.join(ss))

Submission status: Time Limit Exceeded

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

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

for i,c in enumerate(s):
    for j,d in enumerate(t):
        if c==d:
            dp[i+1][j+1]=dp[i][j]+1
            ans[i+1][j+1]=[i,i,j]
        else:
            dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j])
            ans[i+1][j+1]=ans[i][j+1] if dp[i+1][j+1]==dp[i][j+1] else ans[i+1][j]

i=len(s)
j=len(t)
ss=[]
while i>0 and j>0:
    x,i,j=ans[i][j]
    if x>-1:
        ss.append(s[x])

print(''.join(ss[::-1]))

Submission status: Time Limit Exceeded

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

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

for i,c in enumerate(s):
    for j,d in enumerate(t):
        if c==d:
            dp[i+1][j+1]=dp[i][j]+1
            ans[i+1][j+1]=[c,i,j]
        else:
            dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j])
            ans[i+1][j+1]=ans[i][j+1] if dp[i+1][j+1]==dp[i][j+1] else ans[i+1][j]

i=len(s)
j=len(t)
s=[]
while i>0 and j>0:
    c,i,j=ans[i][j]
    s.append(c)

print(''.join(s[::-1]))

Submission status: Time Limit Exceeded

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

fl_i=0
fl_j=0

dp=[['']*len(t) for _ in range(len(s))]

for i in range(len(s)):
    for j in range(len(t)):
        if i==0 or j==0:
            if s[i]==t[j]:
                dp[i][j]=s[i]
                fl_i=1 if i==0 else 0
                fl_j=1 if j==0 else 0
            elif fl_i==1:
                dp[i][j]=dp[i][j-1]
            elif fl_j==1:
                dp[i][j]=dp[i-1][j]
        else:
            if s[i]==t[j]:
                dp[i][j]=dp[i-1][j-1]+s[i]
            elif len(dp[i][j-1])>len(dp[i-1][j]):
                dp[i][j]=dp[i][j-1]
            else:
                dp[i][j]=dp[i-1][j]

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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

####################################################
# LCS(longest common sequence)
# 部分列で最長の共通のもの
####################################################

# dp[i+1][j+1]:= s の i 文字目までと t の j 文字目まででの LCS の長さ

def main():
    S = input()
    T = input()
    ls = len(S)
    lt = len(T)

    dp = [[0]*(lt+1) for _ in range(ls+1)]
    for i in range(ls):
        for j in range(lt):
            if S[i]==T[j]:
                dp[i+1][j+1] = max(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+1][j+1] = max(dp[i+1][j+1], dp[i][j+1])
#    print(dp)
#    print(dp[ls][lt])

    # 復元
    res = ''
    i, j = ls, lt
    while (i > 0 and j > 0):
        # (i-1, j) -> (i, j) と更新されていた場合
        if dp[i][j] == dp[i-1][j]:
            i-=1   # DP の遷移を遡る

        # (i, j-1) -> (i, j) と更新されていた場合
        elif dp[i][j] == dp[i][j-1]:
            j-=1   # DP の遷移を遡る

        # (i-1, j-1) -> (i, j) と更新されていた場合
        else:
            res = S[i-1] + res
            # このとき s[i-1] == t[j-1] なので、t[j-1] + res でも OK
            i-=1
            j-=1   # DP の遷移を遡る
    print(res)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

a=len(s)
b=len(t)

dp=[ [0 for _ in range(a+1)] for _ in range(b+1)]

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

#print(dp)

ans=""
x=a
y=b
while dp[y][x]!=0:
    if dp[y][x]==dp[y-1][x]:
        y -=1
    elif dp[y][x]==dp[y][x-1]:
        x -=1
    else:
        ans += s[x-1]
        y -=1
        x -=1
print(ans[::-1])

Submission status: Time Limit Exceeded

Solution code:
s=input()
t=input()
n=len(t)
m=len(s)
dp=[['']*(n+1) for i in range(m+1)]
lendp=[[0]*(n+1) for i in range(m+1)]
for i in range(m):
  for j in range(n):
    if s[i]==t[j]:
      dp[i+1][j+1]=dp[i][j]+s[i]
      lendp[i+1][j+1]=lendp[i][j]+1

    else:
      if max(lendp[i+1][j],lendp[i][j+1])==lendp[i][j+1]:
        dp[i+1][j+1]=dp[i][j+1]
        lendp[i+1][j+1]=lendp[i][j+1]

      else:
        dp[i+1][j+1]=dp[i+1][j]
        lendp[i+1][j+1]=lendp[i+1][j]

        
print(dp[m][n])
#print(dp)

Submission status: Time Limit Exceeded

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

    else:
      if len(dp[i][j+1])>=len(dp[i+1][j]):
        dp[i+1][j+1]=dp[i][j+1]

      else:
        dp[i+1][j+1]=dp[i+1][j]

        
print(dp[m][n])
#print(dp)

Submission status: Time Limit Exceeded

Solution code:
def solve(s, t):
    n = len(s)
    m = len(t)
    dp = [[0] * (m+1) for i in range(n+1)]
    for i in range(1,n+1):
        for j in range(1,m+1):
            if s[i-1] == t[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i][j-1], dp[i-1][j])
    i, j = n, m
    ans = ""
    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 = s[i] + ans
    return ans

s = input()
t = input()
print(solve(s, t))

Submission status: Time Limit Exceeded

Solution code:
S = input()
T = input()
lenS = len(S)
lenT = len(T)
dp = [[0]*(lenT+1) for _ in range(lenS+1)]
for i in range(1,lenS+1):
    for j in range(1,lenT+1):
        if S[i-1]==T[j-1]:
            dp[i][j] = dp[i-1][j-1]+1
        else:
            dp[i][j] = max(dp[i-1][j],dp[i][j-1])
ans = []
while lenS!=0 and lenT!=0:
    if dp[lenS][lenT]==dp[lenS-1][lenT]:
        lenS-=1
    elif dp[lenS][lenT]==dp[lenS][lenT-1]:
        lenT-=1
    else:
        ans.append(S[lenS-1])
        lenS-=1
        lenT-=1
ans = ans[::-1]
print("".join(ans))

Submission status: Time Limit Exceeded

Solution code:

s = input()
t = input()

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

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

kotae = []

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
        kotae.append(s[i])

kotae.reverse()
kotae = "".join(kotae)
print(kotae)

Submission status: Time Limit Exceeded

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

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

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

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]="".join([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[len(s)][len(t)])

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

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
s = input()
t = input()

dp = np.zeros((len(t)+1, len(s)+1))
for i in range(1, len(t)+1):
    ti = t[i-1]
    dp[i] = dp[i-1]
    for j in range(1, len(s)+1):
        if ti == s[j-1]:
            dp[i][j] = dp[i][j-1] + 1
        else:
            if dp[i][j-1] >= dp[i][j]:
                dp[i][j] = dp[i][j-1]
ans = ''
sl = len(s)
tl = len(t)
while sl > 0 and tl > 0:
    if s[sl-1] == t[tl-1]:
        sl -= 1
        tl -= 1
        ans = s[sl] + ans
        continue

    if dp[tl][sl] == dp[tl][sl-1]:
        sl -= 1
    elif dp[tl][sl] == dp[tl-1][sl]:
        tl -= 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def solve(s1,s2):
    rows=len(s1)
    cols=len(s2)
    dp=[[0]*(cols+1) for i in range(rows+1)]
    for i in range(1,rows+1):
        for j in range(1,cols+1):
            if s1[i-1]==s2[j-1]:
                dp[i][j]=dp[i-1][j-1]+1
            else:
                dp[i][j]=max(dp[i-1][j],dp[i][j-1])
                
    max_len=dp[rows][cols]
    result=[""]*(max_len+1)
    result[max_len]=""
    i=rows
    j=cols
    while i>0 and j>0:
        if s1[i-1]==s2[j-1]:
            result[max_len-1]=s1[i-1]
            max_len -=1
            i -=1
            j -=1
        elif dp[i-1][j]>dp[i][j-1]:
            i -=1
        else:
            j -=1
    return "".join(result)
            
                
#     if i==n or j==m:
#         return result
#     if s1[i]==s2[j]:
#         result +=s1[i]
#         return result+solve(s1,s2,n,m,i+1,j+1,result)
#     else:
#         left=solve(s1,s2,n,m,i+1,j,result)
#         right=solve(s1,s2,n,m,i,j+1,result)
#         if left:
#             result
        
        ##return max(solve(s1,s2,n,m,i+1,j,result),solve(s1,s2,n,m,i,j+1,result))
s1=input()
s2=input()
n=len(s1)
m=len(s2)
result=""
print(solve(s1,s2))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)

s = input()
t = input()

#dp[i][j] : sをi番目、tをj番目まで読んだ時の共通部分列の長さの最大

n = len(s)
m = len(t)

dp = [["" for _ in range(m)] for _ in range(n)]

def lcs(i,j):
    if i < 0 or j < 0:
        return ""
    if s[i] == t[j]:
        dp[i][j] = lcs(i-1, j-1) + s[i]
        return dp[i][j]
    else:
        c1 = lcs(i-1,j)
        c2 = lcs(i,j-1)
        if len(c1) > len(c2):
            dp[i][j] = c1
            return c1
        else:
            dp[i][j] = c2
            return c2

lcs(n-1, m-1)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)

s = input()
t = input()

#dp[i][j] : sをi番目、tをj番目まで読んだ時の共通部分列の長さの最大

n = len(s)
m = len(t)

dp = [["" for _ in range(m)] for _ in range(n)]

def lcs(i,j):
    if i <= -1 or j <= -1:
        return ""
    elif s[i] == t[j]:
        dp[i][j] = lcs(i-1, j-1) + s[i]
        return dp[i][j]
    else:
        c1 = lcs(i-1,j)
        c2 = lcs(i,j-1)
        if len(c1) > len(c2):
            dp[i][j] = c1
        else:
            dp[i][j] = c2
        return dp[i][j]

lcs(n-1, m-1)

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

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7
#from decimal import *
		
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][j+1], dp[i+1][j])


y = len(s)
x = len(t)
ans = ""
while 1:
	#print(y, x, ans)
	if x*y == 0:
		break
	elif s[y-1] == t[x-1]:
		ans += s[y-1]
		x -= 1
		y -= 1
	else:
		if dp[y][x] == dp[y-1][x]:
			y -= 1
		elif dp[y][x] == dp[y][x-1]:
			x -= 1

lcs  = dp[len(s)][len(t)]

q = deque([(len(s), len(t))])
common = [set() for _ in range(lcs)]

while q:
	#print(q)
	y, x =q.popleft()
	if x*y != 0 :
		if s[y-1] == t[x-1]:
			common[dp[y][x]-1].add(t[x-1])
			y -= 1
			x -= 1
			q.append((y, x))
		else:
			if dp[y][x] == dp[y-1][x]:
				q.append((y-1, x))

			if dp[y][x] == dp[y][x-1]:
				q.append((y, x-1))

print(*[list(common[i])[0] for i in range(lcs)], sep="")

Submission status: Time Limit Exceeded

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

dp = [0] * (len(s)+1)
dps = [[] for _ in range(len(s)+1)]
for i in range(1, len(t)+1):
    ti = t[i-1]
    for j in range(1, len(s)+1):
        sj = s[j-1]
        if ti == sj:
            dp[j] = dp[j-1] + 1
            temp = dps[j-1][:]
            temp.append(ti)
            dps[j] = temp
        else:
            if dp[j-1] >= dp[j]:
                dp[j] = dp[j-1]
                dps[j] = dps[j-1][:]
print(''.join(dps[-1]))

Submission status: Time Limit Exceeded

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

dp = [0] * (len(s)+1)
dps = [[] for _ in range(len(s)+1)]
for i in range(1, len(t)+1):
    ti = t[i-1]
    for j in range(1, len(s)+1):
        sj = s[j-1]
        if ti == sj:
            dp[j] = dp[j-1] + 1
            dps[j] = (dps[j-1] + [ti]).copy()
        else:
            if dp[j-1] >= dp[j]:
                dp[j] = dp[j-1]
                dps[j] = dps[j-1][:]
print(''.join(dps[-1]))

Submission status: Time Limit Exceeded

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

dp = [0] * (len(s)+1)
dps = [''] * (len(s)+1)
for i in range(1, len(t)+1):
    ti = t[i-1]
    for j in range(1, len(s)+1):
        sj = s[j-1]
        if ti == sj:
            dp[j] = dp[j-1] + 1
            dps[j] = dps[j-1] + ti
        else:
            if dp[j-1] >= dp[j]:
                dp[j] = dp[j-1]
                dps[j] = dps[j-1]
print(dps[-1])

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7
#from decimal import *
		
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][j+1], dp[i+1][j])
            
y = len(s)
x = len(t)
ans = ""
while 1:
	#print(y, x, ans)
	if x*y == 0:
		break
	elif s[y-1] == t[x-1]:
		ans += s[y-1]
		x -= 1
		y -= 1
	else:
		if dp[y][x] == dp[y-1][x]:
			y -= 1
		elif dp[y][x] == dp[y][x-1]:
			x -= 1
            
print(ans[::-1])

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7
#from decimal import *
		
s = input()
t = input()

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

common = [[] for _ in range(len(t))]

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
			common[dp[i][j]].append(t[j])
		else:
			dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])

y = len(s)
x = len(t)
ans = ""
while 1:
	#print(y, x, ans)
	if x*y == 0:
		break
	elif s[y-1] == t[x-1]:
		ans += s[y-1]
		x -= 1
		y -= 1
	else:
		if dp[y][x] == dp[y-1][x]:
			y -= 1
		elif dp[y][x] == dp[y][x-1]:
			x -= 1

print(ans[::-1])

Submission status: Time Limit Exceeded

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

s1=input()
s2=input()
n=len(s1)
m=len(s2)
# import numpy as np
dp=[["" for i in range(m+1)]for i in range(n+1)]
for i in range(1,n+1):
    for j in range(1,m+1):
        if s1[i-1]==s2[j-1]:
            dp[i][j]=dp[i-1][j-1]+s1[i-1]
        else:
            a=dp[i-1][j]
            b=dp[i][j-1]
            if len(a)>len(b):
                dp[i][j]=a
            else:
                dp[i][j]=b
# print(np.array(dp))
print(dp[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
s1=input()
s2=input()
n=len(s1)
m=len(s2)
# import numpy as np
dp=[["" for i in range(m+1)]for i in range(n+1)]
for i in range(1,n+1):
    for j in range(1,m+1):
        if s1[i-1]==s2[j-1]:
            dp[i][j]=dp[i-1][j-1]+s1[i-1]
        else:
            a=dp[i-1][j]
            b=dp[i][j-1]
            if len(a)>len(b):
                dp[i][j]=a
            else:
                dp[i][j]=b
# print(np.array(dp))
print(dp[-1][-1])

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]:
            dpp = dp[i][j] + 1
            dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dpp)
        dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j + 1])
        dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i + 1][j])

u = ''
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:
        u = s[i - 1] + u
        i -= 1
        j -= 1

print(u)

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
a = len(list(s))
b = len(list(t))
#dp[i][j] をsをi番目、ｔをj番目までの最長共通長
INF = float('inf')
dp = [[-INF for j in range(b+1)] for i in range(a+1)]
for i in range(a+1):
    dp[i][0] = 0
for j in range(b+1):
    dp[0][j] = 0
for i, x in enumerate(list(s)):
    for j, y in enumerate(list(t)):
        if x == y:
            dp[i+1][j+1] = dp[i][j] + 1
        else:
            dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])
#復元パート
ans = ''
while a > 0 and b >0:

    if dp[a][b] == dp[a-1][b]:
        a -= 1
    elif dp[a][b] == dp[a][b-1]:
        b -= 1
    else:
        ans = list(s)[a-1] + ans
        a -= 1
        b -= 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from  collections import defaultdict

# sys.stdin = open('input.txt', 'r')
# sys.stdout = open('output.txt', 'w')

sys.setrecursionlimit(1000000000)

def solve(test):
	s = input()
	t = input()
	memo = {}
	ans = lcs(s, t, 0, 0, memo)
	print(ans)

def lcs(s, t, i, j, memo):
	if (i, j) in memo:
		return memo[(i, j)]
	elif i == len(s) or j == len(t):
		return ''
	else:
		ans = ''
		if s[i] == t[j]:
			ans = s[i] + lcs(s, t, i + 1, j + 1, memo)
		else:
			s1 = lcs(s, t, i + 1, j, memo)
			s2 = lcs(s, t, i, j + 1, memo)
			if len(s1) >= len(s2):
				ans = s1
			else:
				ans = s2
		memo[(i, j)] = ans
		return ans


if __name__ == "__main__":
	test_cases = 1
	for t in range(1, test_cases + 1):
		solve(t)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from  collections import defaultdict

# sys.stdin = open('input.txt', 'r')
# sys.stdout = open('output.txt', 'w')

sys.setrecursionlimit(1000000)

def solve(test):
	s = input()
	t = input()
	memo = {}
	ans = lcs(s, t, 0, 0, memo)
	print(ans)

def lcs(s, t, i, j, memo):
	if (i, j) in memo:
		return memo[(i, j)]
	elif i == len(s) or j == len(t):
		return ''
	else:
		ans = ''
		if s[i] == t[j]:
			ans = s[i] + lcs(s, t, i + 1, j + 1, memo)
		else:
			s1 = lcs(s, t, i + 1, j, memo)
			s2 = lcs(s, t, i, j + 1, memo)
			if len(s1) >= len(s2):
				ans = s1
			else:
				ans = s2
		memo[(i, j)] = ans
		return ans


if __name__ == "__main__":
	test_cases = 1
	for t in range(1, test_cases + 1):
		solve(t)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from  collections import defaultdict

# sys.stdin = open('input.txt', 'r')
# sys.stdout = open('output.txt', 'w')


def solve(test):
	s = [''] + list(input())
	t = [''] + list(input())
	rec = [[0 for j in range(len(t))] for i in range(len(s))]
	for i in range(1, len(s)):
		for j in range(1, len(t)):
			if s[i] == t[j]:
				rec[i][j] = 1 + rec[i - 1][j - 1]
			else:
				rec[i][j] = max(rec[i - 1][j], rec[i][j - 1])

	ans = []
	i, j = len(s) - 1, len(t) - 1
	while i >= 0 and j >= 0:
		if s[i] == t[j]:
			ans.append(s[i])
			i -= 1
			j -= 1
		elif rec[i - 1][j] > rec[i][j - 1]:
			i -= 1
		else:
			j -= 1

	print(''.join(ans[::-1]))


if __name__ == "__main__":
	test_cases = 1
	for t in range(1, test_cases + 1):
		solve(t)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from  collections import defaultdict

# sys.stdin = open('input.txt', 'r')
# sys.stdout = open('output.txt', 'w')

sys.setrecursionlimit(1000000)

def solve(test):
	s = list(input())
	t = list(input())
	memo = {}
	ans = lcs(s, t, 0, 0, memo)
	print(''.join(ans))

def lcs(s, t, i, j, memo):
	if (i, j) in memo:
		return memo[(i, j)]
	elif i == len(s) or j == len(t):
		return ['']
	else:
		ans = ''
		if s[i] == t[j]:
			ans = [s[i]] + lcs(s, t, i + 1, j + 1, memo)
		else:
			s1 = lcs(s, t, i + 1, j, memo)
			s2 = lcs(s, t, i, j + 1, memo)
			if len(s1) >= len(s2):
				ans = s1
			else:
				ans = s2
		memo[(i, j)] = ans
		return ans


if __name__ == "__main__":
	test_cases = 1
	for t in range(1, test_cases + 1):
		solve(t)

Submission status: Time Limit Exceeded

Solution code:
class Solution(object):
    def LCS(self, text1, text2):
        """
        :type text1: str
        :type text2: str
        :rtype: int
        """
        n, m = len(text1), len(text2)
        dp = [[0]*(m+1) for _ in range(n+1)]
        for i in range(0, n):
            for j in range(0, m):
                if text1[i] == text2[j]: dp[i+1][j+1] = dp[i][j]+1
                else:
                  if dp[i][j+1] > dp[i+1][j]: dp[i+1][j+1] = dp[i][j+1]
                  else: dp[i+1][j+1] = dp[i+1][j]
                    
        ans = ""
        i, j = len(text1), len(text2)
        while i > 0 and j > 0:
            if text1[i - 1] == text2[j - 1]:
                ans += text1[i - 1]
                i -= 1
                j -= 1
                continue
            elif dp[i][j] == dp[i - 1][j]: i -= 1
            else: j -= 1
        ans = ans[::-1]
        return "".join(ans)
        #return dp[n][m]
import sys
#import cython
 
def main():
    read = lambda: sys.stdin.readline().rstrip()
    
    #N: cython.longlong = 0
    s = read()
    t = read()
    ret = Solution().LCS(s, t)
    
 
    print(ret)
 
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
class Solution(object):
    def LCS(self, text1, text2):
        """
        :type text1: str
        :type text2: str
        :rtype: int
        """
        n, m = len(text1), len(text2)
        dp = [[0]*(m+1) for _ in range(n+1)]
        for i in range(0, n):
            for j in range(0, m):
                if text1[i] == text2[j]: dp[i+1][j+1] = dp[i][j]+1
                else: dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])
                    
                    
        ans = ""
        i, j = len(text1), len(text2)
        while i > 0 and j > 0:
            if text1[i - 1] == text2[j - 1]:
                ans += text1[i - 1]
                i -= 1
                j -= 1
                continue
            if dp[i][j] == dp[i - 1][j]: i -= 1
            else: j -= 1
        ans = ans[::-1]
        return "".join(ans)
        #return dp[n][m]
import sys
#import cython
 
def main():
    read = lambda: sys.stdin.readline().rstrip()
    
    #N: cython.longlong = 0
    s = read()
    t = read()
    ret = Solution().LCS(s, t)
    
 
    print(ret)
 
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
class Solution(object):
    def LCS(self, text1, text2):
        """
        :type text1: str
        :type text2: str
        :rtype: int
        """
        n, m = len(text1), len(text2)
        dp = [[0]*(m+1) for _ in range(n+1)]
        for i in range(0, n):
            for j in range(0, m):
                if text1[i] == text2[j]: dp[i+1][j+1] = dp[i][j]+1
                else: dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])
                    
                    
        ans = ""
        i, j = len(text1), len(text2)
        while i > 0 and j > 0:
            if text1[i - 1] == text2[j - 1]:
                ans += text1[i - 1]
                i -= 1
                j -= 1
                continue
            elif dp[i][j] == dp[i - 1][j]: i -= 1
            else: j -= 1
        ans = ans[::-1]
        return "".join(ans)
        #return dp[n][m]
import sys
#import cython

def main():
    read = lambda: sys.stdin.readline().rstrip()
    
    #N: cython.longlong = 0
    s = read()
    t = read()
    ret = Solution().LCS(s, t)
    

    print(ret)
 
if __name__ == "__main__":
    main()