Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

N,M,K=map(int,input().split())
mod=10**9+7

def Combi2(a,b):#aは大きいが、bは小さいとき
    if b>a:
        return 0
    ANS=1
    for i in range(min(b,a-b)):
        ANS=ANS*(a-i)*pow(min(b,a-b)-i,mod-2,mod)

    return ANS%mod

SUM_N=SUM_M=0
for i in range(N):
    SUM_N+=i*(N-i)

for i in range(M):
    SUM_M+=i*(M-i)

#print((SUM_N*(M**2)+SUM_M*(N**2))/Combi2(N*M,2)*Combi2(N*M,K)*K*(K-1)//2%mod)
print((SUM_N*(M**2)+SUM_M*(N**2))*pow(Combi2(N*M,2),mod-2,mod)*Combi2(N*M,K)*K*(K-1)*pow(2,mod-2,mod)%mod)


Fixed submission:
import sys
input = sys.stdin.readline

N,M,K=map(int,input().split())
mod=10**9+7

def Combi2(a,b):#aは大きいが、bは小さいとき
    if b>a:
        return 0
    ANS=1
    for i in range(min(b,a-b)):
        ANS=ANS*(a-i)*pow(min(b,a-b)-i,mod-2,mod)%mod

    return ANS%mod

SUM_N=SUM_M=0
for i in range(N):
    SUM_N+=i*(N-i)

for i in range(M):
    SUM_M+=i*(M-i)

#print((SUM_N*(M**2)+SUM_M*(N**2))/Combi2(N*M,2)*Combi2(N*M,K)*K*(K-1)//2%mod)
print((SUM_N*(M**2)+SUM_M*(N**2))*pow(Combi2(N*M,2),mod-2,mod)*Combi2(N*M,K)*K*(K-1)*pow(2,mod-2,mod)%mod)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

N,M,K=map(int,input().split())
mod=10**9+7

def Combi2(a,b):#aは大きいが、bは小さいとき
    if b>a:
        return 0
    ANS=1
    for i in range(min(b,a-b)):
        ANS=ANS*(a-i)*pow(min(b,a-b)-i,mod-2,mod)

    return ANS%mod

SUM_N=SUM_M=0
for i in range(N):
    SUM_N+=i*(N-i)

for i in range(M):
    SUM_M+=i*(M-i)

#print((SUM_N*(M**2)+SUM_M*(N**2))/Combi2(N*M,2)*Combi2(N*M,K)*K*(K-1)//2%mod)
print((SUM_N*(M**2)+SUM_M*(N**2))*pow(Combi2(N*M,2),mod-2,mod)*Combi2(N*M,K)*K*(K-1)*pow(2,mod-2,mod)%mod)


Fixed submission:
import sys
input = sys.stdin.readline

N,M,K=map(int,input().split())
mod=10**9+7

def Combi2(a,b):#aは大きいが、bは小さいとき
    if b>a:
        return 0
    ANS=1
    for i in range(min(b,a-b)):
        ANS=ANS*(a-i)*pow(min(b,a-b)-i,mod-2,mod)%mod

    return ANS%mod

SUM_N=SUM_M=0
for i in range(N):
    SUM_N+=i*(N-i)

for i in range(M):
    SUM_M+=i*(M-i)

#print((SUM_N*(M**2)+SUM_M*(N**2))/Combi2(N*M,2)*Combi2(N*M,K)*K*(K-1)//2%mod)
print((SUM_N*(M**2)+SUM_M*(N**2))*pow(Combi2(N*M,2),mod-2,mod)*Combi2(N*M,K)*K*(K-1)*pow(2,mod-2,mod)%mod)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

H,W=map(int,input().split())
MAP=[list(input().strip()) for i in range(H)]

from collections import deque
QUE=deque()

for i in range(H):
    for j in range(W):

        if MAP[i][j]=="#":
            QUE.append([i,j,0])

ANS=[[-1]*W for i in range(H)]

while QUE:
    NQUE=deque()
    while QUE:
        x,y,z=QUE.pop()
        ANS[x][y]=z

        for nx,ny in [[x+1,y],[x-1,y],[x,y+1],[x,y-1]]:
            if nx<0 or ny<0 or nx>=H or ny>=W:
                continue

            if ANS[nx][ny]!=-1:
                continue

            NQUE.append([nx,ny,z+1])

    QUE=NQUE

            
print(max([max(ANS[i]) for i in range(H)]))
    
    


Fixed submission:
import sys
input = sys.stdin.readline

H,W=map(int,input().split())
MAP=[list(input().strip()) for i in range(H)]

ANS=[[-1]*W for i in range(H)]

from collections import deque
QUE=deque()

for i in range(H):
    for j in range(W):

        if MAP[i][j]=="#":
            QUE.append([i,j,0])
            ANS[i][j]=0

while QUE:
    NQUE=deque()
    while QUE:
        x,y,z=QUE.pop()

        for nx,ny in [[x+1,y],[x-1,y],[x,y+1],[x,y-1]]:
            if nx<0 or ny<0 or nx>=H or ny>=W:
                continue

            if ANS[nx][ny]!=-1:
                continue

            NQUE.append([nx,ny,z+1])
            ANS[nx][ny]=z+1

    QUE=NQUE

            
print(max([max(ANS[i]) for i in range(H)]))

Buggy python submission (verdict: Time Limit Exceeded):
H,W=map(int,input().split())
MAP=[list(input()) for i in range(H)]

from collections import deque
import copy
QUE=deque()

for i in range(H):
    for j in range(W):

        if MAP[i][j]=="#":
            QUE.append([i,j,0])

ANS=[[-1]*W for i in range(H)]

while QUE:
    NQUE=deque()
    while QUE:
        x,y,z=QUE.pop()
        ANS[x][y]=z

        for nx,ny in [[x+1,y],[x-1,y],[x,y+1],[x,y-1]]:
            if nx<0 or ny<0 or nx>=H or ny>=W:
                continue

            if ANS[nx][ny]!=-1:
                continue

            NQUE.append([nx,ny,z+1])

    QUE=NQUE

            
print(max([max(ANS[i]) for i in range(H)]))

Fixed submission:
import sys
input = sys.stdin.readline

H,W=map(int,input().split())
MAP=[list(input().strip()) for i in range(H)]

ANS=[[-1]*W for i in range(H)]

from collections import deque
QUE=deque()

for i in range(H):
    for j in range(W):

        if MAP[i][j]=="#":
            QUE.append([i,j,0])
            ANS[i][j]=0

while QUE:
    NQUE=deque()
    while QUE:
        x,y,z=QUE.pop()

        for nx,ny in [[x+1,y],[x-1,y],[x,y+1],[x,y-1]]:
            if nx<0 or ny<0 or nx>=H or ny>=W:
                continue

            if ANS[nx][ny]!=-1:
                continue

            NQUE.append([nx,ny,z+1])
            ANS[nx][ny]=z+1

    QUE=NQUE

            
print(max([max(ANS[i]) for i in range(H)]))
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

N=int(input())
B=list(map(int,input().split()))

def dfs(B,LEN,ANS):
    #print(B,LEN,ANS)
    if LEN==0:
        for a in ANS[::-1]:
            print(a)
        sys.exit()
    for i in range(LEN):
        if B[i]==i+1:
            C=B[:i]+B[i+1:]
            dfs(C,LEN-1,ANS+[i+1])

dfs(B,N,[])
print(-1)

Fixed submission:
import sys
input = sys.stdin.readline

N=int(input())
B=list(map(int,input().split()))

for i in range(N):
    if B[i]>i+1:
        print(-1)
        sys.exit()

def dfs(B,LEN,ANS):
    #print(B,LEN,ANS)
    if LEN==0:
        for a in ANS[::-1]:
            print(a)
        sys.exit()
    for i in range(LEN-1,-1,-1):
        if B[i]==i+1:
            C=B[:i]+B[i+1:]
            dfs(C,LEN-1,ANS+[i+1])

dfs(B,N,[])
print(-1)
Buggy python submission (verdict: Runtime Error):
import sys

N=int(input())
C=[int(input()) for i in range(N)]
mod=10**9+7

if N==1:
    print(1)
    sys.exit()

S=[C[0]]

for i in range(1,N):
    if C[i]!=C[i-1]:
        S.append(C[i])

L=len(S)

if L==1:
    print(1)
    sys.exit()

AL=[[] for i in range(2*10**5+1)]

for i in range(L):
    AL[S[i]].append(i)

PLUS=[0]*(N+1)

NOW=1

for i in range(L):
    NOW,PLUS[S[i]]=(NOW+PLUS[S[i]])%mod,(PLUS[S[i]]+NOW)%mod
    #PLUS[S[i]]+=NOW
    

    #print(NOW,PLUS)

#print(PLUS)
print(NOW)
    
    


Fixed submission:
import sys

N=int(input())
C=[int(input()) for i in range(N)]
mod=10**9+7

if N==1:
    print(1)
    sys.exit()

S=[C[0]]

for i in range(1,N):
    if C[i]!=C[i-1]:
        S.append(C[i])

L=len(S)

if L==1:
    print(1)
    sys.exit()

AL=[[] for i in range(2*10**5+1)]

for i in range(L):
    AL[S[i]].append(i)

PLUS=[0]*(2*10**5+1)

NOW=1

for i in range(L):
    NOW,PLUS[S[i]]=(NOW+PLUS[S[i]])%mod,(PLUS[S[i]]+NOW)%mod
    #PLUS[S[i]]+=NOW
    

    #print(NOW,PLUS)

#print(PLUS)
print(NOW)

Buggy python submission (verdict: Runtime Error):
import sys

N=int(input())
C=[int(input()) for i in range(N)]
mod=10**9+7

if N==1:
    print(1)
    sys.exit()

S=[C[0]]

for i in range(1,N):
    if C[i]!=C[i-1]:
        S.append(C[i])

L=len(S)

if L==1:
    print(1)
    sys.exit()

AL=[[] for i in range(N+1)]

for i in range(L):
    AL[S[i]].append(i)

PLUS=[0]*(N+1)

NOW=1

for i in range(L):
    NOW,PLUS[S[i]]=(NOW+PLUS[S[i]])%mod,(PLUS[S[i]]+NOW)%mod
    #PLUS[S[i]]+=NOW
    

    #print(NOW,PLUS)

#print(PLUS)
print(NOW)
    
    


Fixed submission:
import sys

N=int(input())
C=[int(input()) for i in range(N)]
mod=10**9+7

if N==1:
    print(1)
    sys.exit()

S=[C[0]]

for i in range(1,N):
    if C[i]!=C[i-1]:
        S.append(C[i])

L=len(S)

if L==1:
    print(1)
    sys.exit()

AL=[[] for i in range(2*10**5+1)]

for i in range(L):
    AL[S[i]].append(i)

PLUS=[0]*(2*10**5+1)

NOW=1

for i in range(L):
    NOW,PLUS[S[i]]=(NOW+PLUS[S[i]])%mod,(PLUS[S[i]]+NOW)%mod
    #PLUS[S[i]]+=NOW
    

    #print(NOW,PLUS)

#print(PLUS)
print(NOW)

Buggy python submission (verdict: Runtime Error):
N=int(input())
C=[int(input()) for i in range(N)]
mod=10**9+7

S=[C[0]]

for i in range(1,N):
    if C[i]!=C[i-1]:
        S.append(C[i])

L=len(S)

AL=[[] for i in range(N+1)]

for i in range(L):
    AL[S[i]].append(i)

PLUS=[0]*(N+1)

NOW=1

for i in range(L):
    NOW,PLUS[S[i]]=(NOW+PLUS[S[i]])%mod,(PLUS[S[i]]+NOW)%mod
    #PLUS[S[i]]+=NOW
    

    #print(NOW,PLUS)

#print(PLUS)
print(NOW)

Fixed submission:
import sys

N=int(input())
C=[int(input()) for i in range(N)]
mod=10**9+7

if N==1:
    print(1)
    sys.exit()

S=[C[0]]

for i in range(1,N):
    if C[i]!=C[i-1]:
        S.append(C[i])

L=len(S)

if L==1:
    print(1)
    sys.exit()

AL=[[] for i in range(2*10**5+1)]

for i in range(L):
    AL[S[i]].append(i)

PLUS=[0]*(2*10**5+1)

NOW=1

for i in range(L):
    NOW,PLUS[S[i]]=(NOW+PLUS[S[i]])%mod,(PLUS[S[i]]+NOW)%mod
    #PLUS[S[i]]+=NOW
    

    #print(NOW,PLUS)

#print(PLUS)
print(NOW)
Buggy python submission (verdict: Runtime Error):
import itertools

N,A,B,C=map(int,input().split())
L=[int(input()) for i in range(N)]

def score(x,NOW):
    L=len(NOW)
    ITE=list(itertools.product([0,1],repeat=L))

    ANS=10**15
    CANDI=[]

    for ite in ITE:
        if max(ite)==0:
            continue
        SUM=sum([NOW[i] for i in range(L) if ite[i]==1])        
        MAGIC=(ite.count(1)-1)*10
        

        if ANS>MAGIC+abs(x-SUM):
            ANS=MAGIC+abs(x-SUM)
            CANDI=ite

    return ANS,[NOW[i] for i in range(L) if CANDI[i]==0]

X=[[A,B,C],[A,C,B],[B,A,C],[B,C,A],[C,A,B],[C,B,A]]
ANS=10**15

for x in X:
    ANS1,L1=score(x[0],L)
    ANS2,L2=score(x[1],L1)
    ANS3,L3=score(x[2],L2)

    #print(ANS,ANS1,ANS2,ANS3,L1,L2,L3,A,B,C)

    if ANS>ANS1+ANS2+ANS3:
        ANS=ANS1+ANS2+ANS3

print(ANS)

Fixed submission:
import itertools

N,A,B,C=map(int,input().split())
L=[int(input()) for i in range(N)]

def score(x,NOW):
    L=len(NOW)
    ITE=list(itertools.product([0,1],repeat=L))

    ANS=10**15
    CANDI=[]

    for ite in ITE:
        if max(ite)==0:
            continue
        SUM=sum([NOW[i] for i in range(L) if ite[i]==1])        
        MAGIC=(ite.count(1)-1)*10
        

        if ANS>MAGIC+abs(x-SUM):
            ANS=MAGIC+abs(x-SUM)
            CANDI=ite

    return ANS,[NOW[i] for i in range(L) if CANDI[i]==0]

X=[[A,B,C],[A,C,B],[B,A,C],[B,C,A],[C,A,B],[C,B,A]]
ANS=10**15

for x in X:
    ANS1,L1=score(x[0],L)
    if len(L1)==0:
        continue
    ANS2,L2=score(x[1],L1)
    if len(L2)==0:
        continue
    ANS3,L3=score(x[2],L2)

    #print(ANS,ANS1,ANS2,ANS3,L1,L2,L3,A,B,C)

    if ANS>ANS1+ANS2+ANS3:
        ANS=ANS1+ANS2+ANS3

print(ANS)
Buggy python submission (verdict: Runtime Error):
S=input()
N=len(S)
mod= 998244353

FACT=[1]
for i in range(1,2*10**5+1):
    FACT.append(FACT[-1]*i%mod)

FACT_INV=[pow(FACT[-1],mod-2,mod)]
for i in range(2*10**5,0,-1):
    FACT_INV.append(FACT_INV[-1]*i%mod)

FACT_INV.reverse()

def Combi(a,b):
    if 0<=b<=a:
        return FACT[a]*FACT_INV[b]*FACT_INV[a-b]%mod
    else:
        return 0

R=0
B=0

RB=[[0,0]]*N

for i in range(N):
    s=S[i]
    if s=="0":
        R+=2
    elif s=="1":
        R+=1
        B+=1
    else:
        B+=2
    RB[i]=[R,B]

DP=[0]*(R+1)
DP[0]=1

for i in range(N):
    NDP=[0]*(R+1)
    red,blue=RB[i]
    for r in range(R+1):
        if DP[r]==0:
            continue
        if r+1<=red:
            NDP[r+1]+=DP[r]
        if i-r+1<=blue:
            NDP[r]+=DP[r]
    DP=NDP


ANS=0
for r in range(N+1):
    red=RB[-1][0]-r
    blue=RB[-1][1]-(N-r)

    ANS=ANS+DP[r]*Combi(red+blue,blue)
    ANS%=mod
print(ANS)

Fixed submission:
S=input()
N=len(S)
mod= 998244353

FACT=[1]
for i in range(1,2*10**5+1):
    FACT.append(FACT[-1]*i%mod)

FACT_INV=[pow(FACT[-1],mod-2,mod)]
for i in range(2*10**5,0,-1):
    FACT_INV.append(FACT_INV[-1]*i%mod)

FACT_INV.reverse()

def Combi(a,b):
    if 0<=b<=a:
        return FACT[a]*FACT_INV[b]*FACT_INV[a-b]%mod
    else:
        return 0

R=0
B=0

RB=[[0,0]]*N

for i in range(N):
    s=S[i]
    if s=="0":
        R+=2
    elif s=="1":
        R+=1
        B+=1
    else:
        B+=2
    RB[i]=[R,B]

DP=[0]*(R+1)
DP[0]=1

for i in range(N):
    NDP=[0]*(R+1)
    red,blue=RB[i]
    for r in range(R+1):
        if DP[r]==0:
            continue
        if r+1<=red:
            NDP[r+1]+=DP[r]
        if i-r+1<=blue:
            NDP[r]+=DP[r]
    DP=NDP


ANS=0
for r in range(R+1):
    red=R-r
    blue=B-(N-r)

    ANS=ANS+DP[r]*Combi(red+blue,blue)
    ANS%=mod
print(ANS)
Buggy python submission (verdict: Time Limit Exceeded):
N,K=map(int,input().split())
A=list(map(int,input().split()))

#DP[keta][limit]で考える

def ANS(keta,limit):
    
    if keta==-1:
        return 0

    A1=0
    A0=0
    for a in A:
        if a & (1<<keta)==0:
            A1+=1<<keta
        else:
            A0+=1<<keta
    
    if limit==1:               
        return max(A0,A1)+ANS(keta-1,1)

    if limit==0:
        if K & (1<<keta)==0:
            return A0+ANS(keta-1,0)
        else:
            return max(A0+ANS(keta-1,1),A1+ANS(keta-1,0))

print(ANS(50,0))

Fixed submission:
N,K=map(int,input().split())
A=list(map(int,input().split()))

for i in range(50):
    if K<(1<<i):
        break

keta=i

NOW=1
ANS=0

for i in range(keta-1,-1,-1):
    #print(i)
    if NOW==1 and K & (1<<i)!=0:
        #print("")
        A0=0
        A1=0
        for a in A:
            if a & (1<<i) ==0:
                A1+=(1<<i)
            else:
                A0+=(1<<i)

        if A1>A0:
            ANS+=(1<<i)
        else:
            ANS+=0
            NOW=0

    elif NOW==1 and K&(1<<i)==0:
        A0=0
        for a in A:
            if a & (1<<i) !=0:
                A0+=(1<<i)

        ANS+=0

    elif NOW==0:
        A0=0
        A1=0
        for a in A:
            if a & (1<<i) ==0:
                A1+=(1<<i)
            else:
                A0+=(1<<i)

        if A1>A0:
            ANS+=(1<<i)
        else:
            ANS+=0

#print(ANS)
SUM=0
for a in A:
    SUM+=ANS^a

print(SUM)
Buggy python submission (verdict: Runtime Error):
N,K=map(int,input().split())
TD=[list(map(int,input().split())) for i in range(N)]
TD.sort(key=lambda x:x[1],reverse=True)

ANS=0

check=[0]*(10**5)
NOCHANGE=[]
NETA=[]

for i in range(K):
    ANS+=TD[i][1]
    NETA.append(TD[i][0])


for i in range(N):
    if check[TD[i][0]]==0:
        NOCHANGE.append(i)
        check[TD[i][0]]=1

NOCHANGE=set(NOCHANGE)
NETA=len(set(NETA))



NOWLIST=set(list(range(K)))
NOWLIST=sorted(list(NOWLIST-NOCHANGE))



NOCHANGE=sorted(list(NOCHANGE))
NOCHANSET=set(NOCHANGE)
ANS+=NETA**2

#print(NOCHANGE)
#print(NOWLIST)
#print(ANS)
#print(NETA)

for j in range(len(NOCHANGE)):
    if NOCHANGE[j]>K-1:
        break

#print(j)
i=K-1
L=len(NOCHANGE)
SCORE=ANS
while j<L:
    while i in NOCHANSET:
        i-=1

    if i<0:
        break


    SCORE+=TD[NOCHANGE[j]][1]-TD[i][1]-NETA**2+(NETA+1)**2
    if SCORE>ANS:
        ANS=SCORE
    #print(i,j,NETA,SCORE)
    NETA+=1
    j+=1
    i-=1


    #print(i,j)

print(ANS)

    
    



Fixed submission:
N,K=map(int,input().split())
TD=[list(map(int,input().split())) for i in range(N)]
TD.sort(key=lambda x:x[1],reverse=True)

ANS=0

check=[0]*(10**5+1)
NOCHANGE=[]
NETA=[]

for i in range(K):
    ANS+=TD[i][1]
    NETA.append(TD[i][0])


for i in range(N):
    if check[TD[i][0]]==0:
        NOCHANGE.append(i)
        check[TD[i][0]]=1

NOCHANSET=set(NOCHANGE)
NETA=len(set(NETA))



#NOWLIST=set(list(range(K)))
#NOWLIST=sorted(list(NOWLIST-NOCHANSET))



NOCHANGE=sorted(list(NOCHANSET))

ANS+=NETA**2

#print(NOCHANGE)
#print(NOWLIST)
#print(ANS)
#print(NETA)

L=len(NOCHANGE)

for j in range(L):
    if NOCHANGE[j]>K-1:
        break
else:
    j=L
#print(j)
i=K-1

SCORE=ANS
#print(SCORE)
while j<L:
    while i in NOCHANSET:
        i-=1

    if i<0:
        break


    SCORE+=TD[NOCHANGE[j]][1]-TD[i][1]-NETA**2+(NETA+1)**2
    if SCORE>ANS:
        ANS=SCORE
    #print(i,j,NETA,SCORE)
    NETA+=1
    j+=1
    i-=1

    #print(SCORE)


    #print(i,j)

print(ANS)
Buggy python submission (verdict: Time Limit Exceeded):
N,K=map(int,input().split())
H=list(map(int,input().split()))

DPLIST=[float("inf")]*N
DPLIST[0]=0

for i in range(N-1):
    for j in range(1,K+1):
        if i+j<N:
            DPLIST[i+j]=min(DPLIST[i+j],DPLIST[i]+abs(H[i+j]-H[i]))

print(DPLIST[N-1])

Fixed submission:
N,K=map(int,input().split())
H=list(map(int,input().split()))

DPLIST=[float("inf")]*N
DPLIST[0]=0

for i in range(N-1):
    for j in range(1,K+1):
        if i+j<N:
            DPLIST[i+j]=min(DPLIST[i+j],DPLIST[i]+abs(H[i+j]-H[i]))

print(DPLIST[N-1])
Buggy python submission (verdict: Time Limit Exceeded):
N,W=map(int,input().split())
WV=[list(map(int,input().split())) for i in range(N)]

DP_W=[0]*(W+1)

for i in range(N):
    for j in range(W,-1,-1):
        if j+WV[i][0]<=W:
            DP_W[j+WV[i][0]]=max(DP_W[j+WV[i][0]],DP_W[j]+WV[i][1])

print(max(DP_W))

Fixed submission:
N,W=map(int,input().split())
WV=[list(map(int,input().split())) for i in range(N)]

DP_W=[0]*(W+1)

for i in range(N):
    for j in range(W,-1,-1):
        if j+WV[i][0]<=W:
            DP_W[j+WV[i][0]]=max(DP_W[j+WV[i][0]],DP_W[j]+WV[i][1])

print(max(DP_W))
Buggy python submission (verdict: Time Limit Exceeded):
s=input()
t=input()

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

DP=[[0 for j in range(len_t+1)] for i 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-1][j],DP[i][j-1])
            
        
x,y=len_s,len_t
ANS=""

while x>0 and y>0:
    if x>0 and DP[x-1][y]==DP[x][y]:
        x-=1
    elif y>0 and DP[x][y-1]==DP[x][y]:
        y-=1
    else:
        ANS+=s[x-1]
        x-=1
        y-=1

print(ANS[::-1])

Fixed submission:
s=input()
t=input()

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

DP=[[0 for j in range(len_t+1)] for i 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-1][j],DP[i][j-1])
            
        
x,y=len_s,len_t
ANS=""

while x>0 and y>0:
    if x>0 and DP[x-1][y]==DP[x][y]:
        x-=1
    elif y>0 and DP[x][y-1]==DP[x][y]:
        y-=1
    else:
        ANS+=s[x-1]
        x-=1
        y-=1

print(ANS[::-1])
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
P=list(map(float,input().split()))

NOW=[1]

for i in range(N):
    NEXT=[0]*(i+2)

    for j in range(i+1):
        NEXT[j]+=NOW[j]*(1-P[i])
        NEXT[j+1]+=NOW[j]*P[i]

    NOW=NEXT
    #print(NOW)

print(sum(NOW[1+N//2:]))

Fixed submission:
N=int(input())
P=list(map(float,input().split()))

NOW=[1]

for i in range(N):
    NEXT=[0]*(i+2)

    for j in range(i+1):
        NEXT[j]+=NOW[j]*(1-P[i])
        NEXT[j+1]+=NOW[j]*P[i]

    NOW=NEXT
    #print(NOW)

print(sum(NOW[1+N//2:]))
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
A=list(map(int,input().split()))

DPLIST=[[None]*N for i in range(N)]

SUM=[0]
for i in range(N):
    DPLIST[i][i]=0
    SUM.append(SUM[-1]+A[i])

for i in range(1,N):
    for j in range(i,N):

        ANS=float("inf")

        for k in range(j-i,j):

            if ANS>DPLIST[j-i][k]+DPLIST[k+1][j]+SUM[j+1]-SUM[j-i]:
                ANS=DPLIST[j-i][k]+DPLIST[k+1][j]+SUM[j+1]-SUM[j-i]
        
        DPLIST[j-i][j]=ANS

print(DPLIST[0][N-1])

Fixed submission:
N=int(input())
A=list(map(int,input().split()))

DPLIST=[[None]*N for i in range(N)]

for i in range(N):
    DPLIST[i][i]=[0,A[i]]

for i in range(1,N):
    for j in range(i,N):
        #print(i,j)
        ANS=float("inf")
        slime=float("inf")

        for k in range(j-i,j):
            sc1,sl1=DPLIST[j-i][k]
            sc2,sl2=DPLIST[k+1][j]

            if ANS>sc1+sc2+sl1+sl2:
                ANS=sc1+sc2+sl1+sl2
                slime=sl1+sl2
        
        DPLIST[j-i][j]=[ANS,slime]

    #print(DPLIST)
    #print()
            

print(DPLIST[0][N-1][0])

Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
A=list(map(int,input().split()))

DPLIST=[[None]*N for i in range(N)]

for i in range(N):
    DPLIST[i][i]=[0,A[i]]

for i in range(1,N):
    for j in range(i,N):
        #print(i,j)
        ANS=float("inf")
        slime=float("inf")

        for k in range(j-i,j):
            sc1,sl1=DPLIST[j-i][k]
            sc2,sl2=DPLIST[k+1][j]

            if ANS>sc1+sc2+sl1+sl2:
                ANS=sc1+sc2+sl1+sl2
                slime=sl1+sl2
        
        DPLIST[j-i][j]=[ANS,slime]

    #print(DPLIST)
    #print()
            

print(DPLIST[0][N-1][0])

Fixed submission:
N=int(input())
A=list(map(int,input().split()))

DPLIST=[[None]*N for i in range(N)]

for i in range(N):
    DPLIST[i][i]=[0,A[i]]

for i in range(1,N):
    for j in range(i,N):
        #print(i,j)
        ANS=float("inf")
        slime=float("inf")

        for k in range(j-i,j):
            sc1,sl1=DPLIST[j-i][k]
            sc2,sl2=DPLIST[k+1][j]

            if ANS>sc1+sc2+sl1+sl2:
                ANS=sc1+sc2+sl1+sl2
                slime=sl1+sl2
        
        DPLIST[j-i][j]=[ANS,slime]

    #print(DPLIST)
    #print()
            

print(DPLIST[0][N-1][0])
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

N=int(input())
H=list(map(int,input().split()))
A=list(map(int,input().split()))


#Segment tree（区間の最大値を求めるバージョン）
for i in range(30):#要素数以上の2のベキを見つける
    if N<=2**i:
        seg_el=2**i#Segment treeの台の要素数
        break

SEG=[0]*(2*seg_el-1)#Segment treeを一次元リストとして作る

def update(n,x,seg_el):#A[n]=xに更新（反映）
    i=n+seg_el-1
    while i>=0:
        SEG[i]=max(x,SEG[i])
        i=(i-1)//2

def getvalues(a,b,k,l,r):#区間[a,b)での,SEG[k],つまり区間[l,r)に関する最大値を調べる
    if r<=a or b<=l:#区間[a,b)が対象区間の外にあれば,infを出力
        return -float("inf")
    if a<=l and r<=b:#区間[a,b)が対象区間の中にあればSEG[k]を出力
        return SEG[k]
    vl=getvalues(a,b,k*2+1,l,(l+r)//2)#それ以外のときは,SEG[k*2+1]とSEG[k*2+2]で場合分け（木の子ノード二つを見る）
    vr=getvalues(a,b,k*2+2,(l+r)//2,r)
    return max(vl,vr)

for i in range(N):
    h,a=H[i],A[i]
    x=getvalues(0,h,0,0,seg_el)
    update(h-1,x+a,seg_el)

print(getvalues(0,N,0,0,seg_el))


Fixed submission:
import sys
input = sys.stdin.readline

N=int(input())
H=list(map(int,input().split()))
A=list(map(int,input().split()))


#Segment tree（区間の最大値を求めるバージョン）
for i in range(30):#要素数以上の2のベキを見つける
    if N<=2**i:
        seg_el=2**i#Segment treeの台の要素数
        break

SEG=[0]*(2*seg_el-1)#Segment treeを一次元リストとして作る

def update(n,x,seg_el):#A[n]=xに更新（反映）
    i=n+seg_el-1
    while i>=0:
        SEG[i]=max(x,SEG[i])
        i=(i-1)//2

def getvalues(a,b,k,l,r):#区間[a,b)での,SEG[k],つまり区間[l,r)に関する最大値を調べる
    if r<=a or b<=l:#区間[a,b)が対象区間の外にあれば,infを出力
        return -float("inf")
    if a<=l and r<=b:#区間[a,b)が対象区間の中にあればSEG[k]を出力
        return SEG[k]
    vl=getvalues(a,b,k*2+1,l,(l+r)//2)#それ以外のときは,SEG[k*2+1]とSEG[k*2+2]で場合分け（木の子ノード二つを見る）
    vr=getvalues(a,b,k*2+2,(l+r)//2,r)
    return max(vl,vr)

for i in range(N):
    h,a=H[i],A[i]
    x=getvalues(0,h,0,0,seg_el)
    update(h-1,x+a,seg_el)

print(getvalues(0,N,0,0,seg_el))