Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
def resolve():
    n=int(input())
    C=sorted([complex(*map(int,input().split())) for _ in range(n)],key=cmath.phase)
    total = sum(C)
    score = 0
    ans = 0
    r=0

    for l in range(n):
        while(r<n and abs(score)<abs(score+C[r])):
            score+=C[r]
            r+=1
        ans=max(ans,abs(score),abs(total-score))
        if r==l:r+=1
        else: score-=C[l]

    print(ans)
resolve()

Fixed submission:
import cmath
import itertools
# cmath.phase:C to (-pi,pi]
n = int(input())
C = sorted([complex(*map(int,input().split())) for _ in range(n)], key=cmath.phase)
score = 0
for i,j in itertools.product(range(n),range(n)):
    if i>j: continue # i+1<=j<=nでループ回すのをサボった
    score = max(score,abs(sum(C[:i]+C[j:])))
    score = max(score,abs(sum(C[i:j])))
print(score)

Buggy python submission (verdict: Runtime Error):
import cmath
import itertools
n = int(input())
C = sorted([complex(*map(int,input().split())) for _ in range(n)], key=cmath.phase)
score = 0
for i,j in itertools.product(range(n),range(n)):
    if i>j: continue
    score = max((score,abs(sum(C[:i]+C[j:])),abs(sum[i:j])))
print(score)

Fixed submission:
import cmath
import itertools
# cmath.phase:C to (-pi,pi]
n = int(input())
C = sorted([complex(*map(int,input().split())) for _ in range(n)], key=cmath.phase)
score = 0
for i,j in itertools.product(range(n),range(n)):
    if i>j: continue # i+1<=j<=nでループ回すのをサボった
    score = max(score,abs(sum(C[:i]+C[j:])))
    score = max(score,abs(sum(C[i:j])))
print(score)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
class mint(object):
    MOD=998244353

    def __init__(self,x):
        self.__x=x%self.MOD

    def __repr__(self):
        return str(self.__x)

    def __add__(self,other):
        return mint(self.__x+other.__x) if isinstance(other,mint) else mint(self.__x+other)

    def __sub__(self,other):
        return mint(self.__x-other.__x) if isinstance(other,mint) else mint(self.__x-other)

    def __mul__(self,other):
        return mint(self.__x*other.__x) if isinstance(other,mint) else mint(self.__x*other)

    def __truediv__(self,other):
        return mint(self.__x*pow(other.__x,self.MOD-2,self.MOD)) if isinstance(other, mint) else mint(self.__x*pow(other, self.MOD-2,self.MOD))

    def __pow__(self,other):
        return mint(pow(self.__x,other.__x,self.MOD)) if isinstance(other,mint) else mint(pow(self.__x,other,self.MOD))

    __radd__=__add__

    def __rsub__(self,other):
        return mint(other.__x-self.__x) if isinstance(other,mint) else mint(other-self.__x)

    __rmul__=__mul__

    def __rtruediv__(self,other):
        return mint(other.__x*pow(self.__x,self.MOD-2,self.MOD)) if isinstance(other,mint) else mint(other*pow(self.__x,self.MOD-2,self.MOD))

    def __rpow__(self,other):
        return mint(pow(other.__x,self.__x,self.MOD)) if isinstance(other,mint) else mint(pow(other,self.__x,self.MOD))

def resolve():
    # preparation
    p=int(input())
    mint.MOD=p
    invfact=[0]*p
    invfact[p-1]=mint(-1) # Wilson's theorem
    for i in range(2,p):
        invfact[p-i]=invfact[p-i+1]*(p-i+1)

    # initialize
    A=[0]*p
    for i,a in enumerate(map(int,input().split())):
        A[i]=mint(a)

    ans=[mint(0)]*p
    ans[0]=A[0]
    r=[mint(0)]*(p+1) # for use of r[-1]=0
    r[0]=mint(1)

    # iterate
    for k in range(1,p):
        newr=[0]*(p+1) # newr(x)=(x-(k-1))r(x)
        v=0 # v=f[k-1](k)
        power=1
        for i in range(p):
            v+=ans[i]*power
            power*=k
            newr[i]=r[i-1]-(k-1)*r[i]
        r=newr
        for i in range(p):
            ans[i]+=(A[k]-v)*invfact[k]*r[i]

    print(*ans)
resolve()

Fixed submission:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    # preparation
    p=int(input())
    invfact=[0]*p
    invfact[p-1]=p-1 # Wilson's theorem
    for i in range(2,p):
        invfact[p-i]=invfact[p-i+1]*(p-i+1)%p

    # initialize
    A=list(map(int,input().split()))
    ans=[0]*p
    ans[0]=A[0]
    r=[0]*(p+1) # for use of r[-1]=0
    r[0]=1

    # iterate
    for k in range(1,p):
        newr=[0]*(p+1) # newr(x)=(x-(k-1))r(x)
        v=0 # v=f[k-1](k)
        power=1
        for i in range(p):
            v+=ans[i]*power%p
            power*=k
            power%=p
            newr[i]=(r[i-1]-(k-1)*r[i])%p
        r=newr
        for i in range(p):
            ans[i]+=(A[k]-v)*invfact[k]*r[i]
            ans[i]%=p
    print(*ans)
resolve()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    from itertools import groupby
    s=input()
    G=groupby(s)
    A=[]
    for i,g in enumerate(G):
        key,iter=g
        if(i%2==0): a=len(list(iter))
        else: A.append((a,len(list(iter))))
    ans=[]
    for x,y in A:
        ans=ans+[0]*(x-1)
        ans.append((x-x//2)+(y//2))
        ans.append((x//2)+(y-y//2))
        ans=ans+[0]*(y-1)
    print(*ans)
resolve()

Fixed submission:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    from itertools import groupby
    s=input()
    n=len(s)
    G=groupby(s)
    A=[]
    for i,g in enumerate(G):
        key,iter=g
        if(i%2==0): a=len(list(iter))
        else: A.append((a,len(list(iter))))
    ans=[0]*n
    idx=-1
    for x,y in A:
        idx+=x
        ans[idx]=x-x//2+y//2
        ans[idx+1]=x//2+y-y//2
        idx+=y
    print(*ans)
resolve()
Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,K=map(int,input().split())
    dp=[[[0]*2600 for _ in range(55)] for _ in range(55)]
    dp[0][0][0]=1
    for i in range(n):
        for j in range(n):
            for k in range(K+1):
                dp[i+1][j][k+2*j]+=(2*j+1)*dp[i][j][k]
                dp[i+1][j][k+2*j]%=MOD
                dp[i+1][j+1][k+2*(j+1)]+=dp[i][j][k]
                dp[i+1][j+1][k+2*(j+1)]%=MOD
                if(j>0):
                    dp[i+1][j-1][k+2*(j-1)]+=j*j*dp[i][j][k]
                    dp[i+1][j-1][k+2*(j-1)]%=MOD
    print(dp[n][0][K])
resolve()

Fixed submission:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,K=map(int,input().split())
    dp=[[[0]*2700 for _ in range(55)] for _ in range(55)]
    dp[0][0][0]=1
    for i in range(n):
        for j in range(i+1):
            for k in range(K+1):
                dp[i+1][j][k+2*j]+=(2*j+1)*dp[i][j][k]
                dp[i+1][j][k+2*j]%=MOD
                dp[i+1][j+1][k+2*(j+1)]+=dp[i][j][k]
                dp[i+1][j+1][k+2*(j+1)]%=MOD
                if(j):
                    dp[i+1][j-1][k+2*(j-1)]+=j*j*dp[i][j][k]
                    dp[i+1][j-1][k+2*(j-1)]%=MOD
    print(dp[n][0][K])
resolve()

Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,K=map(int,input().split())
    dp=[[[0]*2600 for _ in range(55)] for _ in range(55)]
    dp[0][0][0]=1
    for i in range(n):
        for j in range(n):
            for k in range(K+1):
                dp[i+1][j][k+2*j]+=(2*j+1)*dp[i][j][k]
                dp[i+1][j][k+2*j]%=MOD
                dp[i+1][j+1][k+2*(j+1)]+=dp[i][j][k]
                dp[i+1][j+1][k+2*(j+1)]%=MOD
                dp[i+1][j-1][k+2*(j-1)]+=j*j*dp[i][j][k]
                dp[i+1][j-1][k+2*(j-1)]%=MOD
    print(dp[n][0][K])
resolve()

Fixed submission:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,K=map(int,input().split())
    dp=[[[0]*2700 for _ in range(55)] for _ in range(55)]
    dp[0][0][0]=1
    for i in range(n):
        for j in range(i+1):
            for k in range(K+1):
                dp[i+1][j][k+2*j]+=(2*j+1)*dp[i][j][k]
                dp[i+1][j][k+2*j]%=MOD
                dp[i+1][j+1][k+2*(j+1)]+=dp[i][j][k]
                dp[i+1][j+1][k+2*(j+1)]%=MOD
                if(j):
                    dp[i+1][j-1][k+2*(j-1)]+=j*j*dp[i][j][k]
                    dp[i+1][j-1][k+2*(j-1)]%=MOD
    print(dp[n][0][K])
resolve()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,k=map(int,input().split())
    E=[[] for _ in range(n)]
    for _ in range(n-1):
        a,b=map(int,input().split())
        a-=1; b-=1;
        E[a].append(b)
        E[b].append(a)

    dp=[1]*n
    dp[0]=k
    def dfs(v,p)->None:
        if(p!=-1):
            count=0
            for nv in E[v]:
                if(nv==p): continue
                dp[nv]=k-2-count
                count+=1
                dfs(nv,v)
        else:
            count=0
            for nv in E[v]:
                dp[nv]=k-1-count
                count+=1
                dfs(nv,v)

    dfs(0,-1)
    ans=1
    for i in range(n):
        ans*=dp[i]
        ans%=MOD
    print(ans)
resolve()

Fixed submission:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,k=map(int,input().split())
    E=[[] for _ in range(n)]
    for _ in range(n-1):
        a,b=map(int,input().split())
        a-=1; b-=1;
        E[a].append(b)
        E[b].append(a)

    dp=[1]*n
    dp[0]=k
    def dfs(v,p)->None:
        if(p!=-1):
            count=0
            for nv in E[v]:
                if(nv==p): continue
                dp[nv]=k-2-count
                count+=1
                dfs(nv,v)
        else:
            count=0
            for nv in E[v]:
                dp[nv]=k-1-count
                count+=1
                dfs(nv,v)

    dfs(0,-1)
    ans=1
    for i in range(n):
        ans*=dp[i]
        ans%=MOD
    print(ans)
resolve()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    V=100005
    n=int(input())
    E=[[] for _ in range(V*2)]
    for _ in range(n):
        x,y=map(int,input().split())
        y+=V
        E[x].append(y)
        E[y].append(x)

    visited=[0]*(2*V)
    def dfs(v):
        if(visited[v]): return
        visited[v]=1
        cnt[v//V]+=1
        for nv in E[v]: dfs(nv)

    ans=[0]
    for v in range(2*V):
        if(visited[v]): continue
        cnt=[0]*2 # 連結成分のx,yの個数
        dfs(v)
        ans[0]+=cnt[0]*cnt[1]
    print(ans[0]-n)
resolve()

Fixed submission:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    V=100005
    n=int(input())
    E=[[] for _ in range(V*2)]
    for _ in range(n):
        x,y=map(int,input().split())
        y+=V
        E[x].append(y)
        E[y].append(x)

    visited=[0]*(2*V)
    def dfs(v):
        if(visited[v]): return
        visited[v]=1
        cnt[v//V]+=1
        for nv in E[v]: dfs(nv)

    ans=[0]
    for v in range(2*V):
        if(visited[v]): continue
        cnt=[0]*2 # 連結成分のx,yの個数
        dfs(v)
        ans[0]+=cnt[0]*cnt[1]
    print(ans[0]-n)
resolve()
Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,m=map(int,input().split())
    L=-INF; R=INF
    for _ in range(m):
        l,r=map(int,input().split())
        L=max(L,l)
        R=min(R,r)
    print(max(R-L+1),0)
resolve()

Fixed submission:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,m=map(int,input().split())
    L=-INF; R=INF
    for _ in range(m):
        l,r=map(int,input().split())
        L=max(L,l)
        R=min(R,r)
    print(max(R-L+1,0))
resolve()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,m=map(int,input().split())
    E=[[] for _ in range(n)]
    for _ in range(m):
        x,y,z=map(int,input().split())
        x-=1; y-=1
        E[x].append(y)
        E[y].append(x)

    visited=[0]*n
    def dfs(v,p)->bool:
        if(visited[v]):
            return False
        visited[v]=1
        for nv in E[v]:
            if(nv==p): continue
            dfs(nv,v)
        return True

    ans=0
    for v in range(n):
        ans+=dfs(v,-1)
    print(ans)
resolve()

Fixed submission:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
class UnionFind(object):
    def __init__(self,n):
        self.__par=list(range(n))
        self.__rank=[0]*n
        self.__size=[1]*n

    def root(self,k):
        if(self.__par[k]==k): return k
        self.__par[k]=self.root(self.__par[k])
        return self.__par[k]

    def unite(self,i,j):
        i=self.root(i); j=self.root(j)
        par=self.__par; rank=self.__rank; size=self.__size
        if(i==j): return False
        if(rank[i]>rank[j]):
            par[j]=i
            size[i]+=size[j]
        else:
            par[i]=j
            size[j]+=size[i]
            if(rank[i]==rank[j]): rank[j]+=1
        return True

    def size(self,k):
        return self.__size[self.root(k)]

def resolve():
    n,m=map(int,input().split())
    uf=UnionFind(n)
    for _ in range(m):
        x,y,z=map(int,input().split())
        x-=1; y-=1
        uf.unite(x,y)
    print(len({uf.root(i) for i in range(n)}))
resolve()
Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n=int(input())
    H=list(map(int,input().split()))
    M=[0]*n
    M[1]=H[0]
    for i in range(2,n):
        M[i]=max(M[i-1],H[i-1])
    print(sum(1 for i in range(n) if H[i]>=M[i]))
resolve()

Fixed submission:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n=int(input())
    if n==1:
        print(1)
        return
    H=list(map(int,input().split()))
    M=[0]*n
    M[1]=H[0]
    for i in range(2,n):
        M[i]=max(M[i-1],H[i-1])
    print(sum(1 for i in range(n) if H[i]>=M[i]))
resolve()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    x,y,z,k=map(int,input().split())
    A=list(map(int,input().split()))
    B=list(map(int,input().split()))
    C=list(map(int,input().split()))
    A.sort(reverse=1)
    B.sort(reverse=1)
    C.sort(reverse=1)
    A=A[:k]
    B=B[:k]
    C=C[:k]
    S=[]
    from itertools import product
    for i,j,l in product(range(k),repeat=3):
        if(i>=x or j>=y or l>=z): continue
        S.append(A[i]+B[j]+C[l])
    S.sort(reverse=1)
    for i in range(k):
        print(S[i])
resolve()

Fixed submission:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    x,y,z,k=map(int,input().split())
    A=list(map(int,input().split()))
    B=list(map(int,input().split()))
    C=list(map(int,input().split()))
    S=[]
    T=[]
    from itertools import product
    for a,b in product(A,B):
        S.append(a+b)
    S.sort(reverse=1)
    S=S[:k]
    for s,c in product(S,C):
        T.append(s+c)
    T.sort(reverse=1)
    for i in range(k):
        print(T[i])
resolve()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    x,y,z,k=map(int,input().split())
    A=list(map(int,input().split()))
    B=list(map(int,input().split()))
    C=list(map(int,input().split()))
    S=[]
    from itertools import product
    for a,b,c in product(A,B,C):
        S.append(a+b+c)
    S.sort(reverse=1)
    for i in range(k):
        print(S[i])
resolve()

Fixed submission:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    x,y,z,k=map(int,input().split())
    A=list(map(int,input().split()))
    B=list(map(int,input().split()))
    C=list(map(int,input().split()))
    S=[]
    T=[]
    from itertools import product
    for a,b in product(A,B):
        S.append(a+b)
    S.sort(reverse=1)
    S=S[:k]
    for s,c in product(S,C):
        T.append(s+c)
    T.sort(reverse=1)
    for i in range(k):
        print(T[i])
resolve()
Buggy python submission (verdict: Time Limit Exceeded):
N,Q = map(int,input().split())
S = input()

# 2文字の連続部分列はN-1個なので、N-1個のBooleanの配列を生成
b = [S[i]=='A' and S[i+1]=='C' for i in range(N-1)]

for _ in range(Q):
    l,r = map(int,input().split())
    # bのl番目からr-1番目までの和を出力
    print(sum(b[l-1:r-1]))

Fixed submission:
import itertools

N,Q = map(int,input().split())
S = input()

b = [S[i]=='A' and S[i+1]=='C' for i in range(N-1)]
b.insert(0,0)
b = list(itertools.accumulate(b))

for _ in range(Q):
    l,r = map(int,input().split())
    print(b[r-1]-b[l-1])

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

# 2文字の連続部分列はN-1個なので、N-1個のBooleanの配列を生成
b = [S[i:i+2]=="AC" for i in range(N-1)]

for _ in range(Q):
    l,r = map(int,input().split())
    # bのl番目からr-1番目までの和を出力
    print(sum(b[l-1:r-1]))

Fixed submission:
import itertools

N,Q = map(int,input().split())
S = input()

b = [S[i]=='A' and S[i+1]=='C' for i in range(N-1)]
b.insert(0,0)
b = list(itertools.accumulate(b))

for _ in range(Q):
    l,r = map(int,input().split())
    print(b[r-1]-b[l-1])

Buggy python submission (verdict: Time Limit Exceeded):
n,q = map(int,input().split())
s = input()
for i in range(q):
    count = 0
    l,r = map(int,input().split())
    print(s[l-1:r].count("AC"))

Fixed submission:
import itertools

N,Q = map(int,input().split())
S = input()

b = [S[i]=='A' and S[i+1]=='C' for i in range(N-1)]
b.insert(0,0)
b = list(itertools.accumulate(b))

for _ in range(Q):
    l,r = map(int,input().split())
    print(b[r-1]-b[l-1])
Buggy python submission (verdict: Time Limit Exceeded):
s = input()
n = len(s)
flag = True
while(flag):
    for i in range(len(s)-1):
        if s[i]!=s[i+1]:
            s = s[:i]+s[i+2:len(s)]
            break
    else:
        flag=False
print(n-len(s))

Fixed submission:
S = input()
stack = []
count = 0
for s in S:
    if (not stack) or stack[-1]==s:
        stack.append(s)
    else:
        stack.pop()
        count += 2
print(count)
Buggy python submission (verdict: Runtime Error):
from fractions import gcd
from functools import reduce
input()
print(reduce(gcd,map(input().split())))

Fixed submission:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=sys.stdin.readline
def resolve():
    n=int(input())
    A=map(int,input().split())
    from fractions import gcd
    from functools import reduce
    print(reduce(gcd,A))
resolve()
Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,w=map(int,input().split())
    W=[0]*(n+1); V=[0]*(n+1)
    for i in range(1,n+1):
        a,b=map(int,input().split())
        W[i]=a; V[i]=b
    # dp[i][c] iまでの品物で、重さがc以下
    dp=[[-1]*(w+1) for _ in range(n+1)]
    # メモ化再帰
    def solve(i,c):
        if(dp[i][c]!=-1): return dp[i][c]
        if(i==0):
            dp[i][c]=0
            return dp[i][c];
        if(c-W[i]>=0):
            dp[i][c]=max(solve(i-1,c-W[i])+V[i],solve(i-1,c))
            return dp[i][c]
        else:
            dp[i][c]=solve(i-1,c)
            return dp[i][c]
    print(solve(n,w))
resolve()

Fixed submission:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,W=map(int,input().split())
    w,v=[0]*n,[0]*n
    for i in range(n):
        w[i],v[i]=map(int,input().split())
    V=sum(v)
    dp=[INF]*(V+1)
    dp[0]=0
    for i in range(n):
        newdp=dp[:]
        for x in range(V+1):
            if(x+v[i]<V+1):
                newdp[x+v[i]]=min(newdp[x+v[i]],dp[x]+w[i])
        dp=newdp
    for i in range(V,-1,-1):
        if(dp[i]<=W):
            print(i)
            return
resolve()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 # 998244353
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    S = input()
    T = input()
    m = len(S)
    n = len(T)
    dp = [[-INF] * (n + 1) for _ in range(m + 1)]
    dp[0][0] = 0
    prev = [[None] * (n + 1) for _ in range(m + 1)]
    prev[0][0] = (-1, -1, '')

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

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

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

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

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

    for i in range(m):
        dp[i][0] = 0
    for j in range(n):
        dp[0][j] = 0

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

    i, j = m, n
    res = []
    cnt = 0
    while 1:
        pi, pj = prev[i][j]
        if (pi, pj) == (-1, -1):
            break
        if i - pi == 1 and j - pj == 1:
            res.append(S[pi])
        i, j = pi, pj

    print(''.join(reversed(res)))
resolve()