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

Fixed submission:
N = int(input())
A = [int(a) for a in input().split()]
    
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

L = [1]*N
for i in range(1, N):
    L[i] *= L[i-1]*i
    L[i] %= mod
    
ans = 0
for i in range(1, N):
    ans += cmb(N-1, N-i, mod)*L[i-1]*L[N-i-1]*(A[N-1]-A[i-1])
    ans %= mod
        
L2 = [0]*(N-1)
for i in range(N-1):
    L2[i] = A[i+1]-A[i]

S = [0]*N
for i in range(N-1):
    S[i+1] = S[i] + L2[i]
    
L3 = [0]*N
for i in range(1, N):
    if N-i-1 >= i:
        L3[i] = L3[i-1] + S[N-i-1] - S[i-1]
    else:
        L3[i] = L3[N-i-1]

for t in range(1, N-1):
    ans += cmb(N-1, t+1, mod)*L[N-t-2]*L[t-1]*L3[t]
    ans %= mod
        
print(ans)

Buggy submission (verdict: Runtime Error):
N = int(input())
A = [int(a) for a in input().split()]
    
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

if N <= 2000:
    L = [1]*N
    for i in range(1, N):
        L[i] *= L[i-1]*i
        L[i] %= mod
    
    ans = 0
    for i in range(1, N):
        ans += cmb(N-1, N-i, mod)*L[i-1]*L[N-i-1]*(A[N-1]-A[i-1])
        ans %= mod
        for j in range(i+1, N):
            ans += cmb(N-1, j-i+1, mod)*L[N-j+i-2]*L[j-i-1]*(A[j-1]-A[i-1])
            ans %= mod
        
print(ans)
Problem p02839 (python)

Fixed submission:
H,W = map(int, input().split())
A = [[int(a) for a in input().split()] for _ in range(H)]
B = [[int(b) for b in input().split()] for _ in range(H)]

C = [[0]*W for _ in range(H)]
num = 80
for i in range(H):
    for j in range(W):
        C[i][j] = abs(A[i][j]-B[i][j])
        
dp = [[0]*W for _ in range(H)]
dp[0][0] |= (1<<num+C[0][0]) | (1<<num-C[0][0])

for i in range(H):
    for j in range(W):
        if i > 0:
            dp[i][j] |= (dp[i-1][j]<<num+C[i][j]) | (dp[i-1][j]<<num-C[i][j])
        if j > 0:
            dp[i][j] |= (dp[i][j-1]<<num+C[i][j]) | (dp[i][j-1]<<num-C[i][j])
            
b = list(bin(dp[-1][-1]))[::-1]
ans = 10**9
for i in range(len(b)):
    if b[i] == "1":
        ans = min(ans, abs(num*(H+W-1)-i))

print(ans)

Buggy submission (verdict: Runtime Error):
H,W = map(int, input().split())
A = [[int(a) for a in input().split()] for _ in range(H)]
B = [[int(b) for b in input().split()] for _ in range(H)]

dp = [[[False]*12802 for _ in range(W)] for _ in range(H)]
t = A[0][0]-B[0][0]
if t < 0:
    dp[0][0][-t*2] = True
    dp[0][0][-t*2-1] = True
elif t > 0:
    dp[0][0][2*t-1] = True
    dp[0][0][2*t] = True
else:
    dp[0][0][0] = True

for i in range(H):
    for j in range(W):
        if i > 0:
            for k in range(12802):
                if dp[i-1][j][k]:
                    if k % 2 == 0:
                        num = -k//2
                    else:
                        num = (k+1)//2
                    num += A[i][j]-B[i][j]
                    if num <= 0:
                        idx = -num*2
                    else:
                        idx = num*2-1
                    dp[i][j][idx] = True
                    num -= (-A[i][j]+B[i][j])*2
                    if num <= 0:
                        idx = -num*2
                    else:
                        idx = num*2-1
                    dp[i][j][idx] = True
        if j > 0:
            for k in range(12802):
                if dp[i][j-1][k]:
                    if k % 2 == 0:
                        num = -k//2
                    else:
                        num = (k+1)//2
                    num += A[i][j]-B[i][j]
                    if num <= 0:
                        idx = -num*2
                    else:
                        idx = num*2-1
                    dp[i][j][idx] = True
                    num += (-A[i][j]+B[i][j])*2
                    if num <= 0:
                        idx = -num*2
                    else:
                        idx = num*2-1
                    dp[i][j][idx] = True
                    
for k in range(12802):
    if dp[H-1][W-1][k]:
        ans = k//2 + k%2
        break
        
print(ans)
Problem p02866 (python)

Fixed submission:
N = int(input())
D = [int(d) for d in input().split()]

f = 0
if D[0] != 0:
    f = -1
mod = 998244353
L = []

num = 0
cnt = 0
D.sort()
for i in range(N):
    if D[i] == num:
        cnt += 1
    elif D[i] == num+1:
        L.append(cnt)
        cnt = 1
        num += 1
    else:
        f = -1
        break
        
L.append(cnt)
ans = 1
if f == 0:
    if D[0] != 0:
        ans = 0
    if N > 1:
        if D[1] != 1:
            ans = 0
    if ans > 0:
        for i in range(1, len(L)):
            ans *= L[i-1]**L[i]
            ans %= mod
else:
    ans = 0
    
print(ans)

Buggy submission (verdict: Runtime Error):
N = int(input())
D = [int(d) for d in input().split()]

D.sort()
mod = 998244353

if D[0] == 0:
    if N == 1:
        ans = 1
    elif D[1] == 1:
        cnt = 0
        num = 1
        ans = 1
        for i in range(1, N):
            if D[i] == num:
                cnt += 1
            elif num == 1:
                prev = cnt
                cnt = 1
                num += 1
            elif D[i] == num+1:
                ans *= prev**cnt
                ans %= mod
                prev = cnt
                cnt = 1
                num += 1
            else:
                ans = 0
                break
        if cnt > 0:
            ans *= prev**cnt
            ans %= mod
    else:
        ans = 0
else:
    ans = 0
    
print(ans)
Problem p02904 (python)

Fixed submission:
import heapq

N,K = map(int, input().split())
P = [int(p) for p in input().split()]

h = []
H = []
for i in range(K):
    heapq.heappush(h, (P[i], i))
    heapq.heappush(H, (-P[i], i))
    
ans = 1
for i in range(N-K):
    while h[0][1] < i:
        heapq.heappop(h)
    while H[0][1] < i:
        heapq.heappop(H)
    heapq.heappush(h, (P[i+K], i+K))
    heapq.heappush(H, (-P[i+K], i+K))
    if h[0][0] == P[i] and -H[0][0] == P[i+K]:
        continue
    ans += 1
    
f = 0
cnt = 1
for i in range(N-1):
    if P[i] < P[i+1]:
        cnt += 1
    else:
        if cnt >= K and f == 1:
            ans -= 1
        elif cnt >= K and f == 0:
            f = 1
        cnt = 1
        
if cnt >= K and f == 1:
    ans -= 1
    
print(ans)

Buggy submission (verdict: Runtime Error):
N,K = map(int, input().split())
P = [int(p) for p in input().split()]

L = [0 for i in range(N-1)]
temp = P[0]
for i in range(1,N):
    if temp > P[i]:
        L[i-1] = 1
    temp = P[i]
    
cnt = 0
for i in range(K-2, N-K+1):
    if L[i] == 1:
        chk = 0
        for j in range(1,K):
            if L[i+j] == L[i-j]:
                chk += 1
            else:
                break
        if chk == K-1:
            cnt += 1
            
zero = []
z = 0
for i in range(N-1):
    if L[i] == 0:
        z += 1
    else:
        zero.append(z)
        z = 0

cnt2 = 0
for i in range(len(zero)):
    if zero[i] >= K-1:
        cnt2 += zero[i]-K+2
        
print(N-K+1-cnt-cnt2)
Problem p02936 (python)

Fixed submission:
N,Q = map(int, input().split())
L = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    L[a-1].append(b-1)
    L[b-1].append(a-1)
cnt = [0]*N
for _ in range(Q):
    p, x = map(int, input().split())
    cnt[p-1] += x

flag = [1]*N
q = [0]
while q:
    temp = q.pop()
    flag[temp] = 0
    for i in L[temp]:
        if flag[i]:
            q.append(i)
            cnt[i] += cnt[temp]
            
print(*cnt)

Buggy submission (verdict: Runtime Error):
N,Q = map(int, input().split())
L = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    L[a-1].append(b-1)
    L[b-1].append(a-1)
cnt = [0]*N
for _ in range(Q):
    p, x = map(int, input().split())
    cnt[p-1] += x


flag = [-1]*N
q = [0]
cnt[0] = qlist[0]
while q:
    temp = q.pop(0)
    for i in L[temp]:
        if flag[i] < 0:
            q.append(i)
            cnt[i] += cnt[temp]
            flag[i] = 1
            
for i in range(N):
    print(cnt[i])

Buggy submission (verdict: Runtime Error):
N,Q = map(int, input().split())

L = [[] for _ in range(N)]
for i in range(N-1):
    a, b = map(int, input().split())
    L[a-1].append(b-1)
    L[b-1].append(a-1)

question = [[int(q) for q in input().split()] for _ in range(Q)]

L = [[] for _ in range(N)]
for i in range(N-1):
    L[edge[i][0]-1].append(edge[i][1]-1)
    L[edge[i][1]-1].append(edge[i][0]-1)
    
qlist = [0]*N
for i in range(Q):
    qlist[question[i][0]-1] += question[i][1]
    
cnt = [-1]*N
q = [[0, qlist[0]]]
cnt[0] = qlist[0]
while q:
    temp = q.pop(0)
    v = temp[0]
    c = temp[1]
    for i in L[v]:
        if cnt[i] < 0:
            q.append([i, c+qlist[i]])
            cnt[i] = c+qlist[i]
            
for i in range(N):
    cnt[i] = str(cnt[i])
print(" ".join(cnt))
Problem p02939 (python)

Fixed submission:
S = input()
N = len(S)
prev = S[0]
ans = 1
i = 1
while i < N:
  ans += 1
  if len(prev) == 2:
    prev = S[i]
    i += 1
    continue
  if prev == S[i] and i < N-1:
    prev = S[i] + S[i+1]
    i += 2
  elif prev == S[i]:
    ans -= 1
    break
  else:
    prev = S[i]
    i += 1
print(ans)

Buggy submission (verdict: Runtime Error):
S = input()
N = len(S)
prev = S[0]
ans = 1
i = 1
while i < N:
  ans += 1
  if len(prev) == 2:
    prev = S[i]
    i += 1
    continue
  if prev == S[i] and i < N-1:
    i += 2
    prev = S[i] + S[i+1]
  elif prev == S[i]:
    ans -= 1
    break
  else:
    prev = S[i]
    i += 1
print(ans)
Problem p02947 (python)

Fixed submission:
N = int(input())
S = [input() for _ in range(N)]

L = ["0"]*N
for i in range(N):
    temp = ["0"]*10
    for j in range(10):
        temp[j] = S[i][j]
    temp.sort()
    L[i] = temp
        
L.sort()
ans = 0
cnt = 1
temp = L[0]
for i in range(1, N):
    if temp == L[i]:
        cnt += 1
    else:
        ans += cnt*(cnt-1)//2
        cnt = 1
        temp = L[i]
        
ans += cnt*(cnt-1)//2
print(ans)

Buggy submission (verdict: Runtime Error):
N = int(input())
A = []
for i in range(N):
    A.append(input())

dic = {}
for i in range(N):
    temp = {}
    for j in range(10):
        if A[i][j] in temp:
            temp[A[i][j]] += 1
        else:
            temp[A[i][j]] = 1
    if dic in temp:
        dic[temp] += 1
    else:
        dic[temp] = 1
        
ans = 0    
for key in dic:
    if dic[key] > 1:
        ans += (dic[key]*(dic[key]-1)//2)

print(ans)
Problem p02953 (python)

Fixed submission:
N = int(input())
H = [int(h) for h in input().split()]

if N == 1:
    ans = "Yes"
else:
    c = 0
    while c <= N-2:
        if H[c] < H[c+1]:
            H[c+1] -= 1
        c += 1
    List = []
    for j in range(N):
        List.append(H[j])
    List.sort()
    if List == H:
        ans = "Yes"
    else:
        ans = "No"

print(ans)

Buggy submission (verdict: Runtime Error):
N = int(input())
H = [int(h) for h in input().split()]

if N == 1:
    ans = "Yes"
else:
    c = 1
    while c <= N-2:
        if H[c] > H[c+1] and H[c-1] < H[c]:
            H[c] -= 1
        elif H[c] == H[c+1] and H[c-1] < H[c]:
            H[c] -= 1
            H[c+1] -= 1
            c += 1
        c += 1
    List = []
    for j in range(N):
        List.append(H[j])
    List.sort()
    if List == H:
        ans = "Yes"
    else:
        ans = "No"

print(ans,List)
Problem p02992 (python)

Fixed submission:
from itertools import accumulate

N,K = map(int, input().split())
mod = 10**9+7
sqt = int(N**0.5)
cnt = [N // i-N // (i+1) for i in range(1, N//sqt)] + [1]*sqt
x = cnt
for _ in range(K):
    x = [(i*j)%mod for i, j in zip(accumulate(reversed(x)), cnt)]
    

print(x[-1])

Buggy submission (verdict: Runtime Error):
N,K = map(int, input().split())

L = [N]
c = 2
while c < N**0.5:
    if L[-1] != N//c:
        L.append(N//c)
    c += 1
if c > N**0.5:
    c -= 1
    L.append(c)
else:
    L.append(c)


L.reverse()
dp = [[0 for j in range(c+len(L))] for i in range(K+1)]

for j in range(1, c+1):
    dp[2][j] = N//j
for j in range(1, len(L)):
    dp[2][j+c] = N//L[j]*(L[j]-L[j-1])

for i in range(2, K):
    dp[i+1][1] = sum(dp[i])
    for j in range(2, c+len(L)):
        dp[i+1][j] = dp[i+1][j-1]-dp[i][len(dp[0])+1-j]
        if j > c:
            dp[i+1][j] *= (L[j]-L[j-1])
#    for j in range(1, len(L)):
#        dp[i+1][j+c] *= (L[j]-L[j-1])
        

print(sum(dp[K])%(10**9+7))
Problem p02995 (python)

Fixed submission:
A,B,C,D = map(int, input().split())

import fractions

g = fractions.gcd(C, D)
E = C*D//g
num = (B//C-(A-1)//C) + (B//D-(A-1)//D) - (B//E-(A-1)//E)
print(B-A+1-num)

Buggy submission (verdict: Runtime Error):
A,B,C,D = map(int, input().split())

import math

g = math.gcd(C, D)
E = C*D//g
num = (B//C-(A-1)//C) + (B//D-(A-1)//D) - (B//E-(A-1)//E)
print(B-A+1-num)
Problem p03046 (python)

Fixed submission:
M,K = map(int, input().split())

if K >= pow(2, M):
    print(-1)
elif K == 0:
    ans = []
    for i in range(pow(2, M)):
        ans.append(i)
        ans.append(i)
    print(*ans)
else:
    num = 0
    L = []
    for i in range(pow(2, M)):
        if i == K:
            continue
        num ^= i
        L.append(i)
    if num == K:
        L2 = list(reversed(L))
        ans = L + [K] + L2 + [K]
        print(*ans)
    else:
        print(-1)

Buggy submission (verdict: Runtime Error):
M,K = map(int, input().split())

if K >= pow(2, M):
    print(-1)
elif K == 0:
    ans = []
    for i in range(pow(2, M)):
        ans.append(i)
        ans.append(i)
    print(*ans)
else:
    num = 0
    L = []
    for i in range(pow(2, M)):
        if i == K:
            continue
        num ^= i
        L.append(i)
    if num == K:
        ans = L + [K] + L.reverse() + [K]
        print(*ans)
    else:
        print(-1)
Problem p03086 (python)

Fixed submission:
S = input()

def AGCT(S,i):
    if S[i] == "A" or S[i] == "T" or S[i] == "G" or S[i] == "C":
        return 0
    else:
        return 1

c = 0
ANS = []
for i in range(len(S)):
    if AGCT(S,i) == 0:
        c += 1
    else:
        ANS.append(c)
        c = 0
ANS.append(c)
print(max(ANS))

Buggy submission (verdict: Runtime Error):
S = input()

def AGCT(S,i):
    if S[i] == "A" or S[i] == "T" or S[i] == "G" or S[i] == "C":
        return 0
    else:
        return 1

c = 0
ANS = []
for i in range(len(S)):
    if AGCT(S,i) == 0:
        c += 1
    else:
        ANS.append(c)
        c = 0
print(max(ANS))
Problem p03087 (python)

Fixed submission:
N,Q = map(int, input().split())
S = input()
L = []
for i in range(Q):
    L.append([int(x) for x in input().split()])
    
ac_list = [0 for i in range(N)]
ac_num = 0
for i in range(1, N):
    pre = S[i-1]
    ac_list[i] = ac_list[i-1]
    if pre == "A" and S[i] == "C":
        ac_num += 1
        ac_list[i] = ac_num

for i in range(Q):
    ans = ac_list[L[i][1]-1] - ac_list[L[i][0]-1]
    print(ans)

Buggy submission (verdict: Runtime Error):
N,Q = map(int, input().split())
S = input()
L = []
for i in range(Q):
    L.append([int(a) for a in input().split()])

Temp = [0 for i in range(N)]
num = 0
while num <= N-2:
    if S[num] == "A" and S[num+1] == "C":
        Temp[num] = 1
        Temp[num+1] = 2
    num += 1

for j in range(Q):
    Temp2 = Temp[L[j][0]-1:L[j][1]]
    c = sum(Temp2)
    if c%3 == 0:
        if Temp2[0] != 2
            print(int(c/3))
        else:
            print(int(c/3-1))
    elif c%3 == 1:
        print(int((c-1)/3))
    else:
        print(int((c-2)/3))
Problem p03088 (python)

Fixed submission:
N = int(input())

C = 10**9+7
n = 5
num = max(N+1, 6)
L = [0 for i in range(num)]
X = [0 for i in range(num)]
Y = [0 for i in range(num)]
Z = [0 for i in range(num)]
W = [0 for i in range(num)]
G = [0 for i in range(num)]
L[3] = 61
L[4] = 230
X[3] = 3
X[4] = 12
Y[3] = 4
Y[4] = 16
Z[3] = 4
Z[4] = 15
W[3] = 3
W[4] = 12
W[5] = 48
G[3] = 15
G[4] = 58
while n <= N:
    L[n] = 4*L[n-1] - (X[n-1]+Y[n-1]+Z[n-1]+W[n-1])
    G[n] = L[n-1]-X[n-1]
    X[n] = L[n-2]-G[n-2]
    Y[n] = L[n-2]
    Z[n] = L[n-2]-X[n-2]
    if n > 5:
        W[n] = L[n-3]*3
    n += 1

print(L[N]%C)

Buggy submission (verdict: Runtime Error):
N = int(input())

C = 10**9+7
n = 5
L = [0 for i in range(N+1)]
X = [0 for i in range(N+1)]
Y = [0 for i in range(N+1)]
Z = [0 for i in range(N+1)]
W = [0 for i in range(N+1)]
G = [0 for i in range(N+1)]
L[3] = 61
L[4] = 230
X[3] = 3
X[4] = 12
Y[3] = 4
Y[4] = 16
Z[3] = 4
Z[4] = 15
W[3] = 3
W[4] = 12
W[5] = 48
G[3] = 15
G[4] = 58
while n <= N:
    L[n] = 4*L[n-1] - (X[n-1]+Y[n-1]+Z[n-1]+W[n-1])
    G[n] = L[n-1]-X[n-1]
    X[n] = L[n-2]-G[n-2]
    Y[n] = L[n-2]
    Z[n] = L[n-2]-X[n-2]
    if n > 5:
        W[n] = L[n-3]*3
    n += 1

print(L[N]%C)
Problem p03128 (python)

Fixed submission:
N,M = map(int, input().split())
A = [int(a) for a in input().split()]

data = {1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6}
inf = -10**9
dp = [inf for i in range(N+1)]
dp[0] = 0
for i in range(1, N+1):
    for j in range(M):
        if i-data[A[j]] >= 0:
            dp[i] = max(dp[i], dp[i-data[A[j]]]+1)
            
ans = 0
A.sort(reverse=True)
n = dp[N]
i = n-1
temp = N
while i >= 0:
    j = 0
    while j < M:
        if temp-data[A[j]] >= 0:
            if dp[temp-data[A[j]]] == dp[temp]-1:
                temp -= data[A[j]]
                temp = max(temp, 0)
                ans += A[j]*10**i
                j = M
        j += 1
    i -= 1
    
print(ans)

Buggy submission (verdict: Runtime Error):
N,M = map(int, input().split())
A = [int(a) for a in input().split()]

data = {1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6}
inf = -10**9
dp = [inf for i in range(N+1)]
dp[0] = 0
for i in range(1, N+1):
    for j in range(M):
        if i-data[A[j]] >= 0:
            dp[i] = max(dp[i], dp[i-data[A[j]]]+1)
            
ans = 0
A.sort(reverse=True)
n = dp[N]
i = n-1
temp = N
while i >= 0:
    j = 0
    while j < M:
        if dp[temp-data[A[j]]] == dp[temp]-1:
            temp -= data[A[j]]
            ans += A[j]*10**i
            j = M
        j += 1
    i -= 1
    
print(ans)
Problem p03138 (python)

Fixed submission:
N,K = map(int, input().split())
A = [int(a) for a in input().split()]

d = 50
L = [0]*d
for i in range(N):
    b = list(bin(A[i]))
    for j in range(2, len(b)):
        if b[j] == "1":
            L[len(b)-j-1] += 1

X0 = [0]*d
X1 = [0]*d
for i in range(d):
    X0[i] = 2**i*L[i]
    X1[i] = 2**i*(N-L[i])
    
ans = 0
    
Kb = list(bin(K))
for i in range(2, len(Kb)):
    if Kb[i] == "0":
        continue
    c = 0
    for j in range(2, len(Kb)):
        if j < i:
            if Kb[j] == "0":
                c += X0[len(Kb)-1-j]
            else:
                c += X1[len(Kb)-1-j]
        elif j == i:
            c += X0[len(Kb)-1-j]
        else:
            c += max(X0[len(Kb)-1-j], X1[len(Kb)-1-j])
    ans = max(ans, c)
    
for i in range(len(Kb)-2, d):
    ans += X0[i]
    
c = 0
for i in range(N):
    c += K^A[i]
    
ans = max(ans, c)
print(ans)

Buggy submission (verdict: Runtime Error):
N,K = map(int, input().split())
A = [int(a) for a in input().split()]

d = 50
L = [0]*d
for i in range(N):
    b = list(bin(A[i]))
    for j in range(2, len(b)):
        if b[j] == "1":
            L[len(b)-j-1] += 1

X0 = [0]*d
X1 = [0]*d
for i in range(d):
    X0[i] = 2**i*L[i]
    X1[i] = 2**i*(N-L[i])
    
ans = 0
    
Kb = list(bin(K))
for i in range(2, len(Kb)):
    if K[i] == "0":
        continue
    c = 0
    for j in range(2, len(b)):
        if j < i:
            if Kb[j] == "0":
                c += X0[len(Kb)-1-j]
            else:
                c += X1[len(Kb)-1-j]
        elif j == i:
            c += X0[len(Kb)-1-j]
        else:
            c += max(X0[len(Kb)-1-j], X1[len(Kb)-1-j])
    ans = max(ans, c)
    
for i in range(len(Kb)-2, d):
    ans += X0[i]
    
c = 0
for i in range(N):
    c += K^A[i]
    
ans = max(ans, c)
print(ans)

Buggy submission (verdict: Runtime Error):
N,K = map(int, input().split())
A = [int(a) for a in input().split()]

A.sort(reverse=True)
X = A[0]
for i in range(1,N):
    X = (X^A[i])

temp = bin(X)
temp = temp[::-1]
List = []
for i in range(len(temp)-2):
    List.append(temp[i])
while X > K:
    index = List.index(1)
    List[index] = 0
    X = 0
    for j in range(len(List)):
        X += (List[j]*2**j)
        
ans = 0
for l in range(N):
    ans += (A[l]^X)

print(ans)
Problem p03171 (python)

Fixed submission:
N = int(input())
A = [int(a) for a in input().split()]

dp = [[0]*N for _ in range(N)]
        
for k in range(N):
    for i in range(N-k):
        if k == 0:
            dp[i][i] = A[i]
            continue
    
        dp[i][i+k] = max(A[i]-dp[i+1][i+k], A[i+k]-dp[i][i+k-1])

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

Buggy submission (verdict: Runtime Error):
N = int(input())
A = [int(a) for a in input().split()]

dpmax = [[0]*N for _ in range(N)]
dpmin = [[0]*N for _ in range(N)]
        
def f(i, j, t):
    if i > j or i < 0 or i >= N or j < 0 or j >= N:
        return 0
    
    if i == j:
        if t == 0:
            dpmin[i][j] = -A[i]
            return -A[i]
        if t == 1:
            dpmax[i][j] = A[i]
            return A[i]
        
    if t == 0 and dpmin[i][j] > 0:
        return dpmin[i][j]
    elif t == 1 and dpmax[i][j] > 0:
        return dpmax[i][j]
    
    if t == 0:
        dpmin[i][j] = min(-A[i]+f(i+1, j, 1), -A[j]+f(i, j-1, 1))
        return dpmin[i][j]
    else:
        dpmax[i][j] = max(A[i]+f(i+1, j, 0), A[j]+f(i, j-1, 0))
        return dpmax[i][j]

ans = f(0, N-1, 1)
print(ans)

Buggy submission (verdict: Runtime Error):
N = int(input())
A = [int(a) for a in input().split()]

dpmax = [[0]*N for _ in range(N)]
dpmin = [[0]*N for _ in range(N)]
        
def f(i, j, t):
    if i > j or i < 0 or j >= N:
        return 0
    
    if i == j:
        if t == 0:
            dpmin[i][j] = -A[i]
            return -A[i]
        if t == 1:
            dpmax[i][j] = A[i]
            return A[i]
        
    if t == 0 and dpmin[i][j] > 0:
        return dpmin[i][j]
    elif t == 1 and dpmax[i][j] > 0:
        return dpmax[i][j]
    
    if t == 0:
        dpmin[i][j] = min(-A[i]+f(i+1, j, 1), -A[j]+f(i, j-1, 1))
        return dpmin[i][j]
    else:
        dpmax[i][j] = max(A[i]+f(i+1, j, 0), A[j]+f(i, j-1, 0))
        return dpmax[i][j]

ans = f(0, N-1, 1)
print(ans)
Problem p03175 (python)

Fixed submission:
from collections import deque
import sys
sys.setrecursionlimit(10**6)

N = int(input())
E = [[] for _ in range(N)]
for _ in range(N-1):
    x,y = map(int, input().split())
    E[x-1].append(y-1)
    E[y-1].append(x-1)
    
parents = [-1]*N
q = deque()
q.append(0)
while q:
    t = q.popleft()
    for i in E[t]:
        if i == parents[t]:
            continue
        q.append(i)
        parents[i] = t
        
mod = 10**9+7
dp = [[1]*2 for _ in range(N)]
flag = [0]*N

def f(v, j):
    if flag[v]:
        return dp[v][j]
    flag[v] = 1
    for i in E[v]:
        if i == parents[v]:
            continue
        dp[v][0] *= (f(i, 0) + f(i, 1))
        dp[v][1] *= f(i, 0)
        dp[v][0] %= mod
        dp[v][1] %= mod
    return dp[v][j]

print((f(0, 0)+f(0, 1))%mod)

Buggy submission (verdict: Runtime Error):
from collections import deque
from functools import lru_cache
import sys
sys.setrecursionlimit(10**5)

N = int(input())
E = [[] for _ in range(N)]
for _ in range(N-1):
    x,y = map(int, input().split())
    E[x-1].append(y-1)
    E[y-1].append(x-1)
    
parents = [-1]*N
q = deque()
q.append(0)
while q:
    t = q.popleft()
    for i in E[t]:
        if i == parents[t]:
            continue
        q.append(i)
        parents[i] = t
        
mod = 10**9+7
dp = [[1]*2 for _ in range(N)]
flag = [0]*N

@lru_cache(maxsize=None)
def f(v, j):
    if flag[v]:
        return dp[v][j]
    flag[v] = 1
    for i in E[v]:
        if i == parents[v]:
            continue
        dp[v][0] *= (f(i, 0) + f(i, 1))
        dp[v][1] *= f(i, 0)
        dp[v][0] %= mod
        dp[v][1] %= mod
    return dp[v][j]

print((f(0, 0)+f(0, 1))%mod)