Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
import math, sys
sys.setrecursionlimit(100000000)
mod = 10**9+7
N, K = map(int, input().split())
edge = [[] for _ in range(N)]
flag = [False]*N
flag[0] = True
for i in range(N-1):
    a, b = map(int, input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
P = [1]*(K+10)
T = [1]*(K+10)
for i in range(1, K+10):
    P[i] = (P[i-1]*(K-i))%mod
    T[i] = T[i-1]*(K-i-1)%mod
def count(x):
    flag[x]=True
    res = 1
    l = len(edge[x])-1
        
    for e in edge[x]:
        if flag[e]:
            continue
        res*=count(e)
    if x==0:
        return res*K*P[l+1]%mod
    return res*T[l]%mod
print(count(0))


Fixed submission:
import sys
sys.setrecursionlimit(1000000000)
mod = 10**9+7
N, K = map(int, input().split())
edge = [[] for _ in range(N)]
flag = [False]*N
flag[0] = True
for i in range(N-1):
    a, b = map(int, input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
P = [1]*(K+10)
T = [1]*(K+10)
for i in range(1, K+10):
    P[i] = (P[i-1]*(K-i))%mod
    T[i] = T[i-1]*(K-i-1)%mod
def count(x):
    flag[x]=True
    res = 1
    l = len(edge[x])-1
        
    for e in edge[x]:
        if flag[e]:
            continue
        res*=count(e)
    if x==0:
        if l+1> K-1:
            return 0
        return res*K*P[l+1]%mod
    if l>K-2:
        return 0
    return res*T[l]%mod
print(count(0))

Buggy python submission (verdict: Runtime Error):
import math, sys
sys.setrecursionlimit(1000000)
mod = 10**9+7
N, K = map(int, input().split())
edge = [[] for _ in range(N)]
flag = [False]*N
flag[0] = True
for i in range(N-1):
    a, b = map(int, input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
P = [1]*(K+1)
T = [1]*(K+1)
for i in range(1, K+1):
    P[i] = (P[i-1]*(K-i))%mod
    T[i] = T[i-1]*(K-i-1)%mod
def count(x):
    flag[x]=True
    res = 1
    l = len(edge[x])-1
        
    for e in edge[x]:
        if flag[e]:
            continue
        res*=count(e)
    if x==0:
        return res*K*P[l+1]%mod
    return res*T[l]%mod
print(count(0))


Fixed submission:
import sys
sys.setrecursionlimit(1000000000)
mod = 10**9+7
N, K = map(int, input().split())
edge = [[] for _ in range(N)]
flag = [False]*N
flag[0] = True
for i in range(N-1):
    a, b = map(int, input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
P = [1]*(K+10)
T = [1]*(K+10)
for i in range(1, K+10):
    P[i] = (P[i-1]*(K-i))%mod
    T[i] = T[i-1]*(K-i-1)%mod
def count(x):
    flag[x]=True
    res = 1
    l = len(edge[x])-1
        
    for e in edge[x]:
        if flag[e]:
            continue
        res*=count(e)
    if x==0:
        if l+1> K-1:
            return 0
        return res*K*P[l+1]%mod
    if l>K-2:
        return 0
    return res*T[l]%mod
print(count(0))
Buggy python submission (verdict: Runtime Error):
from collections import defaultdict, deque
N, M = map(int, input().split())
G = defaultdict(list)
for _ in range(M):
    u, v = map(int, input().split())
    G[(u-1, 0)].append((v-1, 1))
    G[(u-1, 1)].append((v-1, 2))
    G[(u-1, 2)].append((v-1, 0))
S, T = map(int, input().split())
G3 = defaultdict(list)
dist = defaultdict(lambda : -1)
que = deque([(S-1, 0)])
dist[(S-1, 0)] = 0
while que:
    if v == (T-1, 0):
        break
    v = que.pop()
    d = dist[v]
    for nv in G[v]:
        if dist[nv]>=0:
            continue
        dist[nv] = d+1
        que.append(nv)
print(dist[(T-1, 0)]//3)


Fixed submission:
from collections import defaultdict, deque
N, M = map(int, input().split())
G = defaultdict(list)
for _ in range(M):
    u, v = map(int, input().split())
    G[(u-1, 0)].append((v-1, 1))
    G[(u-1, 1)].append((v-1, 2))
    G[(u-1, 2)].append((v-1, 0))
S, T = map(int, input().split())
dist = defaultdict(lambda : -1)
que = deque([(S-1, 0)])
dist[(S-1, 0)] = 0
while que:
    v = que.popleft()
    d = dist[v]
    for nv in G[v]:
        if dist[nv]>=0:
            continue
        dist[nv] = d+1
        que.append(nv)
print(dist[(T-1, 0)]//3)
Buggy python submission (verdict: Runtime Error):
N, X = map(int, input().split())
L = list(map(int, input().split()))
cnt = 0
for i in range(N):
    cnt+=L[i]
    if cnt>X:
        ans = i+1
        break
print(ans)


Fixed submission:
N, X = map(int, input().split())
L = list(map(int, input().split()))
cnt = 0
ans = N+1
for i in range(N):
    cnt+=L[i]
    if cnt>X:
        ans = i+1
        break
print(ans)
Buggy python submission (verdict: Runtime Error):
mod = 10**9+7
N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
k = [0]*(N+1)
k[0]=1
cnt = 0
if a[0]!=1:
    k[1]=1
else:
    cnt+=1
for i in range(2, N+1):
    if cnt<M and i ==a[cnt]:
        cnt+=1
        continue
    else:
        k[i]=k[i-1]+k[i-2]
print(k[N]%mod)


Fixed submission:
def solve():
    mod = 10**9+7
    N, M = map(int, input().split())
    k = [0]*(N+1)
    if M==0:
        k[0]=1
        k[1]=1
        for i in range(2, N+1):
            k[i]=(k[i-1]+k[i-2])%mod
        print(k[N]%mod)
        return
    a = [int(input()) for _ in range(M)]
    k[0]=1
    cnt = 0
    if a[0]!=1:
        k[1]=1
    else:
        cnt+=1
    for i in range(2, N+1):
        if cnt<M and i ==a[cnt]:
            cnt+=1
            continue
        else:   
            k[i]=(k[i-1]+k[i-2])%mod
    print(k[N]%mod)
    return
solve()
Buggy python submission (verdict: Time Limit Exceeded):
def solve():
    mod = 10**9+7
    L = input()
    N = len(L)
    dp = [[0]*2 for _ in range(N)]
    dp[0][0] = 1
    dp[0][1] = 2
    for i in range(1, N):
        if L[i]=='0':
            dp[i][0]=dp[i-1][0]*3
            dp[i][1] = dp[i-1][1]
        else:
            dp[i][0]=dp[i-1][0]*3+dp[i-1][1]
            dp[i][1] = dp[i-1][1]*2
    print((dp[N-1][0]+dp[N-1][1])%mod)
solve()

Fixed submission:
def solve():
    mod = 10**9+7
    L = input()
    N = len(L)
    dp = [0]*2
    dp[0] = 1
    dp[1] = 2
    for i in range(1, N):
        if L[i]=='0':
            dp[0], dp[1]=dp[0]*3, dp[1]
        else:
            dp[0], dp[1]=dp[0]*3+dp[1], dp[1]*2
    print((dp[0]+dp[1])%mod)
solve()
Buggy python submission (verdict: Runtime Error):
import heapq
n=int(input())
ab = [list(map(int, input().split())) for _ in range(n-1)]
c=sorted(list(map(lambda x:-int(x), input().split())))
print(-sum(c[1:]))
heapq.heapify(c)
mat = [[] for _ in range(n+1)]
ans=[0]*n
for i in range(n-1):
    a, b = ab[i]
    mat[a].append(b)
    mat[b].append(a)
def dp(x, y):
    ans[y-1]=-heapq.heappop(c)
    if y>1 and len(mat[y])==1:
        return
    for i in mat[y]:
        if i!=x:
            dp(y, i)
dp(0, 1)
print(' '.join(map(str, ans)))

Fixed submission:
import heapq
import sys
sys.setrecursionlimit(10000000)
n=int(input())
ab = [list(map(int, input().split())) for _ in range(n-1)]
c=sorted(list(map(lambda x:-int(x), input().split())))
print(-sum(c[1:]))
heapq.heapify(c)
mat = [[] for _ in range(n+1)]
ans=[0]*n
for i in range(n-1):
    a, b = ab[i]
    mat[a].append(b)
    mat[b].append(a)
def dp(x, y):
    ans[y-1]=-heapq.heappop(c)
    if y>1 and len(mat[y])==1:
        return
    for i in mat[y]:
        if i!=x:
            dp(y, i)
dp(0, 1)
print(' '.join(map(str, ans)))
Buggy python submission (verdict: Runtime Error):
n, m = map(int, input().split())
a=sorted(list(map(int, input().split())), reverse = True)
bc = sorted([list(map(int, input().split())) for _ in range(m)], key = lambda x:x[1], reverse = True)
i=0
j=0
cnt=0
ans=0
while True:
    if a[i]<bc[j][1]:
        ans+=min(n-cnt, bc[j][0])*bc[j][1]
        cnt+=min(n-cnt, bc[j][0])
        j+=1
    else:
        ans+=a[i]
        i+=1
        cnt+=1
    if cnt==n:
        break
print(ans)
    

Fixed submission:
n, m = map(int, input().split())
a=sorted(list(map(int, input().split())), reverse = True)
bc = sorted([list(map(int, input().split())) for _ in range(m)], key = lambda x:x[1], reverse = True)
i=0
j=0
cnt=0
ans=0
while True:
    if j<m and a[i]<bc[j][1]:
        ans+=min(n-cnt, bc[j][0])*bc[j][1]
        cnt+=min(n-cnt, bc[j][0])
        j+=1
    else:
        ans+=a[i]
        i+=1
        cnt+=1
    if cnt==n:
        break
print(ans)

Buggy python submission (verdict: Runtime Error):
n, m = map(int, input().split())
a=sorted(list(map(int, input().split())))
bc = sorted([list(map(int, input().split())) for _ in range(m)], key = lambda x:x[1], reverse = True)
tmp=0
cnt=0
ans=0
for i in range(n):
    if cnt>=bc[tmp][0]:
        ans+=bc[tmp][1]*bc[tmp][0]
        cnt-=bc[tmp][0]
        tmp+=1
    if tmp==m:
        k=n
        break
    if a[i]>bc[tmp][1]:
        k=i
        ans+=bc[tmp][1]*(cnt)
        break
    cnt+=1
print(sum(a[k:])+ans)

Fixed submission:
n, m = map(int, input().split())
a=sorted(list(map(int, input().split())), reverse = True)
bc = sorted([list(map(int, input().split())) for _ in range(m)], key = lambda x:x[1], reverse = True)
i=0
j=0
cnt=0
ans=0
while True:
    if j<m and a[i]<bc[j][1]:
        ans+=min(n-cnt, bc[j][0])*bc[j][1]
        cnt+=min(n-cnt, bc[j][0])
        j+=1
    else:
        ans+=a[i]
        i+=1
        cnt+=1
    if cnt==n:
        break
print(ans)

Buggy python submission (verdict: Runtime Error):
n, m = map(int, input().split())
a=sorted(list(map(int, input().split())))
bc = sorted([list(map(int, input().split())) for _ in range(m)], key = lambda x:x[1], reverse = True)
tmp=0
cnt=0
ans=0
print(a, bc)
for i in range(n):
    if cnt>=bc[tmp][0]:
        ans+=bc[tmp][1]*bc[tmp][0]
        cnt-=bc[tmp][0]
        tmp+=1
    if a[i]>bc[tmp][1]:
        k=i
        ans+=bc[tmp][1]*(cnt)
        break
    cnt+=1
print(sum(a[k:])+ans)

Fixed submission:
n, m = map(int, input().split())
a=sorted(list(map(int, input().split())), reverse = True)
bc = sorted([list(map(int, input().split())) for _ in range(m)], key = lambda x:x[1], reverse = True)
i=0
j=0
cnt=0
ans=0
while True:
    if j<m and a[i]<bc[j][1]:
        ans+=min(n-cnt, bc[j][0])*bc[j][1]
        cnt+=min(n-cnt, bc[j][0])
        j+=1
    else:
        ans+=a[i]
        i+=1
        cnt+=1
    if cnt==n:
        break
print(ans)
Buggy python submission (verdict: Runtime Error):

class UnionFind(object):
    def __init__(self, size):
        self.parent = [i for i in range(size)]
        self.rank = [0 for _ in range(size)]
 
 
    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            return self.find(self.parent[x])
 
 
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
 
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
 
    def same(self, x, y):
        return self.find(x) == self.find(y)
n, m = map(int, input().split())
U=UnionFind(n)
for i in range(m):
    x, y, z = map(int, input().split())
    U.unite(x-1, y-1)
cnt=0
for i in range(n):
    if U.find(i)==i:
        cnt+=1
print(cnt)

Fixed submission:
n, k = map(int, input().split())
s=list(input())
s[k-1]=s[k-1].lower()
print(''.join(s))
Buggy python submission (verdict: Runtime Error):
M, K = map(int, input().split())
if K>1<<M-1:
    print(-1)
elif M == 1 and K == 1:
    print(-1)
elif M == 1 and K == 0:
    print(0, 0, 1, 1)
elif M == 0 and K == 0:
    print(0, 0)
elif M == 0:
    print(-1)
else:
    N = 1<<M
    ans = list(range(K))+list(range(K+1, N))+[K]+list(range(K+1, N))[::-1]+list(range(K))[::-1]+[K]
    print(*ans)

Fixed submission:
M, K = map(int, input().split())
if K>(1<<M)-1:
    print(-1)
elif M == 1 and K == 1:
    print(-1)
elif M == 1 and K == 0:
    print(0, 0, 1, 1)
elif M == 0 and K == 0:
    print(0, 0)
elif M == 0:
    print(-1)
else:
    N = 1<<M
    ans = list(range(K))+list(range(K+1, N))+[K]+list(range(K+1, N))[::-1]+list(range(K))[::-1]+[K]
    print(*ans)
Buggy python submission (verdict: Time Limit Exceeded):
r, g, b, n = map(int, input().split())
ans=0
for i in range(n//r+1):
    for j in range(n-r*i+1):
        p=n-(r*i+g*j)
        if p>=0 and p%b==0:
            ans+=1
print(ans)

Fixed submission:
r, g, b, n = map(int, input().split())
ans=0
for i in range(n//r+1):
    for j in range(n-r*i+1):
        p=n-(r*i+g*j)
        if p>=0 and p%b==0:
            ans+=1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
r, g, b, n = map(int, input().split())
ans=0
for i in range(3001):
    for j in range(3001):
        if n-(r*i+g*j)>=0 and (n-(r*i+g*j))%b==0:
            ans+=1
print(ans)

Fixed submission:
r, g, b, n = map(int, input().split())
ans=0
for i in range(n//r+1):
    for j in range(n-r*i+1):
        p=n-(r*i+g*j)
        if p>=0 and p%b==0:
            ans+=1
print(ans)
Buggy python submission (verdict: Runtime Error):
N = int(input())
edges = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)

def bfs(v0):
    dist = [-1]*N
    que = deque([v0])
    dist[v0] = 0
    while que:
        v = que.pop()
        d = dist[v]
        for nv in edges[v]:
            if dist[nv] < 0:
                que.append(nv)
                dist[nv] = d+1
    m = max(dist)
    v = dist.index(d)
    return v, m
u, _ = bfs(0)
_, dia = bfs(u)
if (dia+1-2)%3 == 0:
    print('Second')
else:
    print('First')


Fixed submission:
from collections import deque
N = int(input())
edges = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)

def bfs(v0):
    dist = [-1]*N
    que = deque([v0])
    dist[v0] = 0
    while que:
        v = que.pop()
        d = dist[v]
        for nv in edges[v]:
            if dist[nv] < 0:
                que.append(nv)
                dist[nv] = d+1
    m = max(dist)
    v = dist.index(m)
    return v, m
u, _ = bfs(0)
_, dia = bfs(u)
if N == 1:
    print('First')
elif (dia+1-2)%3 == 0:
    print('Second')
else:
    print('First')
Buggy python submission (verdict: Runtime Error):
n=int(input())
a=list(map(int, input().split()))
pos=[]
nega=[]
for i in range(n):
    if a[i]>=0:
        pos.append(a[i])
    else:
        nega.append(a[i])
if len(nega)%2==0:
    print(sum(pos)-sum(nega))
else:
    if min(pos)>-max(nega):
        print(sum(pos)-sum(nega)+max(nega)*2)
    else:
        print(sum(pos)-sum(nega)-min(pos)*2)
        

Fixed submission:
n=int(input())
a=list(map(int, input().split()))
pos=[]
nega=[]

for i in range(n):
    if a[i]>=0:
        pos.append(a[i])
    else:
        nega.append(a[i])
if len(pos)==0:
    if len(nega)%2==0:
        print(abs(sum(a)))
    else:
        print(abs(sum(a))+max(a)*2)
elif len(nega)==0:
    print(sum(a))
elif len(nega)%2==0:
    print(sum(pos)-sum(nega))
else:
    if min(pos)>-max(nega):
        print(sum(pos)-sum(nega)+max(nega)*2)
    else:
        print(sum(pos)-sum(nega)-min(pos)*2)
Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
s=list(map(int, list(input())))
tmp=s[0]
cnt=[]
c=0
for i in range(n):
    if tmp==s[i]:
        c+=1
    else:
        tmp=s[i]
        cnt.append( c)
        c=1
    if i==n-1:
        cnt.append( c)
ans=0
for i in range(len(cnt)):
    if i%2==s[0]:
        if i+k*2<=len(cnt):
            ans=max(ans, sum(cnt[i:i+k*2]))
        else:
            ans=max(ans, sum(cnt[i:]))
    else:
        if i+k*2+1<=len(cnt):
            ans=max(ans, sum(cnt[i:i+k*2+1]))
        else:
            ans=max(ans, sum(cnt[i:]))
print(ans)
    

Fixed submission:
n, k = map(int, input().split())
s=list(map(int, list(input())))
tmp=s[0]
cnt=[]
c=0
for i in range(n):
    if tmp==s[i]:
        c+=1
    else:
        tmp=s[i]
        cnt.append( c)
        c=1
    if i==n-1:
        cnt.append( c)
ans=0
S=[0]*len(cnt)
S[0]=cnt[0]
for i in range(1, len(cnt)):
    S[i]=S[i-1]+cnt[i]
S=[0]+S

for i in range(len(cnt)):
    if i%2==s[0]:
        if i+k*2<=len(cnt):
            ans=max(ans, S[i+k*2]-S[i])
        else:
            ans=max(ans, S[len(cnt)]-S[i])
    else:
        if i+k*2+1<=len(cnt):
            ans=max(ans, S[i+k*2+1]-S[i])
        else:
            ans=max(ans,S[len(cnt)]-S[i])
print(ans)
Buggy python submission (verdict: Runtime Error):
from heapq import heappush, heappop
s=set()
q=[]
x, y, z, k = map(int, input().split())
a=sorted(list(map(int, input().split())), reverse=True)
b=sorted(list(map(int, input().split())), reverse=True)
c=sorted(list(map(int, input().split())), reverse=True)
heapq.heappush(q, (-(a[0]+b[0]+c[0]), 0, 0, 0))
def push(d, e, f):
    if (d, e, f) not in s and 0<=d<x and 0<=e<y and 0<=f<z:
        heapq.heappush(q, (-(a[d]+b[e]+c[f]), d, e, f))
        s.add((d, e, f))
for i in range(k):
    p, d, e, f =heapq.heappop(q)
    print(-p)
    push(d+1, e, f)
    push(d, e+1, f)
    push(d, e, f+1)
        

Fixed submission:
from heapq import heappush, heappop
s=set()
q=[]
x, y, z, k = map(int, input().split())
a=sorted(list(map(int, input().split())), reverse=True)
b=sorted(list(map(int, input().split())), reverse=True)
c=sorted(list(map(int, input().split())), reverse=True)
heappush(q, (-(a[0]+b[0]+c[0]), 0, 0, 0))
def push(d, e, f):
    if (d, e, f) not in s and 0<=d<x and 0<=e<y and 0<=f<z:
        heappush(q, (-(a[d]+b[e]+c[f]), d, e, f))
        s.add((d, e, f))
for i in range(k):
    p, d, e, f =heappop(q)
    print(-p)
    push(d+1, e, f)
    push(d, e+1, f)
    push(d, e, f+1)
Buggy python submission (verdict: Runtime Error):
n,m = map(int, input().split())
q=[input() for i in range(n)]
l=[i+1 for i in range(m)]
l1=[i+1 for i in range(m)]
for i in q:
  t=list(map(int, i.split()))
  for k in l1:
    if (k not in t[1:]):
      l.remove(k)
print(len(l))


Fixed submission:
n,m = map(int, input().split())
q=[input() for i in range(n)]
l=[i+1 for i in range(m)]
l1=[i+1 for i in range(m)]
for i in q:
  t=list(map(int, i.split()))
  for k in l1:
    if (k not in t[1:]):
      if k in l:
      	l.remove(k)
print(len(l))
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**9)
N = int(input())
h = list(map(int, input().split()))
from functools import lru_cache
@lru_cache(maxsize=10000000)
def dp(i):
    if i == 0:
        return 0
    if i>=2:
        return min(dp(i-1)+abs(h[i]-h[i-1]), dp(i-2)+abs(h[i]-h[i-2]))
    else:
        return dp(i-1)+abs(h[i]-h[i-1])
print(dp(N-1))

Fixed submission:
N = int(input())
h = list(map(int, input().split()))
dp = [0]*N
for i in range(1, N):
    if i-2>=0:
        dp[i] = min(dp[i-1]+abs(h[i]-h[i-1]), dp[i-2]+abs(h[i]-h[i-2]))
    else:
        dp[i] = dp[i-1]+abs(h[i]-h[i-1])
print(dp[-1])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**9)
N = int(input())
h = list(map(int, input().split()))
from functools import lru_cache
@lru_cache(maxsize=1000)
def dp(i):
    if i == 0:
        return 0
    if i>=2:
        return min(dp(i-1)+abs(h[i]-h[i-1]), dp(i-2)+abs(h[i]-h[i-2]))
    else:
        return dp(i-1)+abs(h[i]-h[i-1])
print(dp(N-1))



Fixed submission:
N = int(input())
h = list(map(int, input().split()))
dp = [0]*N
for i in range(1, N):
    if i-2>=0:
        dp[i] = min(dp[i-1]+abs(h[i]-h[i-1]), dp[i-2]+abs(h[i]-h[i-2]))
    else:
        dp[i] = dp[i-1]+abs(h[i]-h[i-1])
print(dp[-1])

Buggy python submission (verdict: Runtime Error):
sys.setrecursionlimit(10**9)
N = int(input())
h = list(map(int, input().split()))
memo = [-1]*N
def dp(i):
    if memo[i]>=0:
        return memo[i]
    if i == 0:
        memo[i] = 0
        return 0
    if i>=2:
        memo[i] = min(dp(i-1)+abs(h[i]-h[i-1]), dp(i-2)+abs(h[i]-h[i-2]))
    else:
        memo[i] = dp(i-1)+abs(h[i]-h[i-1])
    return memo[i]
print(dp(N-1))



Fixed submission:
N = int(input())
h = list(map(int, input().split()))
dp = [0]*N
for i in range(1, N):
    if i-2>=0:
        dp[i] = min(dp[i-1]+abs(h[i]-h[i-1]), dp[i-2]+abs(h[i]-h[i-2]))
    else:
        dp[i] = dp[i-1]+abs(h[i]-h[i-1])
print(dp[-1])

Buggy python submission (verdict: Runtime Error):
N = int(input())
h = list(map(int, input().split()))
memo = [-1]*N
def dp(i):
    if memo[i]>=0:
        return memo[i]
    if i == 0:
        memo[i] = 0
        return 0
    if i>=2:
        memo[i] = min(dp(i-1)+abs(h[i]-h[i-1]), dp(i-2)+abs(h[i]-h[i-2]))
    else:
        memo[i] = dp(i-1)+abs(h[i]-h[i-1])
    return memo[i]
print(dp(N-1))



Fixed submission:
N = int(input())
h = list(map(int, input().split()))
dp = [0]*N
for i in range(1, N):
    if i-2>=0:
        dp[i] = min(dp[i-1]+abs(h[i]-h[i-1]), dp[i-2]+abs(h[i]-h[i-2]))
    else:
        dp[i] = dp[i-1]+abs(h[i]-h[i-1])
print(dp[-1])
Buggy python submission (verdict: Runtime Error):
import sys
#input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
 
import numpy as np
N, W = map(int, input().split())
dp = np.zeros(W+1, dtype = np.int64)
for _ in range(N):
    w, v = map(int, input().split())
    np.maximum(dp[w:], dp[:-w] + v, out = dp[w:])
print(dp.max())

Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
 
import numpy as np
N, W = map(int, input().split())
dp = np.zeros(W+1, dtype = np.int64)
for _ in range(N):
    w, v = map(int, input().split())
    np.maximum(dp[w:], dp[:-w] + v, out = dp[w:])
print(dp.max())
Buggy python submission (verdict: Runtime Error):
import numpy as np
mod = 10**9+7
def MatPower(A, k):
    B = np.identity(len(A), dtype = object)
    while k:
        if k&1:
            B = np.dot(A, B)%mod
        A = np.dot(A, A)%mod
        k//=2
    return B
N, K = map(int, input().split())
a = np.array([list(map(int, input().split())) for _ in range(N)], dtype = object)
v = np.array([1]*N, dtype = object).T
An = MatPower(a, K)
v = np.dot(An, v)%mod
ans = 0
for i in range(N):
    ans+=v[i]
    ans%=mod
print(ans)





Fixed submission:
import sys
#input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N, M = map(int, input().split())
G = [[] for _ in range(N)]
H = [0]*N
for _ in range(M):
    x, y = map(int, input().split())
    G[x-1].append(y-1)
    H[y-1]+=1

def topological_sort(G, H):
    res = []
    st0 = set()
    for v, n in enumerate(H):
        if n == 0:
            st0.add(v)
    while st0:
        v = st0.pop()
        res.append(v)
        for nv in G[v]:
            H[nv]-=1
            if H[nv] == 0:
                st0.add(nv)
    return res
i_to_v = topological_sort(G, H)
v_to_i = [0]*N
for i in range(N):
    v_to_i[i_to_v[i]] = i
dp = [0]*N
for i in range(N-1):
    for nv in G[i_to_v[i]]:
        dp[v_to_i[nv]] = max(dp[i]+1, dp[v_to_i[nv]])
print(max(dp))
Buggy python submission (verdict: Time Limit Exceeded):
import sys
#input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
mod = 10**9+7
N = int(input())
p = list(map(float, input().split()))
dp = [[0]*(N+1) for _ in range(N)]
dp[0][0] = 1-p[0]
dp[0][1] = p[0]
for i in range(1, N):
    for j in range(N+1):
        if j == 0:
            dp[i][j] = dp[i-1][j]*(1-p[i])
        else:
            dp[i][j] = dp[i-1][j-1]*p[i]+dp[i-1][j]*(1-p[i])
print(sum(dp[-1][(N+1)//2:]))








Fixed submission:
import sys
#input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
mod = 10**9+7
N = int(input())
p = list(map(float, input().split()))
dp = [[0]*(N+1) for _ in range(N)]
dp[0][0] = 1-p[0]
dp[0][1] = p[0]
for i in range(1, N):
    for j in range(N+1):
        if j == 0:
            dp[i][j] = dp[i-1][j]*(1-p[i])
        else:
            dp[i][j] = dp[i-1][j-1]*p[i]+dp[i-1][j]*(1-p[i])
print(sum(dp[-1][(N+1)//2:]))
Buggy python submission (verdict: Time Limit Exceeded):
mod = 10**9+7
N = int(input())
a = list(map(int, input().split()))
S = [0]*(N+1)#i~j-1の和はS[j]-S[i]
for i in range(1, N+1):
    S[i] = S[i-1]+a[i-1]
memo = [[-1]*(N+1) for _ in range(N)]
def dp(i, j):
    if memo[i][j]>=0:
        return memo[i][j]
    if j-i == 1:
        memo[i][j] = 0
        return 0
    memo[i][j] = min(dp(i, k)+dp(k, j)+S[j]-S[i]for k in range(i+1, j))
    return memo[i][j]
print(dp(0, N))


    








Fixed submission:
mod = 10**9+7
N = int(input())
a = list(map(int, input().split()))
S = [0]*(N+1)
for i in range(1, N+1):
    S[i] = S[i-1]+a[i-1]
dp = [[float('inf')]*(N+1) for _ in range(N)]
for i in range(N):
    dp[i][i+1] = 0
for l in range(2, N+1):
    for i in range(N-l+1):
        j = i+l
        for ll in range(1, l):
            k = i+ll
            dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j]+S[j]-S[i])
print(dp[0][-1])