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:
#!/usr/bin/env python3
import sys
from collections.abc import Iterable
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


def lcs(xs, ys):
    dp = [([''] * (len(ys) + 1)) for _ in range(len(xs) + 1)]
    for i, x in enumerate(xs):
        for j, y in enumerate(ys):
            dp[i + 1][j + 1] = dp[i][j + 1]
            if len(dp[i + 1][j + 1]) < len(dp[i + 1][j]):
                dp[i + 1][j + 1] = dp[i + 1][j]
            if len(dp[i + 1][j + 1]) < (len(dp[i][j]) + int(x == y)):
                dp[i + 1][j + 1] = dp[i][j] + x
    return dp[-1][-1]


def solve(s: str, t: str):
    return lcs(s, t)


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
    result = solve(s, t)
    if isinstance(result, Iterable) and not isinstance(result, str):
        result = '\n'.join([str(v) for v in result])
    print(result)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
S = input()
T = input()
len_S = len(S)
len_T = len(T)

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

# backtrack
ans = ''
i, j = len_S, len_T
while i > 0 and j > 0:
    if S[i-1] == T[j-1]:
        ans = S[i-1] + ans
        i, j = i - 1, j - 1
    else:
        if dp[i][j] == dp[i-1][j]:
            i -= 1
        else:
            j -= 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left as bl
def LIS(L):
    if not L:
        return 0
    seq = [L[0]]
    for i in L[1:]:
        if seq[-1] < i:
            seq.append(i)
        else:
            seq[bl(seq, i)] = i
    return len(seq)

def LCS(S, T):
    ls = len(S)
    lt = len(T)
    S = [-1] + [ord(s) for s in S]
    T = [-2] + [ord(t) for t in T]
    dp = [0]*((ls+1)*(lt+1))
    geta = ls + 1
    for j in range(1, lt+1):
        for i in range(1, ls+1):
            if S[i] == T[j]:
                dp[geta*j + i] = dp[geta*(j-1) + i-1] + 1
            else:
                dp[geta*j + i] = max(dp[geta*(j-1) + i], dp[geta*j + i-1])
    if not dp[-1]:
        return ''
    ans = [0]*dp[-1]
    i, j = ls, lt
    ctr = -1
    for _ in range(ls + lt):
        if i == 0 or j == 0:
            break
        if S[i] == T[j]:
            ans[ctr] = S[i]
            i -= 1
            j -= 1
            ctr -= 1
        elif dp[(j-1)*geta + i] >= dp[j*geta + i-1]:
            j -= 1
        else:
            i -= 1
    return ''.join([chr(a) for a in ans])

def LCS_length(S, T, alps = 150):
    S = [ord(s) for s in S]
    T = [ord(t) for t in T]
    M = [[] for _ in range(alps)]
    for i, s in enumerate(S):
        M[s].append(i)
    L = []
    for t in T:
        L.extend(reversed(M[t]))
    if not L:
        return 0
    return LIS(L)

s = input().strip()
t = input().strip()
print(LCS(s, t))
assert len(LCS(s, t)) == LCS_length(s, t), 'chigau'

Submission status: Time Limit Exceeded

Solution code:
def get_inputs():
    S = input()
    T = input()
    return S, T


def maxlenstring(L):
    max_l = max_i = -1
    for i, v in enumerate(L):
        if len(v) > max_l:
            max_l = len(v)
            max_i = i
    
    return L[max_i]


def dpcalc(S, T):
    #動的計画法のテーブルを用意する　初期値は全て0
    dp = [[""] * (len(S) + 1) for _ in range(len(T) + 1)]
    
    for j in range(1, len(T) + 1):
        for i in range(1, len(S) + 1):
            if S[i - 1] == T[j - 1]:
                dp[j][i] = maxlenstring([dp[j - 1][i - 1] + S[i - 1], dp[j - 1][i], dp[j][i - 1]])
            else:
                dp[j][i] = maxlenstring([dp[j - 1][i], dp[j][i - 1]])
    
    return dp[len(T)][len(S)]


S, T = get_inputs()
print(dpcalc(S, T))

Submission status: Time Limit Exceeded

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

s = input()
t = input()
dp = [[0]*(len(t) + 1) for i in range(len(s) + 1)]
for i in range(1,len(dp)):
    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 - 1][j],dp[i][j - 1])
out = ''
i = len(s)
j = len(t)
while i != 0 and j != 0:
    if s[i - 1] == t[j - 1]:
        out += s[i - 1]
        i -= 1
        j -= 1
    elif dp[i][j - 1]>dp[i - 1][j]:
        j -= 1
    else:
        i -= 1
print(out[::-1])

Submission status: Time Limit Exceeded

Solution code:
def f():
    # 入力から文字列を生成していく？
    s = input()
    t = input()
    ls, lt = len(s), len(t)
    dp = [[0] * (ls + 1) for _ in range(lt + 1)]
    for i in range(lt):
        for j in range(ls):
            if s[j] == t[i]:
                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])
    r = ''
    i += 1
    j += 1
    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:
            r = s[j - 1] + r
            j -= 1
            i -= 1
    return r


if __name__ == '__main__':
    ans = f()
    print(ans)

Submission status: Time Limit Exceeded

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

dp = [[[] for _ in range(len(S)+1)] for _ in range(len(T)+1)]
cdp = [[None for _ in range(len(S)+1)] for _ in range(len(T)+1)]
dp[0] = [[''] for _ in range(len(T)+1)]
cdp[0] = [0 for _ in range(len(T)+1)]

for i in range(1,len(T)+1):
    for j in range(len(S)+1):
        if j == 0:
            dp[i][j] = ['']
            cdp[i][j] = 0
            continue
        if S[j-1] == T[i-1]:
            dp[i][j] = [p + S[j-1] for p in dp[i-1][j-1]]
            cdp[i][j] = cdp[i-1][j-1] + 1
        else:
            if cdp[i][j-1] > cdp[i-1][j]:
                dp[i][j] = dp[i][j-1]
                cdp[i][j] = cdp[i][j-1]
            else:
                dp[i][j] = dp[i-1][j]
                cdp[i][j] = cdp[i-1][j]

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

Submission status: Time Limit Exceeded

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

dp = [[[] for _ in range(len(S)+1)] for _ in range(len(T)+1)]
dp[0] = [[''] for _ in range(len(T)+1)]

for i in range(1,len(T)+1):
    for j in range(len(S)+1):
        if j == 0:
            dp[i][j] = ['']
            continue
        if S[j-1] == T[i-1]:
            dp[i][j] = [p + S[j-1] for p in dp[i-1][j-1]]
        else:
            if len(dp[i][j-1][0]) > len(dp[i-1][j][0]):
                dp[i][j] = dp[i][j-1]
            else:
                dp[i][j] = dp[i-1][j]

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

Submission status: Time Limit Exceeded

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

# Get longest LCS num
dp = [[0] * (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])

# Restore LCS
h, w = len_s, len_t
ans = ""
while dp[h][w] != 0:
    while dp[h][w] == dp[h-1][w]:
        h -= 1
    while dp[h][w] == dp[h][w-1]:
        w -= 1
    h -= 1
    w -= 1
    ans += t[w]

print(ans[::-1])

Submission status: Time Limit Exceeded

Solution code:
s = input().rstrip()
t = input().rstrip()
len_s = len(s)
len_t = len(t)
lcs = [[""] * (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]:
            lcs[i][j] = lcs[i-1][j-1] + s[i-1]
        else:
            if len(lcs[i][j-1]) > len(lcs[i-1][j]):
                lcs[i][j] = lcs[i][j-1] 
            else:
                lcs[i][j] = lcs[i-1][j] 
print(lcs[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
def lcs(a, b):
    n = len(a)
    m = len(b)
    dp = [[0] * (m + 1) for _ in range(n + 1)]

    for i in range(n):
        for j in range(m):
            if a[i] == b[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])

    lcs_str = ''
    i, j = n, m
    while i >= 1 and j >= 1:
        if a[i - 1] == b[j - 1]:
            lcs_str += a[i - 1] #or b[j - 1]
            i -= 1
            j -= 1
        else:
            if dp[i - 1][j] > dp[i][j - 1]:
                i -= 1
            else:
                j -= 1

    return lcs_str[::-1]


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

Submission status: Time Limit Exceeded

Solution code:
s=input()
t=input()
ns,nt=len(s),len(t)
DP=[[""]*(nt+1) for i in range(ns+1)]
for i in range(ns):
  for j in range(nt):
    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[ns][nt])

Submission status: Time Limit Exceeded

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

S = len(s)
T = len(t)

dp = [[""] * T for i in range(S)]

for i, SS in enumerate(s):
    for j, TT in enumerate(t):
        ii = max(0,i-1)
        jj = max(0,j-1)
        if SS == TT:
            dp[i][j] = dp[ii][jj] + SS
        else:
            if len(dp[i][jj]) > len(dp[ii][j]):
                dp[i][j] = dp[i][jj]
            else:
                dp[i][j] = dp[ii][j]
print(dp[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
def f(s,t):
    sn = len(s)
    tn = len(t)
    dp = [[[]] * (tn + 1) for _ in range(sn + 1)]
    dpi1 = dp[0]
    for i in range(1, sn + 1):
        dpi = dp[i]
        for j in range(1, tn + 1):
            if s[i - 1] == t[j - 1]:
                dpi[j] = dpi1[j - 1] + [s[i - 1]]
            else:
                if len(dpi1[j]) > len(dpi[j - 1]):
                    dpi[j] = dpi1[j]
                else:
                    dpi[j] = dpi[j - 1]
        dpi1 = dpi
    print(*dp[-1][-1],sep="")

s = input()
t = input()
f(s,t)

Submission status: Time Limit Exceeded

Solution code:
def f(s,t):
    sn = len(s)
    tn = len(t)
    dp = [[""] * (tn + 1) for _ in range(sn + 1)]
    dpi1 = dp[0]
    for i in range(1, sn + 1):
        dpi = dp[i]
        for j in range(1, tn + 1):
            if s[i - 1] == t[j - 1]:
                dpi[j] = dpi1[j - 1] + s[i - 1]
            else:
                if len(dpi1[j]) > len(dpi[j - 1]):
                    dpi[j] = dpi1[j]
                else:
                    dpi[j] = dpi[j - 1]
        dpi1 = dpi
    print(dp[-1][-1])

s = input()
t = input()
f(s,t)

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
sn = len(s)
tn = len(t)
dp = [[""] * (tn + 1) for _ in range(sn + 1)]
dpi1 = dp[0]
for i in range(1, sn + 1):
    dpi = dp[i]
    for j in range(1, tn + 1):
        if s[i - 1] == t[j - 1]:
            dpi[j] = dpi1[j - 1] + s[i - 1]
        else:
            if len(dpi1[j]) > len(dpi[j - 1]):
                dpi[j] = dpi1[j]
            else:
                dpi[j] = dpi[j - 1]
    dpi1 = dpi
print(dp[-1][-1])

Submission status: Time Limit Exceeded

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

len_s = len(s)
len_t = len(t)

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

i = len_s
j = len_t
str = ''

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

s = input()
t = input()

len_s = len(s)
len_t = len(t)

dp = np.zeros((len_s+1, len_t+1), dtype = int)

for i in range(len_s):
        for j in range(len_t):
                if s[i] == t[j]:
                        dp[i+1, j+1] = np.maximum( dp[i+1, j+1], dp[i, j] + 1)
                dp[i+1, j+1] = np.maximum(dp[i+1,j+1], dp[i+1,j])
                dp[i+1, j+1] = np.maximum(dp[i+1,j+1], dp[i,j+1])
                # print(dp)

# print(dp[len_s,len_t])

i = len_s
j = len_t
str = ''

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

s = input()
t = input()

lens = len(s)
lent = len(t)

dp = [[{'str': '', 'len': 0} for _ in range(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]:
            candidate = max(dp[i-1][j-1]['len']+1, dp[i-1][j]['len'], dp[i][j-1]['len'])
            if candidate == dp[i-1][j-1]['len']+1:
                dp[i][j] = {'str': dp[i-1][j-1]['str'] + s[i-1], 'len': candidate}
                continue
            elif candidate == dp[i-1][j]['len']:
                dp[i][j] = {'str': dp[i-1][j]['str'], 'len': candidate}
                continue
            else:
                dp[i][j] = {'str': dp[i][j-1]['str'], 'len': candidate}
        else:
            candidate = max(dp[i-1][j]['len'], dp[i][j-1]['len'])
            if candidate == dp[i-1][j]['len']:
                dp[i][j] = {'str': dp[i-1][j]['str'], 'len': candidate}
                continue
            else:
                dp[i][j] = {'str': dp[i][j-1]['str'], 'len': candidate}

print(dp[lens][lent]['str'])

Submission status: Time Limit Exceeded

Solution code:
s=input()
t=input()
dp=[["" for i in range(len(t)+1)] for i in range(len(s)+1)]
for i,S in enumerate(s,1):
  for j,T in enumerate(t,1):
    if(S==T):
      dp[i][j]=dp[i-1][j-1]+S
    else:
      a=dp[i][j-1]
      b=dp[i-1][j]
      if(len(a)>len(b)):
        dp[i][j]=a
      else:
        dp[i][j]=b
print(dp[-1][-1])

Submission status: Time Limit Exceeded

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

def lcs(s,t):
    n=len(s)
    m=len(t)
    for i in range(0,n+1):
        for j in range(0,m+1):
            if i==0 or j==0:
                L[i][j]=0
            elif 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])
lcs(s,t)
ans=[]
i=len(s)
j=len(t)
while L[i][j]!=0:
    if L[i][j]!=L[i-1][j] or L[i][j]!=L[i][j-1]:
        ans.append(s[i-1])
        i-=1
        j-=1
    else :
        if L[i][j]==L[i-1][j]:
            i-=1
            continue
        else :
            j-=1
            continue
print(''.join(ans[::-1]))

Submission status: Time Limit Exceeded

Solution code:
s=' '+input()
t=' '+input()
dp=[]
dp_l=[]
for i in range(len(s)):
    sub_list=[]
    l_list=[]
    for j in range(len(t)):
        sub_list.append('')
        l_list.append(0)
    dp.append(sub_list)
    dp_l.append(l_list)
for i in range(1,len(s)):
    for j in range(1,len(t)):
        if s[i]==t[j]:
            dp[i][j]=dp[i-1][j-1]+s[i]
            dp_l[i][j]=dp_l[i-1][j-1]+1
        else:
            if dp_l[i-1][j]>dp_l[i][j-1]:
                dp[i][j]=dp[i-1][j]
                dp_l[i][j]=dp_l[i-1][j]
            else:
                dp[i][j]=dp[i][j-1]
                dp_l[i][j]=dp_l[i][j-1]
print(dp[len(s)-1][len(t)-1])

Submission status: Time Limit Exceeded

Solution code:
s=' '+input()
t=' '+input()
dp=[]
for i in range(len(s)):
    sub_list=[]
    for j in range(len(t)):
        sub_list.append('')
    dp.append(sub_list)
for i in range(1,len(s)):
    for j in range(1,len(t)):
        if s[i]==t[j]:
            dp[i][j]=dp[i-1][j-1]+s[i]
        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)-1][len(t)-1])

Submission status: Time Limit Exceeded

Solution code:
x = input()
y = input()
lx = len(x)
ly = len(y)

lcs = [[''] * (ly + 1) for _ in range(lx + 1)]
for i_x in range(lx):
    for i_y in range(ly):
        if x[i_x] == y[i_y]:
            lcs[i_x+1][i_y+1] = lcs[i_x][i_y] + x[i_x]
        else:
            lcs[i_x+1][i_y+1] = max(lcs[i_x+1][i_y], lcs[i_x][i_y+1], key=len)

print(lcs[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
x = input()
y = input()
lx = len(x)
ly = len(y)

chars = [[''] * (ly + 1) for _ in range(lx + 1)]
length = [[0] * (ly + 1) for _ in range(lx + 1)]
prev = [[0b00] * (ly + 1) for _ in range(lx + 1)]

for i_x in range(lx):
    for i_y in range(ly):
        if x[i_x] == y[i_y]:
            length[i_x+1][i_y+1] = length[i_x][i_y] + 1
            chars[i_x+1][i_y+1] = x[i_x]
            prev[i_x+1][i_y+1] = 0b11
        elif length[i_x+1][i_y] > length[i_x][i_y+1]:
            length[i_x+1][i_y+1] = length[i_x+1][i_y]
            prev[i_x+1][i_y+1] = 0b01
        else:
            length[i_x+1][i_y+1] = length[i_x][i_y+1]
            prev[i_x+1][i_y+1] = 0b10

lcs = [''] * length[-1][-1]
i_x, i_y = lx, ly
i = 1
while i_x * i_y:
    if prev[i_x][i_y] == 0b11:
        lcs[-i] = chars[i_x][i_y]
        i += 1
    i_x, i_y = i_x - ((prev[i_x][i_y] & 0b10) >> 1), i_y - (prev[i_x][i_y] & 0b01)

print(''.join(lcs))

Submission status: Time Limit Exceeded

Solution code:
x = input()
y = input()

lcs = [[''] * (len(y) + 1) for _ in range(len(x) + 1)]
for i_x in range(len(x)):
    for i_y in range(len(y)):
        if x[i_x] == y[i_y]:
            lcs[i_x+1][i_y+1] = lcs[i_x][i_y] + x[i_x]
        elif len(lcs[i_x+1][i_y]) > len(lcs[i_x][i_y+1]):
            lcs[i_x+1][i_y+1] = lcs[i_x+1][i_y]
        else:
            lcs[i_x+1][i_y+1] = lcs[i_x][i_y+1]

print(lcs[-1][-1])

Submission status: Time Limit Exceeded

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

for i in range(s_num):
    for j in range(t_num):
        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[s_num][t_num])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
sList, tList = input(), input()
dp = np.zeros((len(sList)+1, len(tList)+1), dtype=np.int16)


# 横方向で回す
for i, s in enumerate(sList, start=1):
    for j, t in enumerate(tList, start=1):
        dp[i][j] = max([dp[i][j - 1], dp[i-1][j],
                        dp[i-1][j-1] + 1 if s == t else 0])
m = dp[i][j]
ans = ""
# traceback
cnt = 0
while i + j != 0:
    if dp[i - 1][j - 1] == m - 1 and tList[j-1] == sList[i-1]:
        ans = tList[j-1] + ans
        i -= 1
        j -= 1
        m -= 1
    else:
        if dp[i - 1][j] == m:
            i -= 1
        elif dp[i][j-1] == m:
            j -= 1
    cnt += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
sList, tList = input(), input()
dp = np.zeros((len(sList)+1, len(tList)+1), dtype=np.int16)


# 横方向で回す
for i, s in enumerate(sList, start=1):
    for j, t in enumerate(tList, start=1):
        dp[i][j] = np.max([dp[i][j - 1], dp[i-1][j],
                           dp[i-1][j-1] + 1 if s == t else 0])
m = dp[i][j]
ans = ""
# traceback
cnt = 0
while i + j != 0:
    if dp[i - 1][j - 1] == m - 1 and tList[j-1] == sList[i-1]:
        ans = tList[j-1] + ans
        i -= 1
        j -= 1
        m -= 1
    else:
        if dp[i - 1][j] == m:
            i -= 1
        elif dp[i][j-1] == m:
            j -= 1
    cnt += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
sList, tList = input(), input()

dp = [[""] * (len(tList) + 1) for _ in range(2)]
index = 0

# 横方向で回す
for i, s in enumerate(sList, start=1):
    index = i % 2
    for j, t in enumerate(tList, start=1):
        dp[index][j] = max([dp[index][j - 1], dp[index-1][j],
                            dp[index-1][j-1] + s if s == t else ""], key=len)


print(dp[index][-1])

Submission status: Time Limit Exceeded

Solution code:
sList, tList = map(list, sorted([input(), input()], key=lambda x: len(x)))
#sList, tList = map(list, sorted(["sd;fnas;ncnlaubsukefbcasjbdlcbaslidoc;ulabnuebchasvdbcnuayrfivoasdbfkasvludfhwialunejcbasdnbciluahweflicbja",
#                                 "sjdnlifvbasublchawubeyfcainwbidcnbasvebhfcjhbwavendjkcahbsjdbcbasuibefcasjhdvcanwukehfucanbshdbc"], key=lambda x: len(x)))

dp = [[["", 0]] * (len(tList) + 1) for _ in range(2)]
index = 0
for i, s in enumerate(sList, start=1):
    index = i % 2
    sameStr, sameStrLen = "", 0
    for j, t in enumerate(tList, start=1):
        aboveStr, aboveStrLen = dp[index-1][j]
        if s[0] == t[0]:
            sameStr = dp[index - 1][j - 1][0] + s[0]
            sameStrLen = dp[index - 1][j - 1][1] + 1

        if sameStrLen > aboveStrLen:
            dp[index][j] = sameStr, sameStrLen
        else:
            dp[index][j] = aboveStr, aboveStrLen

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

Submission status: Time Limit Exceeded

Solution code:
import string, random
def randomname(n):
    return ''.join(random.choices(string.ascii_letters + string.digits, k=n))

#sList, tList = list(randomname(3000)), list(randomname(3000))
sList, tList = list(input()), list(input())

dp = [[[0, ""] for _ in range(len(tList) + 1)] for _ in range(2)]
index = 0
for i, s in enumerate(sList, start=1):
    index = i % 2
    sameLen = 0
    sameStr = ""
    for j, t in enumerate(tList, start=1):
        aboveLen = dp[index-1][j][0]
        aboveStr = dp[index-1][j][1]
        if s == t:
            sameLen = dp[index-1][j-1][0] + 1
            sameStr = dp[index-1][j-1][1] + s
        if sameLen > aboveLen:
            dp[index][j][0] = sameLen
            dp[index][j][1] = sameStr
        else:
            dp[index][j][0] = aboveLen
            dp[index][j][1] = aboveStr

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

Submission status: Time Limit Exceeded

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

dp = [['']*(len(T)+1) for _ in range(len(S)+1)]

for i, s in enumerate(S):
    for j, t in enumerate(T):
        if s == t:
            dp[i+1][j+1] = dp[i][j] + s
        else:
            dp[i+1][j+1] = dp[i+1][j] if len(dp[i+1][j]) > len(dp[i][j+1]) else dp[i][j+1]
print(dp[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sList, tList = list(input()), list(input())

dp = [[""] * (len(tList) + 1) for _ in range(2)]
index = 0
for i, s in enumerate(sList, start=1):
    index = i % 2
    sameStr = ""
    for j, t in enumerate(tList, start=1):
        aboveStr = dp[index-1][j]
        if s == t:
            sameStr = dp[index-1][j-1] + s
        dp[index][j] = sameStr if len(sameStr) > len(aboveStr) else aboveStr

print(dp[index][-1])

Submission status: Time Limit Exceeded

Solution code:
sList, tList = map(list, sorted([input(), input()], key=lambda x: len(x)))

dp = [[""] * (len(tList) + 1) for _ in range(2)]
index = 0
for i, s in enumerate(sList, start=1):
    index = i % 2
    sameStr = ""
    for j, t in enumerate(tList, start=1):
        aboveStr = dp[index-1][j]
        if s == t:
            sameStr = dp[index-1][j-1] + s
        dp[index][j] = sameStr if len(sameStr) > len(aboveStr) else aboveStr

print(dp[index][-1])

Submission status: Time Limit Exceeded

Solution code:
s, t = sorted([input(), input()], key=lambda x: len(x))
len_s, len_t = len(s), len(t)

dp = [[""] * len_t for _ in range(2)]
index = 0
for i in range(len_s):
    index = i % 2
    sameStr = ""
    for j in range(len_t):
        aboveStr = dp[index-1][j]
        if s[i] == t[j]:
            sameStr = aboveStr + s[i]
        dp[index][j] = sameStr if len(sameStr) >= len(aboveStr) else aboveStr

print(dp[index][-1])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# coding: utf-8

def rev_enumerate(sequence, start=0):
    n = start
    for elem in sequence:
        yield n, elem
        n -= 1

def main():
    #raw = ["axyb",
    #       "abyxb"]
    #raw = ["abracadabra",
    #       "avadakedavra"]
    #ss, ts = raw
    import sys
    ss = sys.stdin.readline()[:-1]
    ts = sys.stdin.readline()[:-1]
    slen = len(ss)
    tlen = len(ts)
    dp = [[0] * (slen + 1) for _ in range(tlen + 1)]
    for i, t in rev_enumerate(reversed(ts), tlen - 1):
        for j, s in rev_enumerate(reversed(ss), slen - 1):
            if s == t:
                dp[i][j] = max(dp[i+1][j], dp[i][j+1], dp[i+1][j+1] + 1)
            else:
                dp[i][j] = max(dp[i+1][j], dp[i][j+1])
    i, j = 0, 0
    ans = ""
    #for xs in dp:
    #    print(" ".join(map(str, xs)))
    while i < tlen and j < slen:
        if dp[i][j] == dp[i+1][j]:
            i += 1
        elif dp[i][j] == dp[i][j+1]:
            j += 1
        else:
            ans += ss[j]
            i += 1
            j += 1
    print(ans)

main()

Submission status: Time Limit Exceeded

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

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] = (dp[i][j][0] + s[i][0], dp[i][j][1] + 1)
        else:
            dp[i+1][j+1] = dp[i][j+1] if dp[i][j +
                                               1][1] >= dp[i+1][j][1] else dp[i+1][j]

lcs = dp[len(s)][len(t)][0]
print('', end='') if lcs == '' else print(lcs)

Submission status: Time Limit Exceeded

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

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)):
        if s[i] == t[j]:
            dp[i+1][j+1] = dp[i][j] + s[i]
        else:
            dp[i+1][j+1] = max([dp[i][j+1], dp[i+1][j]], key=lambda x: len(x))

lcs = dp[len(s)][len(t)]
print('', end='') if lcs == '' else print(lcs)

Submission status: Time Limit Exceeded

Solution code:
s = [x for x in input()]
t = [x for x in input()]
dp = [['' for i in range(len(s)+1)] for j in range(len(t)+1)]
for i in range(len(s)-1,-1,-1):
    for j in range(len(t)-1,-1,-1):
        a = dp[j+1][i]
        b = dp[j][i+1]
        if s[i] == t[j]:
            c = s[i] + dp[j+1][i+1]
        else:
            c = ''
        dp[j][i] = max(a, b, c,key=len)
print(dp[0][0])

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(2100000000)
s = [x for x in input()]
t = [x for x in input()]
dp = [['' for i in range(len(s))] for j in range(len(t))]
dpcheck = [[False for i in range(len(s))] for j in range(len(t))]
def dppp(ns,nt):
    global dp,s,t,dpcheck
    if ns == len(s) or nt == len(t):return ''
    if dpcheck[nt][ns] == True:return dp[nt][ns]
    if s[ns] == t[nt]:
        get = s[ns] + dppp(ns+1,nt+1)
    else:
        get = ''
    sgo = dppp(ns+1,nt)
    tgo = dppp(ns,nt+1)
    dpcheck[nt][ns] = True
    if len(sgo) >= len(tgo) and len(sgo) >= len(get):
        dp[nt][ns] = sgo
        return sgo
    elif len(tgo) >= len(sgo) and len(tgo) >= len(get):
        dp[nt][ns] = tgo
        return tgo
    else:
        dp[nt][ns] = get
        return get
ans = dppp(0,0)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(2000000000)
s = [x for x in input()]
t = [x for x in input()]
dp = [['' for i in range(len(s))] for j in range(len(t))]
def dppp(ns,nt):
    global dp,s,t
    if ns == len(s) or nt == len(t):return ''
    if dp[nt][ns] != '':return dp[nt][ns]
    if s[ns] == t[nt]:
        get = s[ns] + dppp(ns+1,nt+1)
    else:
        get = ''
    sgo = dppp(ns+1,nt)
    tgo = dppp(ns,nt+1)
    if len(sgo) >= len(tgo) and len(sgo) >= len(get):
        dp[nt][ns] = sgo
        return sgo
    elif len(tgo) >= len(sgo) and len(tgo) >= len(get):
        dp[nt][ns] = tgo
        return tgo
    else:
        dp[nt][ns] = get
        return get
ans = dppp(0,0)
print(ans)

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

m = len(s)
n = len(t)
ans = []
while m > 0 or n > 0:
    if m >= 1 and dp[m][n] == dp[m-1][n]:
        m -= 1
    elif n >= 1 and dp[m][n] == dp[m][n-1]:
        n -= 1
    else:
        m -= 1
        n -= 1
        ans.insert(0, s[m])


print(''.join(ans))

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = 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)):
        if len(dp[i+1][j]) > len(dp[i+1][j+1]):
            dp[i+1][j+1] = dp[i+1][j]
        if len(dp[i][j+1]) > len(dp[i+1][j+1]):
            dp[i+1][j+1] = dp[i][j+1]
        if s[i] == t[j]:
            if len(dp[i][j]) + 1 > len(dp[i+1][j+1]):
                dp[i+1][j+1] = dp[i][j] + s[i]

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

Submission status: Time Limit Exceeded

Solution code:
"""
AtCoder Educational DP Contest
https://atcoder.jp/contests/dp/tasks/dp_e

F - LCS

value scatters less than weight does
"""
MAX_VALUE_SUM = 100000
DEFAULT_WEIGHT = 100000000007

import collections
import itertools as it


def solve2(s, t):
    len_s, len_t = len(s), len(t)
    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:
                n, iterable = dp[i - 1][j - 1]
                dp[i][j] = (n + 1, it.chain(iterable, [cs]))
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1], key=lambda tup: tup[0])
    return "".join(dp[len(s)][len(t)][1])


seq1 = input().strip()
seq2 = input().strip()
res = solve2(seq1, seq2)
print(res)

Submission status: Time Limit Exceeded

Solution code:
"""
AtCoder Educational DP Contest
https://atcoder.jp/contests/dp/tasks/dp_e

F - LCS

value scatters less than weight does
"""
MAX_VALUE_SUM = 100000
DEFAULT_WEIGHT = 100000000007

import collections


def solve(s, t):
    dp = collections.defaultdict(list)
    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] + [cs]
            else:
                dp[i, j] = max(dp[i - 1, j], dp[i, j - 1], key=len)
    return "".join(dp[len(s), len(t)])


seq1 = input().strip()
seq2 = input().strip()
res = solve(seq1, seq2)
print(res)