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:
s=input()
t=input()
dp=[["" for i in range(len(t)+1)] for j 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]="{0}{1}".format(dp[i-1][j-1],s[i-1])
        else:
            A=len(dp[i-1][j])
            B=len(dp[i][j-1])
            if A>=B:
                dp[i][j]=dp[i-1][j]
            else:
                dp[i][j]=dp[i][j-1]
print(dp[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict as dd
mod = pow(10, 9) + 7
mod2 = 998244353
inf = int(1e20)
def data(): return sys.stdin.readline().strip()
def out(*var, end="\n"): sys.stdout.write(" ".join(map(str, var))+end)
def l(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]


s, t = data(), data()
n, m = len(s), len(t)
dp = dd(lambda: dd(int))
state = dd(lambda: -1)
for i in range(n):
    for j in range(m):
        if s[i] == t[j]:
            dp[i][j] = dp[i-1][j-1] + 1
            state[(i, j)] = 0
        elif dp[i-1][j] >= dp[i][j-1]:
            dp[i][j] = dp[i-1][j]
            state[(i, j)] = 1
        else:
            dp[i][j] = dp[i][j-1]
            state[(i, j)] = 2
answer = []
i, j = n-1, m-1
while i >= 0 and j >= 0:
    if state[(i, j)] == 0:
        answer.append(s[i])
        i -= 1
        j -= 1
        continue
    if state[(i, j)] == 1:
        i -= 1
        continue
    j -= 1
out(''.join(map(str, answer[::-1])))

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
def main():
    s=tuple(input())
    t=tuple(input())
    n=len(s)
    m=len(t)
    dp=[['' for i in range(m+1)] for j 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]+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][m])
if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
s1 = input()
s2 = input()

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

x = len(s1)
y = len(s2)

s = ""

while x > 0 and y > 0:
    while x > 1 and dp[y][x-1] == dp[y][x]:
        x -= 1
    while y > 1 and dp[y-1][x] == dp[y][x]:
        y -= 1

    if s1[x-1] == s2[y-1] and y > 0:
        s += s2[y-1]

    y -= 1

print(s[::-1])

Submission status: Time Limit Exceeded

Solution code:
s1 = input()
s2 = input()

dp = [[0 for x in range(len(s1))] for y in range(len(s2))]
for y in range(len(s2)):
    for x in range(len(s1)):
        if s2[y] == s1[x]:
            if y == 0:
                dp[y][x] += 1
            else:
                if dp[y-1][x]+1 > dp[y][x]:
                    dp[y][x] = dp[y-1][x]+1

        if x != 0:
            if dp[y][x-1] > dp[y][x]:
                dp[y][x] = dp[y][x-1]
        if y != 0:
            if dp[y-1][x] > dp[y][x]:
                dp[y][x] = dp[y-1][x]

x = len(s1)-1
y = len(s2)-1

s = ""

while x >= 0 and y >= 0:
    while x > 0 and dp[y][x-1] == dp[y][x]:
        x -= 1
    while y > 0 and dp[y-1][x] == dp[y][x]:
        y -= 1

    if s1[x] == s2[y] and y >= 0:
        s += s2[y]
    y -=1

print(s[::-1])

Submission status: Time Limit Exceeded

Solution code:
def main():
    s=input()
    t=input()
    n,m=len(s),len(t)
    dp=[[0]*(m+1)for i in range(n+1)]
    for i in range(n+1):
        for j in range(m+1):
            if i==0 or j==0:
                dp[i][j]=0
            elif 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])
    index = dp[n][m] 
    lcs = [""] * (index+1) 
    lcs[index] = "" 
    i = n
    j = m 
    while i > 0 and j > 0: 
  
        # If current character in X[] and Y are same, then 
        # current character is part of LCS 
        if s[i-1] == t[j-1]: 
            lcs[index-1] = s[i-1] 
            i-=1
            j-=1
            index-=1
  
        # If not same, then find the larger of two and 
        # go in the direction of larger value 
        elif dp[i-1][j] > dp[i][j-1]: 
            i-=1
        else: 
            j-=1
    print(''.join(lcs))
if __name__== '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def main():
    S = input()
    LS = len(S)
    T = input()
    LT = len(T)
    # LCS
    dp = [[0 for _ in range(LT + 1)] for _ in range(LS + 1)]
    for s in range(LS):
        for t in range(LT):
            if S[s] == T[t]:
                dp[s + 1][t + 1] = 1 + dp[s][t]
            else:
                dp[s + 1][t + 1] = max([dp[s][t + 1], dp[s + 1][t]])
    # recover
    s, t = LS, LT
    que = deque()
    que.appendleft('')
    while s > 0 and t > 0:
        if dp[s][t] == dp[s - 1][t]:
            s -= 1
        elif dp[s][t] == dp[s][t - 1]:
            t -= 1
        else:
            que.appendleft(S[s - 1])
            s -= 1
            t -= 1
    print(''.join(list(que)))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# dp[i][j] 文字列sのi-1番目までと文字列tのj-1番目までの文字を比較したときの最長部分列
# 添え字は0~(文字列の長さ) テーブルのi=0, j=0では値はゼロ 行列ともに文字列の長さより1大きい
# s[i]=t[j]のときdp[i+1][j+1]=dp[i][j]+1
# 等しくないときdp[i+1][j+1]=max(dp[i+1][j]+dp[i][j+1])
# 文字列の復元
# dpテーブルを一番右下から逆にたどる。
# s[i]=t[j]のとき、その文字をresの左側に保存して左上にジャンプ
# 等しくなければ、左か上が同じ値なので大きいほうにジャンプ
# 解答は文字列res

import numpy as np

# 入力
s = input()
t = input()

N = len(s)
M = len(t)

# 初期化
dp = np.zeros((N + 1, M + 1), dtype='int8')

# dpテーブル作成
for i in range(0, N):
    for j in range(0, M):
        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])

# 復元する文字を記憶するための文字列
res = ""

# 添え字の初期値 dpの右下、dp[N][M]からたどる
i = N
j = M

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

print(res)

Submission status: Time Limit Exceeded

Solution code:
s = input()
s_len = len(s)
t = input()
t_len = len(t)
dp = [[0] * (t_len + 1) for _ in range(s_len + 1)]
for i in range(s_len):
    S = s[i]
    for j in range(t_len):
        T = t[j]
        ni = i + 1
        nj = j + 1
        if S == T:
            dp[ni][nj] = max(dp[ni][nj], dp[i][j] + 1, dp[i][nj], dp[ni][j])
        else:
            dp[ni][nj] = max(dp[ni][nj], dp[i][nj], dp[ni][j])

nagasa = dp[s_len][t_len]

a = s_len
b = t_len
ans = []
while nagasa > 0:
    if dp[a][b] == nagasa:
        a -= 1
    elif dp[a + 1][b] == nagasa:
        b -= 1
    else:
        ans.append(s[a])
        nagasa -= 1
ans = ans[::-1]
print(*ans, sep="")

Submission status: Time Limit Exceeded

Solution code:
S = input()
T = input()

dp = [[0]*(len(T)+1) for _ in range(len(S)+1)]
prev = [[(-1,-1)]*(len(T)+1)for _ in range(len(S)+1)]

res = ""

for i in range(1,len(S)+1):
    for j in range(1,len(T)+1):
        if S[i-1] != T[j-1] or dp[i-1][j] != dp[i-1][j-1] or dp[i][j-1] != dp[i-1][j-1]:
            if dp[i-1][j] > dp[i][j-1]:
                dp[i][j] = dp[i-1][j]
                prev[i][j] = (i-1,j)
            else:
                dp[i][j] = dp[i][j-1]
                prev[i][j] = (i,j-1)
        else:
            dp[i][j] = dp[i-1][j-1] + 1
            res += S[i-1]
            prev[i][j] = (-2,-2)
to = (len(S), len(T))
res = ""
while to != (-1,-1):
    p = prev[to[0]][to[1]]
    if p[0] == -2:
        res += S[to[0]-1]
        to = (to[0]-1, to[1]-1)
    else:
        to = p
print(res[::-1])

Submission status: Time Limit Exceeded

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

hassame = False
for i, s_ in enumerate(s):
    if hassame or s_ == t[0]: dp[i+1][1]=1; hassame=True
hassame = False
for i, t_ in enumerate(t):
    if hassame or t_ == s[0]: dp[1][i+1]=1; hassame=True

lcs = 0
for i, s_ in enumerate(s):
    if i==0: continue
    for j, t_ in enumerate(t):
        if j==0: continue
        if s_!=t_:
            dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])
        else:
            dp[i+1][j+1] = dp[i][j]+1
        lcs = max(lcs, dp[i+1][j+1])

ans = ''
i, j = len(s), len(t)
while 0<i and 0<j:
        if s[i-1] == t[j-1]: ans+=s[i-1]; i-=1; j-=1
        else:
            if dp[i-1][j] > dp[i][j-1]: i-=1
            else: j-=1
print(ans[::-1])


for i in range(len(s)):
    dp+=s[i]

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
n = len(s)
m = len(t)
dp = [[""] * (m + 5) for _ in range(n + 5)]
for i in range(n):
    for j in range(m):
        if len(dp[i + 1][j]) < len(dp[i][j]):
            dp[i + 1][j] = dp[i][j]
        if len(dp[i][j + 1]) < len(dp[i][j]):
            dp[i][j + 1] = dp[i][j]
        if s[i] == t[j]:
            dp[i + 1][j + 1] = dp[i][j] + s[i]
# print(dp)
ans = ""
for i in range(n + 1):
    for j in range(m + 1):
        if len(ans) < len(dp[i][j]):
            ans = dp[i][j]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

IN=lambda : map(int, input().split())
LIN=lambda : list(IN())
mod=1000000007

#+++++

def main():
	#a = int(input())
	#b , c = IN()
	sa = input()[:-1]
	sb = input()[:-1]
	lcb = ['']*len(sb)
	for ac in sa:
		ll = ''
		for i, bc in enumerate(sb):
			if bc == ac:
				tll=ll
				if len(ll) < len(lcb[i]):
					ll = lcb[i]
				pre_len = len(lcb[i])
				post_len = len(tll) + 1
				if pre_len < post_len:
					lcb[i] = tll+ac
			else:
				if len(ll) < len(lcb[i]):
					ll = lcb[i]
	
	ret = max(lcb, key=lambda s:len(s))
	print(ret)
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Time Limit Exceeded

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

IN=lambda : map(int, input().split())
LIN=lambda : list(IN())
mod=1000000007

#+++++

def main():
	#a = int(input())
	#b , c = IN()
	sa = input()
	sb = input()
	lcb = ['']*len(sb)
	for ac in sa:
		ll = ''
		for i, bc in enumerate(sb):
			if bc == ac:
				tll=ll
				if len(ll) < len(lcb[i]):
					ll = lcb[i]
				pre_len = len(lcb[i])
				post_len = len(tll) + 1
				if pre_len < post_len:
					lcb[i] = tll+ac
			else:
				if len(ll) < len(lcb[i]):
					ll = lcb[i]
	
	ret = max(lcb, key=lambda s:len(s))
	print(ret)
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Time Limit Exceeded

Solution code:
S = input()
T = input()
# S = "abracadabra"
# T = "avadakedavra"
dp = [[[] for i in range(len(T)+1)] for j in range(len(S)+1)]
for i in range(1,len(S)+1):
    for j in range(1,len(T)+1):
        if i == 0 or j == 0: continue
        if S[i-1] == T[j-1]:
            dp[i][j].append("".join(dp[i-1][j-1]) + S[i-1])
        else:
            if len("".join(dp[i-1][j])) >= len("".join(dp[i][j-1])): 
                dp[i][j].append("".join(dp[i-1][j]))
            else:
                dp[i][j].append("".join(dp[i][j-1]))

print("".join(dp[len(S)][len(T)]))

Submission status: Time Limit Exceeded

Solution code:
S = input()
T = input()
dp = [["" for i in range(len(T)+1)] for j in range(len(S)+1)]
for i in range(1,len(S)+1):
    for j in range(1,len(T)+1):
        if i == 0 or j == 0: continue
        if S[i-1] == T[j-1]:
            dp[i][j] = dp[i-1][j-1] + S[i-1]
        else:
            if len(dp[i-1][j]) >= len(dp[i][j-1]): 
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = dp[i][j-1]
print(dp[len(S)][len(T)])

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
ls = len(s)
lt = len(t)
DP_len = [[0] * (lt+1) for i in range(ls+1)]
DP = [[''] * (lt+1) for i in range(ls+1)]
for i in range(1, ls+1):
    for j in range(1, lt+1):
        if s[i-1] == t[j-1]:
            if (DP_len[i-1][j-1] + 1 >= DP_len[i][j-1]) and (DP_len[i-1][j-1] + 1 >= DP_len[i-1][j]):
                DP[i][j] = DP[i-1][j-1] + s[i-1]
                DP_len[i][j] = DP_len[i - 1][j - 1] + 1
            else:
                if (DP_len[i-1][j] >= DP_len[i][j-1]) and (DP_len[i-1][j] >= DP_lenDP[i][j]):
                    DP[i][j] = DP[i-1][j]
                    DP_len[i][j] = DP_len[i - 1][j]
                elif (DP_len[i-1][j] <= DP_len[i][j-1]) and (DP_len[i][j-1] >= DP_len[i][j]):
                    DP[i][j] = DP[i][j-1]
                    DP_len[i][j] = DP_len[i][j-1]
        else:
            if (DP_len[i - 1][j] >= DP_len[i][j - 1]) and (DP_len[i - 1][j] >= DP_len[i][j]):
                DP[i][j] = DP[i - 1][j]
                DP_len[i][j] = DP_len[i - 1][j]
            elif (DP_len[i - 1][j] <= DP_len[i][j - 1]) and (DP_len[i][j - 1] >= DP_len[i][j]):
                DP[i][j] = DP[i][j - 1]
                DP_len[i][j] = DP_len[i][j - 1]

print(DP[ls][lt])

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
ls = len(s)
lt = len(t)
DP = [[''] * (lt+1) for i in range(ls+1)]
for i in range(1, ls+1):
    for j in range(1, lt+1):
        if s[i-1] == t[j-1]:
            if (len(DP[i-1][j-1]) + 1 >= len(DP[i][j-1])) and (len(DP[i-1][j-1]) + 1 >= len(DP[i-1][j])):
                DP[i][j] = DP[i-1][j-1] + s[i-1]
                flag = False
            else:
                if (len(DP[i-1][j]) >= len(DP[i][j-1])) and (len(DP[i-1][j]) >= len(DP[i][j])):
                    DP[i][j] = DP[i-1][j]
                elif (len(DP[i-1][j]) <= len(DP[i][j-1])) and (len(DP[i][j-1]) >= len(DP[i][j])):
                    DP[i][j] = DP[i][j-1]

        else:
            if (len(DP[i - 1][j]) >= len(DP[i][j - 1])) and (len(DP[i - 1][j]) >= len(DP[i][j])):
                DP[i][j] = DP[i - 1][j]
            elif (len(DP[i - 1][j]) <= len(DP[i][j - 1])) and (len(DP[i][j - 1]) >= len(DP[i][j])):
                DP[i][j] = DP[i][j - 1]

print(DP[ls][lt])

Submission status: Time Limit Exceeded

Solution code:
s=input()
t=input()
n1,n2=len(s),len(t)
dp=[[0]*(n1+1) for i in range(n2+1)]
st=''
for i in range(1,n2+1):
    for j in range(1,n1+1):
        if s[j-1]==t[i-1]:
            dp[i][j]=dp[i-1][j-1]+1
            #st+=s[j-1]
        else:
            dp[i][j]=max(dp[i-1][j],dp[i][j-1])
while i>0 and j>0:
    if t[i-1]==s[j-1]:
        st=s[j-1]+st
        i-=1
        j-=1
    elif dp[i][j-1]>dp[i-1][j]:
        j-=1
    else:
        i-=1
print(st)

Submission status: Time Limit Exceeded

Solution code:
s = [""]+list(input())
t = [""]+list(input())
dp = [[0 for x in range(len(s))] for x in range(len(t))]
for y in range(1,len(t)):
    for x in range(1,len(s)):
        if(t[y] == s[x]):
            dp[y][x] = dp[y-1][x-1]+1
        else:
            dp[y][x] = max(dp[y-1][x],dp[y][x-1])
y,x = len(t)-1,len(s)-1
ans = []
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.append(s[x])
        y -= 1
        x -= 1
ans.reverse()
print("".join(ans))

Submission status: Time Limit Exceeded

Solution code:
s=input()
t=input()
a=len(s)
b=len(t)
n_list=  ['' for i in range(a)]
b_list=['' for j in range(b)]
for i in range(b) :
  if s[0] in t[:i+1] :
    b_list[i]=s[0]
for i in range(a) :
  if t[0] in s[:i+1] :
    n_list[i]=t[0]

import copy
for i in range(1,b) :
  n_list1=copy.deepcopy(n_list)
  n_list[0]=b_list[i]
  for j in range(1,a) :
    
    if len(n_list1[j])>len(n_list[j]) :
      n_list[j]=n_list1[j]
    if len(n_list[j-1])>len(n_list[j]) :
      n_list[j]=n_list[j-1]
    if t[i]==s[j] and len(n_list1[j-1])+1>len(n_list[j])  :
      n_list[j] = n_list1[j - 1]+t[i]

print(n_list[-1])

Submission status: Time Limit Exceeded

Solution code:
s=input()
t=input()
a=len(s)
b=len(t)
n_list=  [['' for i in range(a)] for j in range(b)]
for i in range(b) :
  if s[0] in t[:i+1] :
    n_list[i][0]=s[0]
for i in range(a) :
  if t[0] in s[:i+1] :
    n_list[0][i]=t[0]


for i in range(1,b) :
  for j in range(1,a) :
    if len(n_list[i-1][j])>len(n_list[i][j]) :
      n_list[i][j]=n_list[i-1][j]
    if len(n_list[i][j-1])>len(n_list[i][j]) :
      n_list[i][j]=n_list[i][j-1]
    if t[i]==s[j] and len(n_list[i-1][j-1])+1>len(n_list[i][j])  :
      n_list[i][j] = n_list[i-1][j - 1]+t[i]

print(n_list[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
x=input()
y=input()
x_part=[[]]*len(x)
y_part=[[]]*len(y)
x_part[0]=['',x[0]]
y_part[0]=['',y[0]]
x_part1=['',x[0]]
for i in range(1,len(x)) :
  part=[]
  for item  in x_part1 :
    part.append(item+x[i])
  x_part1.extend(part)
 
 
y_part1=['',y[0]]
for i in range(1,len(y)) :
  part=[]
  for item  in y_part1 :
    part.append(item + y[i])
  y_part1.extend(part)
 
 
 
common=list(set(x_part1)& set(y_part1))

 
current_length=0
current_word=''
for item in common :
  if len(item)>current_length :
    current_length=len(item)
    current_word=item
print(current_word)

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    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)):
            match = s[i] == t[j]
            dp[i + 1][j + 1] = max(dp[i][j] + match , dp[i + 1][j + 1])
            dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i + 1][j + 1])
            dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][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
        elif dp[i][j] == dp[i - 1][j - 1] + 1:
            res = s[i - 1] + res
            i -= 1
            j -= 1

    print(res)
    
resolve()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Mon May  4 12:20:33 2020

@author: Kanaru Sato
"""

s = list(input())
t = list(input())

dp = [[-1 for i in range(len(t)+1)] for j 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] = ""
        elif s[i-1] == t[j-1]:
                dp[i][j] = dp[i-1][j-1]+s[i-1]
        else:
            p = len(dp[i][j-1])
            q = len(dp[i-1][j])
            if p > q:
                dp[i][j] = dp[i][j-1]
            else:
                dp[i][j] = dp[i-1][j]

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Mon May  4 12:03:46 2020

@author: Kanaru Sato
"""

import sys
sys.setrecursionlimit(10**9)

s = list(input())
t = list(input())

def lcs(a,b,i,j):
    if i == 0 or j == 0:
        return ""
    else:
        if a[i-1] == b[j-1]:
            return lcs(a,b,i-1,j-1)+a[i-1]
        else:
            p = len(lcs(a,b,i-1,j))
            q = len(lcs(a,b,i,j-1))
            if p >= q:
                return lcs(a,b,i-1,j)
            else:
                return lcs(a,b,i,j-1)

print(lcs(s,t,len(s),len(t)))

Submission status: Time Limit Exceeded

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

dp = [[0 for i in range(3010)] for j in range(3010)]

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+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])
        
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] + ans
        i -= 1
        j -= 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys


def solve(s: str, t: str):
    len_s = len(s)
    len_t = len(t)

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


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    s = next(tokens)  # type: str
    t = next(tokens)  # type: str
    solve(s, t)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

def inp_str():
    '''
    一行の文字をlistで取得
    '''
    return list(input())

s = inp_str()
t = inp_str()
n = len(s)-1
m = len(t)-1
value = [[0]*(m+1) for i in range(n+1)]
ans = [[""]*(m+1) for i in range(n+1)]


for i in range(n):
    for j in range(m):
        if s[i] == t[j]:
            value[i + 1][j + 1] = value[i][j] + 1
            ans[i + 1][j + 1] = "".join([ans[i][j], s[i]])
        elif value[i][j + 1] > value[i + 1][j]: #UP
            ans[i + 1][j + 1] = ans[i][j + 1]
            value[i + 1][j + 1] = value[i][j + 1]
        else:  # LEFT
            ans[i + 1][j + 1] = ans[i + 1][j]
            value[i + 1][j + 1] = value[i + 1][j]

print(ans[n][m])

Submission status: Time Limit Exceeded

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

def inp_str():
    '''
    一行の文字をlistで取得
    '''
    return list(input())

s = inp_str()
t = inp_str()
n = len(s)-1
m = len(t)-1
value = [[0]*(m+1) for i in range(n+1)]
ans = [[""]*(m+1) for i in range(n+1)]

for i in range(n):
    for j in range(m):
        if s[i] == t[j]:
            value[i + 1][j + 1] = value[i][j] + 1
            ans[i + 1][j + 1] = ans[i][j]+s[i]#"".join([ans[i][j], s[i]])
        elif value[i][j + 1] > value[i + 1][j]: #UP
            ans[i + 1][j + 1] = ans[i][j + 1]
            value[i + 1][j + 1] = value[i][j + 1]
        else:  # LEFT
            ans[i + 1][j + 1] = ans[i + 1][j]
            value[i + 1][j + 1] = value[i + 1][j]

print(ans[n][m])

Submission status: Time Limit Exceeded

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

def inp_str():
    '''
    一行の文字をlistで取得
    '''
    return list(input())[:-1]

s = inp_str()
t = inp_str()
n = len(s)
m = len(t)
value = [[0]*(m+1) for i in range(n+1)]
ans = [[""]*(m+1) for i in range(n+1)]

for i in range(n):
    for j in range(m):
        if s[i] == t[j]:
            value[i + 1][j + 1] = value[i][j] + 1
            ans[i + 1][j + 1] = ans[i][j]+s[i]#"".join([ans[i][j], s[i]])
        elif value[i][j + 1] > value[i + 1][j]: #UP
            ans[i + 1][j + 1] = ans[i][j + 1]
            value[i + 1][j + 1] = value[i][j + 1]
        else:  # LEFT
            ans[i + 1][j + 1] = ans[i + 1][j]
            value[i + 1][j + 1] = value[i + 1][j]

print(ans[n][m])

Submission status: Time Limit Exceeded

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

def inp_str():
    '''
    一行の文字をlistで取得
    '''
    return list(input())[:-1]


s = inp_str()
t = inp_str()
n = len(s)
m = len(t)
value = [[0]*(m+1) for i in range(n+1)]
ans = [[""]*(m+1) for i in range(n+1)]

for i in range(n):
    for j in range(m):
        if s[i] == t[j]:
            value[i + 1][j + 1] = value[i][j] + 1
            ans[i + 1][j + 1] = "".join([ans[i][j], s[i]])
        elif value[i][j + 1] > value[i + 1][j]: #UP
            ans[i + 1][j + 1] = ans[i][j + 1]
            value[i + 1][j + 1] = value[i][j + 1]
        else:  # LEFT
            ans[i + 1][j + 1] = ans[i + 1][j]
            value[i + 1][j + 1] = value[i + 1][j]

print(ans[n][m])

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

s = inp_str()
t = inp_str()
n = len(s)
m = len(t)
class node():
    def __init__(self):
        self.value = 0
        self.ans=""
value = [[0]*(m+1) for i in range(n+1)]
ans = [[""]*(m+1) for i in range(n+1)]

for i in range(n):
    for j in range(m):
        if s[i] == t[j]:
            value[i + 1][j + 1] = value[i][j] + 1
            ans[i + 1][j + 1] = "".join([ans[i][j], s[i]])
        elif value[i][j + 1] > value[i + 1][j]: #UP
            ans[i + 1][j + 1] = ans[i][j + 1]
            value[i + 1][j + 1] = value[i][j + 1]
        else:  # LEFT
            ans[i + 1][j + 1] = ans[i + 1][j]
            value[i + 1][j + 1] = value[i + 1][j]

print(ans[n][m])

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

s = inp_str()
t = inp_str()
n = len(s)
m = len(t)
class node():
    def __init__(self):
        self.value = 0
        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 = "".join([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:
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 = "".join([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)