Harryxun/GPT-100-sft-dataset huggingface dataset:
Problem p02716 (python)

Fixed submission:
n = int(input())
*A, = map(int, input().split())
inf = 10**18
# DP[i][0]=i番目まででi//2個選んだ最大値
# DP[i][1]=i番目まででi//2+1個選んだ最大値
DP = [[-inf]*2 for i in range(n)]
DP[0][0] = 0
DP[0][1] = A[0]
DP[1][0] = 0
DP[1][1] = max(A[0], A[1])
for i in range(2, n):
    if i % 2 == 0:
        DP[i][0] = max(DP[i-2][0]+A[i], DP[i-1][1])
        DP[i][1] = DP[i-2][1]+A[i]
    else:
        DP[i][0] = max(DP[i-2][0]+A[i], DP[i-1][0])
        DP[i][1] = max(DP[i-2][1]+A[i], DP[i-1][1])
if n % 2 == 0:
    print(DP[n-1][1])
else:
    print(DP[n-1][0])

Buggy submission (verdict: Runtime Error):
n = int(input())
*A, = map(int, input().split())
inf = 10**18
# DP[i][0]=i番目まででi//2個選んだ最大値
# DP[i][1]=i番目まででi//2+1個選んだ最大値
DP = [(None, None) for i in range(n)]
DP[0] = (0, A[0])
DP[1] = (0, max(A[0], A[1]))
for i in range(2, n):
    if i % 2 == 0:
        DP[i][0] = max(DP[i-2][0]+A[i], DP[i-1][1])
        DP[i][1] = DP[i-2][1]+A[i]
    else:
        DP[i][0] = max(DP[i-2][0]+A[i], DP[i-1][0])
        DP[i][1] = max(DP[i-2][1]+A[i], DP[i-1][1])
if n % 2 == 0:
    print(DP[n-1][1])
else:
    print(DP[n-1][0])

Buggy submission (verdict: Runtime Error):
n = int(input())
*A, = map(int, input().split())
inf = 10**18
X0 = (0, A[0])
X1 = (0, max(A[0], A[1]))
for i in range(2, n):
    X20 = max(X0[0]+A[i], X1[1]*(1-i % 2)+X1[0]*(i % 2))
    X21 = max(X0[1]+A[i], X1[1]*(1-i % 2)+(-inf)*(i % 2))
    X2 = (X20, X21)
    X0, X1 = X1, X2
if n % 2 == 1:
    print(X2[0])
else:
    print(X2[1])
Problem p02774 (python)

Fixed submission:
import numpy as np


def count_pair(x):
    # A内のペアで積がxより小さいものの個数
    # まず(i,j)と(j,i)を重複して数える
    cnt = 0
    # A[i]<0なる各iに対してA[j]>x/A[i]なるjの個数
    cnt += (N-np.searchsorted(A, x//A_nega, side='right')).sum()
    if x > 0:
        # 各iに対してA[j]=0なるjの個数
        cnt += len(A_zero)*N
    # A[i]>0なる各iに対してA[j]<x/A[i]なるjの個数
    cnt += np.searchsorted(A, -(-x//A_posi), side='left').sum()
    # i=jを除いてから2で割る
    cnt = (cnt-(A**2 < x).sum())//2
    return cnt


# count_pair(x)<Kをみたすxの最大値を二分探索で求める
N, K = map(int, input().split())
* A, = map(int, input().split())
A = np.array(A)
A = np.sort(A)
A_posi = A[A > 0]
A_zero = A[A == 0]
A_nega = A[A < 0]
inf = 10**18+1
l, r = -inf, inf
while r - l > 1:
    c = (l + r) // 2
    if count_pair(c) < K:
        l = c
    else:
        r = c
print(l)

Buggy submission (verdict: Runtime Error):
import numpy as np

def count_pair(x):
    cnt = 0
    cnt += (n-np.searchsorted(A, x//A_nega, side='right')).sum()
    if x > 0:
        cnt += len(A_zero)*n
    cnt += np.searchsorted(A, -(-x//A_posi), side='left').sum()
    cnt = (cnt-(A**2 < x).sum())//2
    return cnt

n, k = map(int, input().split())
* A, = map(int, input().split())
A = np.array(A)
A = np.sort(A)
A_posi = A[A > 0]
A_zero = A[A == 0]
A_nega = A[A < 0]
inf = 10**18+1
l, r = -inf, inf
while r - l > 1:
    c = (l + r) // 2
    if count_pair(c) < K:
        l = c
    else:
        r = c
print(l)

Buggy submission (verdict: Runtime Error):
n = [int(_) for _ in list(input())]
a, b = 0, 1
for i in n:
    a, b = min(a+i, b+10-i), min(a+(i+1), b+10-(i+1))
print(a)

Buggy submission (verdict: Runtime Error):
def count_pair(A, x, K):
    # A内のペアで積がxより小さいものの個数がK未満ならTrueを返す
    cnt = 0
    N = len(A)
    for n in range(N - 1):
        if A[n] < 0:
            y = x // A[n]
            # n+1番以降でyより大きいものの個数
            m = N-1
            while A[m] > y and m > n:
                cnt += 1
                m -= 1
                if cnt >= K:
                    return False
        elif A[n] > 0:
            y = -(-x // A[n])
            # n+1番以降でyより小さいものの個数
            m = n + 1
            while A[m] < y and m < N:
                cnt += 1
                m += 1
                if cnt >= K:
                    return False
        elif x > 0:
            cnt += N - (n + 1)
            if cnt >= K:
                return False
    return True


def main():
    # count_pair(x)<Kをみたすxの最大値を求める
    N, K = map(int, input().split())
    * A, = map(int, input().split())
    A.sort()
    inf = 10**18+1
    l, r = -inf, inf
    for _ in range(inf):
        if r - l <= 1:
            print(l)
            exit()
        c = (l + r) // 2
        if count_pair(A, c, K):
            l = c
        else:
            r = c


if __name__ == '__main__':
    main()
Problem p02788 (python)

Fixed submission:
n, d, a = map(int, input().split())
XH = []
for i in range(n):
    x, h = map(int, input().split())
    XH.append((x, h))
XH.sort()
X = [x for x, h in XH]
H = [h for x, h in XH]
# n, d, a = 9, 2, 2
# X = [1, 3, 4, 6, 9, 10, 12, 13, 16]
# H = [7, 6, 7, 5, 10, 3, 8, 9, 6]
X.append(10**10)
H.append(0)
j = 0
c = 0
S = [0]*(n+1)
for i in range(n):
    H[i] = max(0, H[i]-S[i])
    c += -(-H[i]//a)
    while X[j] <= X[i] + 2*d:
        j += 1
    S[i+1] += S[i] + -(-H[i]//a)*a
    S[j] -= -(-H[i]//a)*a
    # print(i)
    # print(H)
    # print(S)
# print(H)
# print(S)
print(c)

Buggy submission (verdict: Runtime Error):
n, d, a = map(int, input().split())
XH = [tuple(map(input().split())) for i in range(n)]
XH.sort()
X = [x for x, h in XH]
H = [h for x, h in XH]
X.append(10**10)
H.append(0)
j = 0
S = [0]*(n+1)
ans = 0
for i in range(n):
    H[i] = max(0, H[i]-S[i])
    c = -(-H[i]//a)
    while X[j] <= X[i] + 2*d:
        j += 1
    S[i+1] += S[i] + a*c
    S[j] -= a*c
    ans += c
print(ans)
Problem p02814 (python)

Fixed submission:
import functools
import fractions

def lcm(a, b):
    return a * b // fractions.gcd(a, b)

# xが2で何回割れるか
def div2count(x):
    count=0
    while x%2==0:
        x=x//2
        count+=1
    return count

N,M=map(int,input().split())
A=list(map(int,input().split()))
if len(set(map(div2count,A)))!=1:
    print(0)
    exit()
LCM=functools.reduce(lcm,A)
HLCM=LCM//2
Y=M//HLCM
if Y%2==0:
    print(Y//2)
else:
    print((Y+1)//2)

Buggy submission (verdict: Runtime Error):
import functools
import math
def lcm(a, b):
    return a * b // math.gcd(a, b)
N,M=map(int,input().split())
A=list(map(int,input().split()))
LCM=functools.reduce(lcm,A)
HLCM=LCM//2
Y=M//HLCM
if Y%2==0:
    print(Y//2)
else:
    print((Y+1)//2)
Problem p02837 (python)

Fixed submission:
N=int(input())
A,X,Y=[],[],[]
for n in range(N):
    An=int(input())
    Xn,Yn=[],[]
    for a in range(An):
        x,y=map(int,input().split())
        Xn.append(x-1)
        Yn.append(y)
    A.append(An)
    X.append(Xn)
    Y.append(Yn)

max_count=0
for k in range(2**N):
    P=[int(_) for _ in bin(k)[2:].zfill(N)]
    ok=True
    for i in range(N):
        for j in range(A[i]):
            if P[i]==1 and P[X[i][j]]!=Y[i][j]:
                ok=False
    if ok:
        max_count=max(max_count,sum(P))
print(max_count)

Buggy submission (verdict: Runtime Error):
N=int(input())
A,X,Y=[],[],[]
for n in range(N):
    An=int(input())
    Xn,Yn=[],[]
    for a in range(An):
        x,y=map(int,input().split())
        Xn.append(x-1)
        Yn.append(y)
    A.append(An)
    X.append(Xn)
    Y.append(Yn)

max_count=0
for k in range(2**N):
    P=[int(_) for _ in bin(k)[2:].zfill(N)]
    ok=True
    for i in range(N):
        for j in range(A[i]):
            if P[i]==1 and P[X[i][j]]!=Y[i][j]
                ok=False
    if ok:
        max_count=max(max_count,sum(P))
print(max_count)
Problem p02844 (python)

Fixed submission:
N = int(input())
S = input()
L = [str(i).zfill(3) for i in range(1000)]
count = 0
for l in L:
    try:
        i = S.index(l[0])
        j = S.index(l[1], i + 1)
        k = S.index(l[2], j + 1)
        count += 1
    except:
        continue
print(count)

Buggy submission (verdict: Runtime Error):
import numpy as np
N = int(input())
S = input()
L = [str(i).zfill(3) for i in range(1000)]


def contain(l):
    phase = 0
    for c in S:
        if phase == 0 and c == l[0]:
            phase = 1
            continue
        if phase == 1 and c == l[1]:
            phase = 2
            continue
        if phase == 2 and c == l[2]:
            return 1
    return 0


f = np.frompyfunc(contain, 1, 1)
print(sum(f(L)))
Problem p02850 (python)

Fixed submission:
from collections import deque

N=int(input())
G=[[] for n in range(N)]
E=[]
for n in range(N-1):
    a,b=map(int,input().split())
    E.append((a-1,b-1))
    G[a-1].append(b-1)
    G[b-1].append(a-1)
K=max([len(v) for v in G])

P=[-1]*N
Q=[0]
X=[]
count=0
while Q:
    v=Q.pop()
    X.append(v)
    for u in G[v]:
        if u==P[v]:
            continue
        P[u]=v
        Q.append(u)

C={}
for v in X:
    color=0
    try:
        p_color=C[tuple(sorted((v,P[v])))]
    except:
        p_color=-1
    for u in G[v]:
        if u==P[v]:
            continue
        if color==p_color:
            color+=1
        C[tuple(sorted((u,v)))]=color
        color+=1

print(K)
for e in E:
    print(C[e]+1)

Buggy submission (verdict: Runtime Error):
import copy
N=int(input())
G=[[] for n in range(N)]
E=[]
for n in range(N-1):
    a,b=map(int,input().split())
    E.append((a-1,b-1))
    G[a-1].append(b-1)
    G[b-1].append(a-1)

deg=[len(v) for v in G]
K=max(deg)
Q=copy.copy(G[0])
X=[0]
C=[0]*N
color_map={}
while Q!=[]:
    v=Q.pop(0)
    X.append(v)
    colors=list(range(1,K+1))
    for u in G[v]:
        if C[u] in colors:
            colors.remove(C[u])
        for w in G[u]:
            if C[w] in colors:
                colors.remove(C[w])
        if u not in X:
            Q.append(u)
    color=copy.copy(colors[0])
    C[v]=color
    p=list(set(X)&set(G[v]))[0]
    color_map[(min(p,v),max(p,v))]=color

print(K)
for e in E:
    print(color_map[e])
Problem p02889 (python)

Fixed submission:
from scipy.sparse.csgraph import floyd_warshall
N,M,L=map(int,input().split())
inf=10**9+1

distance=[[inf for n in range(N)] for n in range(N)]
for n in range(N):
    distance[n][n]=0
for m in range(M):
    a,b,c=map(int,input().split())
    distance[a-1][b-1]=c
    distance[b-1][a-1]=c
distance=floyd_warshall(distance)

distance2=[[inf for n in range(N)] for n in range(N)]
for i in range(N):
    for j in range(N):
        if distance[i][j]<=L:
            distance2[i][j]=1
for n in range(N):
    distance2[n][n]=0
distance2=floyd_warshall(distance2)

Q=int(input())
for q in range(Q):
    s,t=map(int,input().split())
    if distance2[s-1][t-1]==inf:
        print(-1)
    else:
        print(int(distance2[s-1][t-1]-1))

Buggy submission (verdict: Runtime Error):
from scipy.sparse.csgraph import floyd_warshall
N,M,L=map(int,input().split())
inf=10**9+1

distance=[[inf for n in range(N)] for n in range(N)]
for n in range(N):
    distance[n][n]=0
for m in range(M):
    a,b,c=map(int,input().split())
    distance[a-1][b-1]=c
    distance[b-1][a-1]=c
distance=floyd_warshall

distance2=[[inf for n in range(N)] for n in range(N)]
for i in range(N):
    for j in range(N):
        if distance[i][j]<=L:
            distance2[i][j]=1
for n in range(N):
    distance2[n][n]=0
distance2=floyd_warshall(distance2)

Q=int(input())
for q in range(Q):
    s,t=map(int,input().split())
    if distance2[s-1][t-1]==inf:
        print(-1)
    else:
        print(distance2[s-1][t-1]-1)
Problem p02923 (python)

Fixed submission:
N=int(input())
H=list(map(int,input().split()))
count=0
maxcount=0
for n in range(N-1):
    right=H[-(n+1)]
    left=H[-(n+2)]
    if left>=right:
        count+=1
    else:
        count=0
    if count>maxcount:
        maxcount=count

print(maxcount)

Buggy submission (verdict: Runtime Error):
N=int(input())
H=list(map(int,input().split()))
count=0
H0=[]
for n in range(N-1):
    right=H[-(n+1)]
    left=H[-(n+2)]
    if left>=right:
        count+=1
        H0=[count]+H0
    else:
        count=0
        H0=[count]+H0

print(max(H0))
Problem p02953 (python)

Fixed submission:
N=int(input())
H=list(map(int,input().split()))
answer='Yes'
for i in range(N-1):
    left=H[N-2-i]
    right=H[N-1-i]
    if left<=right and answer=='Yes':
        answer='Yes'
    elif left==right+1 and answer=='Yes':
        H[N-2-i]-=1
    else:
        answer='No'
print(answer)

Buggy submission (verdict: Runtime Error):
N=int(input())
H=list(map(int,input().split()))
answer='Yes'
for i in range(N-1):
    if H[N-1-i]>=H[N-2-i]:
        answer='Yes'
    elif H[N-1-i]+1==H[N-2-i]:
        H[N-2-i]-=1
    else:
        answer='No'
    print(H)
print(answer)
Problem p02975 (python)

Fixed submission:
import collections
N=int(input())
a=list(map(int,input().split()))
def judge(a):
    if sum(a)==0:
        return True
    else:
        a=dict(collections.Counter(a))
        if len(a.keys())==3:
            a0=list(a.keys())[0]
            a1=list(a.keys())[1]
            a2=list(a.keys())[2]
            if a0^a1==a2 and a[a0]==a[a1] and a[a1]==a[a2]:
                return True
        if len(a.keys())==2:
            a0=list(a.keys())[0]
            a1=list(a.keys())[1]
            if a0==0 or a1==0:
                if a[a0]==2*a[a1] or a[a1]==2*a[a0]:
                    return True
    return False

if judge(a):
    print("Yes")
else:
    print("No")

Buggy submission (verdict: Runtime Error):
import collections
N=int(input())
a=list(map(int,input().split()))
def judge(a):
    if sum(a)==0:
        return True
    else:
        a=dict(collections.Counter(a))
        a0=list(a.keys())[0]
        a1=list(a.keys())[1]
        a2=list(a.keys())[2]
        if a0^a1==a2:
            return True
    return False

if judge(a):
    print("Yes")
else:
    print("No")
Problem p03037 (python)

Fixed submission:
N,M=map(int,input().split())
L=[]
R=[]
for m in range(M):
    Lm,Rm=map(int,input().split())
    L.append(Lm)
    R.append(Rm)
maxL=max(L)
minR=min(R)
print(max(minR-maxL+1,0))

Buggy submission (verdict: Runtime Error):
n, m = map(int, input().split())
l0, r0 = 1, n
for j in range(m):
    l1, r1 = map(int, inp)
    l0 = max(l0, l1)
    r0 = min(r0, r1)
print(max(0, r0-l0+1))
Problem p03061 (python)

Fixed submission:
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors

N=int(input())
A=list(map(int,input().split()))
x=A[0]
y=A[1]
D=sorted(list(set(make_divisors(x))|set(make_divisors(y))))[::-1]
for d in D:
    if sum([a%d==0 for a in A])>=N-1:
        break
print(d)

Buggy submission (verdict: Runtime Error):
import math
N=int(input())
A=list(map(int,input().split()))
L=[0]
R=[0]
for i in range(N-1):
    L=L+[math.gcd(L[-1],A[i])]
    R=[math.gcd(R[0],A[N-i-1])]+R
M=[math.gcd(L[n],R[n]) for n in range(N)]
print(max(M))
Problem p03067 (python)

Fixed submission:
A, B, C = map(int, input().split())
if A < C < B or B < C < A:
    print("Yes")
else:
    print("No")

Buggy submission (verdict: Runtime Error):
A, B, C = map(int, input().split())
if A < C < B or B < C < A:
    print("Yes")
else:
    print("No")
Problem p03078 (python)

Fixed submission:
X, Y, Z, K = map(int, input().split())
*A, = sorted(map(int, input().split()), reverse=True)
*B, = sorted(map(int, input().split()), reverse=True)
*C, = sorted(map(int, input().split()), reverse=True)
AB = [A[x] + B[y] for y in range(Y) for x in range(X)]
AB.sort(reverse=True)
AB = AB[:K]
ABC = [AB[x] + C[z] for z in range(Z) for x in range(len(AB))]
ABC.sort(reverse=True)
for k in range(K):
    print(ABC[k])

Buggy submission (verdict: Runtime Error):
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()))
AB = [A[x]+B[y] for x in range(X) for y in range(Y)]
AB.sort(reverse=True)
AB = AB[:K]
ABC = [AB[k]+C[z] for k in range(K) for z in range(Z)]
ABC.sort(reverse=True)
for k in range(K):
    print(ABC[k])
Problem p03105 (python)

Fixed submission:
A,B,C=map(int,input().split())
print(min(int(B/A),C))

Buggy submission (verdict: Runtime Error):
A,B,C=map(int,input().split())
print(min(int(B/A),C)
Problem p03160 (python)

Fixed submission:
N = int(input())
h = list(map(int, input().split()))
dp = [10 ** 10] * N
# dp[n]はあとnのところからのN-1に行くのに支払うコストの最小値
dp[0] = 0
dp[1] = abs(h[N-1]-h[N-2])
for n in range(0, N-2):
    dp[n+2] = min(dp[n+1]+abs(h[(N-1)-(n+2)]-h[(N-1)-(n+1)]),
                  dp[n]+abs(h[(N-1)-(n+2)]-h[(N-1)-n]))
print(dp[N-1])

Buggy submission (verdict: Runtime Error):
N, K = map(int, input().split())
K = 2
*h, = map(int, input().split())
a = [abs(h[0] - h[k]) for k in range(K)]
for n in range(N - K):
    a = a[1:] + [min([a[k] + abs(h[n + k] - h[n + K]) for k in range(K)])]
print(a[K - 1])
Problem p03161 (python)

Fixed submission:
N, K = map(int, input().split())
K = min(N, K)
*h, = map(int, input().split())
a = [abs(h[0] - h[k]) for k in range(K)]
for n in range(N - K):
    a = a[1:] + [min([a[k] + abs(h[n + k] - h[n + K]) for k in range(K)])]
print(a[K - 1])

Buggy submission (verdict: Runtime Error):
N, K = map(int, input().split())
*h, = map(int, input().split())
a = [abs(h[0] - h[k]) for k in range(K)]
for n in range(N - K):
    a = a[1:] + [min([a[k] + abs(h[n + k] - h[n + K]) for k in range(K)])]
print(a[K - 1])
Problem p03165 (python)

Fixed submission:
S = input()
T = input()
m, n = len(S), len(T)
C = [[0 for j in range(n+1)] for i in range(m+1)]
for i in range(m):
    for j in range(n):
        if S[i] == T[j]:
            C[i+1][j+1] = C[i][j] + 1
        else:
            C[i+1][j+1] = max(C[i][j+1], C[i+1][j])
l = C[m][n]
X = ''
while l:
    if S[m-1] == T[n-1]:
        X = S[m-1]+X
        m -= 1
        n -= 1
        l -= 1
    elif C[m][n] == C[m-1][n]:
        m -= 1
    else:
        n -= 1
print(X)

Buggy submission (verdict: Runtime Error):
S = input()
T = input()
m, n = len(S), len(T)
DP = [[0 for j in range(n+1)] for i in range(m+1)]
for i in range(1, m+1):
    for j in range(1, n+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])
X = ''
i, j = m, n
while len(X) < DP[m][n]:
    if DP[i][j] == DP[i-1][j-1]+1:
        i -= 1
        j -= 1
        l += 1
        X = S[i-1]+X
    elif DP[i][j] == DP[i-1][j]:
        i -= 1
    elif DP[i][j] == DP[i][j-1]:
        j -= 1
print(X)

Buggy submission (verdict: Runtime Error):
S = input()
T = input()
m, n = len(S), len(T)
C = [[0 for j in range(n+1)] for i in range(m+1)]
for i in range(m):
    for j in range(n):
        if S[i] == T[j]:
            C[i+1][j+1] = C[i][j] + 1
        else:
            C[i+1][j+1] = max(C[i][j+1], C[i+1][j])
X = ''
i, j, k = 0, 0, 0
while k < C[m][n]:
    if S[i] == T[j]:
        X = X + S[i]
        i += 1
        j += 1
        k += 1
    elif C[i+1][j] == C[i][j]:
        i += 1
    else:
        j += 1
print(X)
Problem p03166 (python)

Fixed submission:
n, m = map(int, input().split())
G = [[] for i in range(n)]
I = [0 for i in range(n)]
for j in range(m):
    x, y = map(int, input().split())
    G[x-1].append(y-1)
    I[y-1] += 1
# Q:出発点の候補
Q = [i for i in range(n) if I[i] == 0]
# L[i]=iを終点とする最長パスの長さ
L = [0 for i in range(n)]
while Q:
    i = Q.pop()
    while G[i]:
        j = G[i].pop()
        I[j] -= 1
        L[j] = max(L[j], L[i]+1)
        if I[j] == 0:
            Q.append(j)
print(max(L))

Buggy submission (verdict: Runtime Error):
n, m = map(int, input().split())
G = [[] for i in range(n)]
for j in range(m):
    x, y = map(int, input().split())
    G[x-1].append(y-1)
DP = [None for i in range(n)]
def dp(i):
    if DP[i] != None:
        return DP[i]
    ret = 0
    for j in G[i]:
        ret = max(ret, dp(j)+1)
    DP[i] = ret
    return ret
print(max([dp(i) for i in range(n)]))
Problem p03170 (python)

Fixed submission:
n, k = map(int, input().split())
*A, = map(int, input().split())
DP = [False] * (k+1)
for i in range(k+1):
    for a in A:
        if i+a <= k and not DP[i]:
            DP[i+a] = True
if DP[k]:
    print('First')
else:
    print('Second')

Buggy submission (verdict: Runtime Error):
def f(k):
    if k < 0:
        return True
    if k == 0:
        return False
    return any([not f(k-a) for a in A])


n, k = map(int, input().split())
*A, = map(int, input().split())
print(f(k))
Problem p03171 (python)

Fixed submission:
n = int(input())
*A, = map(int, input().split())
DP = [[0 for j in range(n+1)] for i in range(n+1)]
for l in range(1, n+1):
    for i in range(n-l+1):
        DP[i][i+l] = max(A[i]-DP[i+1][i+l], A[i+l-1]-DP[i][i+l-1])
print(DP[0][n])

Buggy submission (verdict: Runtime Error):
n = int(input())
*A, = map(int, input().split())
DP = [[None for j in range(n+1)] for i in range(n)]
def dp(i, j):
    if i == j:
        return 0
    if DP[i][j] != None:
        return DP[i][j]
    DP[i][j] = max(A[i]-dp(i+1, j), A[j-1]-dp(i, j-1))
    return DP[i][j]
print(dp(0, n))

Buggy submission (verdict: Runtime Error):
def dp(i, j):
    if i == j:
        return A[i]
    return max(A[i]-dp(i+1, j), A[j]-dp(i, j-1))


n = int(input())
*A, = map(int, input().split())
print(dp(0, n-1))
Problem p03175 (python)

Fixed submission:
import sys
sys.setrecursionlimit(100000)
n = int(input())
G = [[] for i in range(n)]
for i in range(n-1):
    x, y = map(int, input().split())
    G[x-1].append(y-1)
    G[y-1].append(x-1)
p = 10**9+7
Q = [0]
V = [False for i in range(n)]
C = [[] for i in range(n)]
while Q:
    x = Q.pop()
    V[x] = True
    for y in G[x]:
        if not V[y]:
            C[x].append(y)
            Q.append(y)
DP = [[None, None] for i in range(n)]
def dp(i, c):
    if DP[i][c] != None:
        return DP[i][c]
    tmp = 1
    for j in C[i]:
        if c == 0:
            tmp = (tmp*(dp(j, 0)+dp(j, 1))) % p
        else:
            tmp = (tmp*dp(j, 0)) % p
    DP[i][c] = tmp
    return DP[i][c]
print((dp(0, 0)+dp(0, 1))%p)

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10000)
n = int(input())
G = [[] for i in range(n)]
for i in range(n-1):
    x, y = map(int, input().split())
    G[x-1].append(y-1)
    G[y-1].append(x-1)
p = 10**9+7
Q = [0]
V = [False for i in range(n)]
C = [[] for i in range(n)]
while Q:
    x = Q.pop()
    V[x] = True
    for y in G[x]:
        if not V[y]:
            C[x].append(y)
            Q.append(y)
DP = [[None, None] for i in range(n)]
def dp(i, c):
    if DP[i][c] != None:
        return DP[i][c]
    tmp = 1
    for j in C[i]:
        if c == 0:
            tmp = (tmp*(dp(j, 0)+dp(j, 1))) % p
        else:
            tmp = (tmp*dp(j, 0)) % p
    DP[i][c] = tmp
    return DP[i][c]
print(dp(0, 0)+dp(0, 1))

Buggy submission (verdict: Runtime Error):
n = int(input())
G = [[] for i in range(n)]
for i in range(n-1):
    x, y = map(int, input().split())
    G[x-1].append(y-1)
    G[y-1].append(x-1)
p = 10**9+7
Q = [0]
V = [False for i in range(n)]
C = [[] for i in range(n)]
while Q:
    x = Q.pop()
    V[x] = True
    for y in G[x]:
        if not V[y]:
            C[x].append(y)
            Q.append(y)
DP = [[None, None] for i in range(n)]
def dp(i, c):
    if DP[i][c] != None:
        return DP[i][c]
    tmp = 1
    for j in C[i]:
        if c == 0:
            tmp = (tmp*(dp(j, 0)+dp(j, 1))) % p
        else:
            tmp = (tmp*dp(j, 0)) % p
    DP[i][c] = tmp
    return DP[i][c]
print(dp(0, 0)+dp(0, 1))