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

Fixed submission:
N, M = (int(i) for i in input().split())
A = [int(i) for i in input().split()]
A.sort(reverse=True)
As = [0]*(N+1)
for i in range(N):
    As[i+1] = As[i] + A[i]
A.reverse()

import bisect

def flag(x):
    ans = 0
    for i in range(N):
        a = x - A[i]
        res = bisect.bisect_left(A, a)
        ans += (N-res)
    return bool(ans >= M)

def an(x):
    ans = 0
    m = 0
    for i in range(N):
        a = x - A[i]
        res = bisect.bisect_left(A, a)
        m += (N-res)
        ans += As[N-res]
        ans += A[i] * (N-res)
    ans -= (m - M) * x
    return ans


low = 0
high = 10**6

while low <= high:
    mid = (low + high) // 2
    if flag(mid):
        if not flag(mid+1):
            ans = mid
            break
        else:
            low = mid + 1
    else:
        high = mid - 1

print(an(ans))

Buggy submission (verdict: Runtime Error):
N, M = (int(i) for i in input().split())
A = [int(i) for i in input().split()]
A.sort(reverse=True)
As = [0]*(N+1)
for i in range(N):
    As[i+1] = As[i] + A[i]
A.reverse()

import bisect

def flag(x):
    ans = 0
    for i in range(N):
        a = x - A[i]
        res = bisect.bisect_left(A, a)
        ans += (N-res)
    return bool(ans >= M)

def an(x):
    ans = 0
    m = 0
    for i in range(N):
        a = x - A[i]
        res = bisect.bisect_left(A, a)
        m += (N-res)
        ans += As[N-res]
        ans += A[i] * (N-res)
    ans -= (m - M) * x
    return ans


low = 0
high = 10**5 + 100

while low <= high:
    mid = (low + high) // 2
    if flag(mid):
        if not flag(mid+1):
            ans = mid
            break
        else:
            low = mid + 1
    else:
        high = mid - 1

print(an(ans))
Problem p03096 (python)

Fixed submission:
N = int(input())
DP = [0] * (N+1)
DP[0] = 1
su = [0] * (2*(10**5)+1)
prev = None
MOD = 10**9+7
for i in range(N):
    C = int(input())
    if prev == C:
        DP[i+1] = DP[i]
    else:
        su[C] += DP[i]
        su[C] %= MOD
        DP[i+1] = su[C]
    DP[i+1] %= MOD
    prev = C
print(DP[N])

Buggy submission (verdict: Runtime Error):
N = int(input())
DP = [0] * (N+1)
DP[0] = 1
su = [0] * (2*(10**5))
prev = None
for i in range(N):
    C = int(input())
    if prev == C:
        DP[i+1] = DP[i]
    else:
        su[C] += DP[i]
        DP[i+1] = su[C]
    prev = C
print(DP[N])
Problem p03138 (python)

Fixed submission:
N, K = (int(i) for i in input().split())
A = [int(i) for i in input().split()]
A = [format(a,'b').zfill(40) for a in A]
C = [0]*40
for i in range(40):
    cc = 0
    for a in A:
        keta = 39 - i
        if a[keta] == "1":
            cc += 1
    C[keta] = cc
ans = 0
for i in range(40):
    b = 39 - i
    if C[i] < N - C[i]:#0の方が個数が多い→1を採用したいとき
        if K < 2**b:
            ans += (2**b * C[i])
        else:
            ans += (2**b * (N-C[i]))
            K -= 2**b
    else:
        ans += (2**b * C[i])
print(ans)

Buggy submission (verdict: Runtime Error):
N, K = (int(i) for i in input().split())
A = [int(i) for i in input().split()]
C = [[0]*2 for i in range(40)]
for i in range(40):
  cc = 0
  for a in A:
    if a & (2**(39-i)):
      cc += 1
  C[i][0] = cc * 2**(39-i)
  C[i][1] = (N-cc) * 2**(39-i)
INF = float("inf")
dp = [[-INF]*2 for i in range(41)]
dp[0][0] = 0
for i in range(40):
  d = (K>>(39-i))&1
  dp[i+1][0] = dp[i][0] + C[i][d]
  dp[i+1][1] = dp[i][1] + max(C[i])
  if d == 1:
    dp[i+1][1] = max(dp[i][0] + C[i][0], dp[i+1][1]
print(max(dp[40]))

Buggy submission (verdict: Runtime Error):
N, K = (int(i) for i in input().split())
A = [int(i) for i in input().split()]
C = [0]*40
for i in range(40):
  for a in A:
    if a & (2**(39-i)):
      C[i] += 1
dp = [[0]*2 for in range(41)]
for i in range(40):
  if K ＆ (2**(39-i)):
    temp1 = dp[i][0] + 2**(39-i)*C[i]
    temp2 = dp[i][1] + 2**(39-i)*max(C[i],N-C[i])
    dp[i+1][1] = max(temp1, temp2)
    dp[i+1][0] = dp[i][1] + 2**(39-i)*(N-C[i])
  else:
    dp[i+1][1] =  dp[i][1] + 2**(39-i)*max(C[i],N-C[i])
    dp[i+1][0] = dp[i][0] + 2**(39-i)*C[i]
print(max(dp[40]))
Problem p03146 (python)

Fixed submission:
s = int(input())
if s == 1 or s == 2:
    print(4)
else:
    res = 1
    while True:
        if s == 4:
            break
        else:
            if s % 2 == 0:
                s = s // 2
            else:
                s = 3 * s + 1
            res += 1

    print(res+3)

Buggy submission (verdict: Runtime Error):
s = int(input())
if s == 1 or s == 2:
    print(4)
    res = 1
else:
    while True:
        if s == 4:
            break
        else:
            if s % 2 == 0:
                s = s // 2
            else:
                s = 3 * s + 1
            res += 1

    print(res+3)
Problem p03148 (python)

Fixed submission:
N, K = (int(i) for i in input().split())
L = []
for i in range(N):
    t,d = (int(i) for i in input().split())
    L.append((t,d))

L = sorted(L, key = lambda x:(x[0], -x[1]))
for i in range(N):
    if i == 0:
        ra = 0
        L[i] = (L[i][0], L[i][1], ra)
    else:
        if L[i][0] == L[i-1][0]:
            ra += 1
        else:
            ra = 0
        L[i] = (L[i][0], L[i][1], ra)

L = sorted(L, key = lambda x:(-x[1], x[0]))

if N != K:
    kouho = L[:K]
    amari = L[K:]
else:
    kouho = L
    
nowval = len(set([sushi[0] for sushi in kouho]))
nowder = sum([sushi[1] for sushi in kouho])
point = nowval ** 2 + nowder

if N == K:
    print(point)
else:
    weaks = []
    for sushi in kouho:
        if sushi[2] > 0:
            weaks.append(sushi)
    weaks.reverse()
    kaburan = []
    for sushi in amari:
        if sushi[2] == 0:
            kaburan.append(sushi)
    
    ma = min(len(weaks), len(kaburan))
    newpoint = point
    if ma:
        for i in range(ma):
            newpoint = newpoint - weaks[i][1] + kaburan[i][1]
            newpoint = newpoint - nowval ** 2 + (nowval + 1) ** 2
            nowval += 1
            point = max(point, newpoint)
        print(point)
    else:
        print(point)

Buggy submission (verdict: Runtime Error):
N, K = (int(i) for i in input().split())
L = []
for i in range(N):
    t,d = (int(i) for i in input().split())
    L.append((t,d))

L = sorted(L, key = lambda x:(x[0], -x[1]))
for i in range(N):
    if i == 0:
        ra = 0
        L[i] = (L[i][0], L[i][1], ra)
    else:
        if L[i][0] == L[i-1][0]:
            ra += 1
        else:
            ra = 0
        L[i] = (L[i][0], L[i][1], ra)

L = sorted(L, key = lambda x:(-x[1], x[0]))

if N != K:
    kouho = L[:K]
    amari = L[K:]
else:
    kouho = L
    
nowval = len(set([sushi[0] for sushi in kouho]))
nowder = sum([sushi[1] for sushi in kouho])
point = nowval ** 2 + nowder

if N == K:
    print(point)
else:
    weaks = []
    for sushi in kouho:
        if sushi[2] > 0:
            weaks.append(sushi)
    weaks.reverse()
    kaburan = []
    for sushi in amari:
        if sushi[2] == 0:
            kaburan.append(sushi)
    
    ma = max(len(weaks), len(kaburan))
    newpoint = point
    for i in range(ma):
        newpoint = newpoint - weaks[i][1] + kaburan[i][1]
        newpoint = newpoint - nowval ** 2 + (nowval + 1) ** 2
        nowval += 1
        point = max(point, newpoint)
    print(point)
Problem p03436 (python)

Fixed submission:
import sys

H, W = ( int(i) for i in input().split() )
S = [input() for i in range(H)]

cc = 0
for ss in S:
    for st in ss:
        if st == ".":
            cc += 1

for i in range(len(S)):
    S[i] = "#" + S[i] + "#"

temp = ["#" * (W + 2)]
S = temp + S + temp

dd = [[float("inf")] * W for i in range(H)]

def DFS(a, b, d):
    dd[a-1][b-1] = d
    for x, y in [(a+1, b), (a-1, b), (a, b+1), (a, b-1)]:
        if S[x][y] == "#":
            continue
        else:
            if dd[x-1][y-1] > d + 1:
                DFS(x, y, d + 1)

sys.setrecursionlimit(10000)

DFS(1,1,0)
if dd[H-1][W-1] != float("inf"):
    print(cc - dd[H-1][W-1] -1)
else:
    print("-1")

Buggy submission (verdict: Runtime Error):
H, W = ( int(i) for i in input().split() )
S = [input() for i in range(H)]

cc = 0
for ss in S:
    for st in ss:
        if st == ".":
            cc += 1

for i in range(len(S)):
    S[i] = "#" + S[i] + "#"

temp = ["#" * (W + 2)]
S = temp + S + temp

dd = [[float("inf")] * W for i in range(H)]

def DFS(a, b, d):
    dd[a-1][b-1] = d
    for x, y in [(a+1, b), (a-1, b), (a, b+1), (a, b-1)]:
        if S[x][y] == "#":
            continue
        else:
            if dd[x-1][y-1] > d + 1:
                DFS(x, y, d + 1)

DFS(1,1,0)

print(cc - dd[H-1][W-1] -1)
Problem p03472 (python)

Fixed submission:
N, H = ( int(i) for i in input().split() )
ka = []
kb = []
for i in range(N):
	a, b = ( int(i) for i in input().split() )
	ka.append(a)
	kb.append(b)
	
kb.sort()
kb.reverse()
ma = max(ka)

hp = H
res = 0
for b in kb:
	if b < ma:
		continue
	hp = hp - b
	res += 1
	if hp <= 0:
		break
else:
	res += (hp + ma - 1)//ma
	
print(res)

Buggy submission (verdict: Runtime Error):
N, H = ( int(i) for i in input().split() )
ka = []
kb = []
for i in range(N):
	a, b = ( int(i) for i in input().split() )
	ka.append(a)
	kb.append(b)
	
kb.sort()
kb.reverse()

hp = H
res = 0
for b in kb:
	if b < max(a):
		continue
	hp = hp - b
	res += 1
	if hp <= 0:
		break
else:
	res += (hp + max(ka) - 1)//max(ka)
	
print(res)
Problem p03504 (python)

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

N, C = (int(i) for i in input().split())

pp = [[0] * 100001 for i in range(C)]

for i in range(N):
    s, t, c = (int(i) for i in input().split())
    for j in range(s, t+1):
        pp[c-1][j] = 1

res = 0
for i in range(100001):
    cc = 0
    for j in range(C):
        if pp[j][i]:
            cc += 1
    res = max(res, cc)

print(res)

Buggy submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline

N, C = (int(i) for i in input().split())

pp = [[0] * 100000 for i in range(C)]

for i in range(N):
    s, t, c = (int(i) for i in input().split())
    for j in range(s, t+1):
        pp[c-1][j] = 1

res = 0
for i in range(100000):
    cc = 0
    for j in range(C):
        if pp[j][i]:
            cc += 1
    res = max(res, cc)

print(res)
Problem p03565 (python)

Fixed submission:
Sdash = str(input())
T = str(input())

reslis = []

if len(Sdash) >= len(T):
    for i in range(len(Sdash) - len(T) + 1):
        res = Sdash
        temp = Sdash[i:i+len(T)]
        for k in range(len(T)):
            if T[k] == temp[k] or temp[k] == "?":
                res = list(res)
                res[k+i] = T[k]
                res = "".join(res)
            else:
                break
        else:
            reslis.append(res) 

if reslis:
    reslis = [st.replace("?", "a") for st in reslis]
    print(min(reslis))
else:
    print("UNRESTORABLE")

Buggy submission (verdict: Runtime Error):
Sdash = str(input())
T = str(input())

reslis = []
N = len(Sdash) - len(T) + 1
for i in range(N):
    Tdash = Sdash[i:i+len(T)]
    for j in range(len(T)):
        if Tdash[j] == T[j] or Tdash[j] == "?":
            pass
        else:
            break
    else:
        if i == 0:
            reslis.append(T + Sdash[i+len(T)])
        elif i == N - 1:
            reslis.append(Sdash[:i] + T)
        else:
            reslis.append(Sdash[:i] + T + Sdash[i+len(T)])

if reslis:
    reslis = [st.replace("?","a") for st in reslis]
    reslis.sort()
    print(reslis[0])

else:
    print("UNRESTORABLE")

Buggy submission (verdict: Runtime Error):
Sdash = str(input())
T = str(input())

reslis = []
N = len(Sdash) - len(T) + 1
for i in range(N):
    Tdash = Sdash[i:i+len(T)]
    for j in range(len(T)):
        if Tdash[j] == T[j] or Tdash[j] == "?":
            pass
        else:
            break
    else:
        print(Tdash)
        if i == 0:
            reslis.append(T + Sdash[i+len(T)])
        elif i == N - 1:
            reslis.append(Sdash[:i] + T)
        else:
            reslis.append(Sdash[:i] + T + Sdash[i+len(T)])

if reslis:
    reslis = [st.replace("?","a") for st in reslis]
    reslis.sort()
    print(reslis[0])

else:
    print("UNRESTORABLE")
Problem p03633 (python)

Fixed submission:
def kouyaku(a,b):
    aa = max(a,b)
    bb = min(a,b)
    if bb == 0:
        return aa
    else:
        return kouyaku(bb,aa%bb)

N = int(input())
T = []
for i in range(N):
    T.append(int(input()))

T.sort()

ans = T[0]
for time in T:
    kou = kouyaku(ans, time)
    if kou != time:
        ans = ans//kou * time
    
print(ans)

Buggy submission (verdict: Runtime Error):
def kouyaku(a,b):
    aa = max(a,b)
    bb = min(a,b)
    if bb == 0:
        return aa
    else:
        return kouyaku(bb,aa%bb)

N = int(input())
T = []
for i in range(N):
    T.append(int(input()))

ans = T[0]
for time in T:
    ans = int( ans / kouyaku(ans, time) * time)
    
print(ans)

Buggy submission (verdict: Runtime Error):
def kouyaku(a,b):
    aa = max(a,b)
    bb = min(a,b)
    if bb == 0:
        return aa
    else:
        return kouyaku(bb,aa%bb)

N = int(input())
T = []
for i in range(N):
    T.append(int(input()))

ans = 0
for time in T:
    if ans:
        ans = int( ans * time / kouyaku(ans, time) )
    else:
        ans = time
    
print(ans)

Buggy submission (verdict: Runtime Error):
def kouyaku(a,b):
    aa = max(a,b)
    bb = min(a,b)
    if bb == 0:
        return aa
    else:
        return kouyaku(bb,aa%bb)

N = int(input())
T = []
for i in range(N):
    T.append(int(input()))

T.sort()
T.reverse()

ans = 0
for time in T:
    if ans:
        ans = int( ans * time / kouyaku(ans, time) )
    else:
        ans = time
    
print(ans)
Problem p03639 (python)

Fixed submission:
N = int(input())
A = [int(i) for i in input().split()]
c4=0
c2=0
for i in range(N):
  if A[i]%4==0:
    c4+=1
  elif A[i]%2==0:
    c2+=1
if c4:
  a = c4*2+1
else:
  a = 0
if c2>1:
  b = c2
  if a:
    a -= 1
else:
  b = 0
if a+b>=N:
  print("Yes")
else:
  print("No")

Buggy submission (verdict: Runtime Error):
H, W = (int(i) for i in input().split())
N = int(input())
A = [int(i) for i in input().split()]
C = []
for i in range(N):
  for j in range(A[i]):
    C.append(i+1)
ans = [[0]*W for i in range(H)]
for i in range(H*W):
  y = i // W
  if y%2==0:
    x = i%W
  else:
    x = W-1-i%W
  ans[x][y] = C[i]
for i in range(H):
  ans[i] = [str(a) for a in ans[i]]
  print(" ".join(ans[i]))

Buggy submission (verdict: Runtime Error):
N = int(input())
A = [int(i) for i in input().split()]
c4=0
c2=0
for i in range(N):
  if A[i]%4==0:
    c4+=1
  elif A[i]%2==0:
    c2+=1
if c4:
  a = c4*2+1
else:
  a = 0
if c2>1:
  b = c2b
  if a:
    a -= 1
else:
  b = 0
if a+b>=N:
  print("Yes")
else:
  print("No")
Problem p03640 (python)

Fixed submission:
H, W = (int(i) for i in input().split())
N = int(input())
A = [int(i) for i in input().split()]
C = []
for i in range(N):
  for j in range(A[i]):
    C.append(i+1)
ans = [[0]*W for i in range(H)]
for i in range(H*W):
  y = i // W
  if y%2==0:
    x = i%W
  else:
    x = W-1-i%W
  ans[y][x] = C[i]
for i in range(H):
  ans[i] = [str(a) for a in ans[i]]
  print(" ".join(ans[i]))

Buggy submission (verdict: Runtime Error):
H, W = (int(i) for i in input().split())
N = int(input())
A = [int(i) for i in input().split()]
C = []
for i in range(N):
  for j in range(A[i]):
    C.append(i+1)
ans = [[0]*W for i in range(H)]
for i in range(H*W):
  y = i // W
  if y%2==0:
    x = i%W
  else:
    x = W-1-i%W
  ans[x][y] = C[i]
for i in range(H):
  ans[i] = [str(a) for a in ans[i]]
  print(" ".join(ans[i]))

Buggy submission (verdict: Runtime Error):
H, W = (int(i) for i in input().split())
N = int(input())
A = [int(i) for i in input().split()]
C = []
for i in range(N):
  for j in range(a[i]):
    C.append(i+1)
ans = [[0]*W for i in range(H)]
for i in range(HW):
  y = i // W
  if y%2==0:
    x = i%W
  else:
    x = W-1-i%W
  ans[x][y] = C[i]
for i in range(H):
  ans[i] = [str(a) for a in ans]
  print(" ".join(ans[i]))
Problem p03648 (python)

Fixed submission:
K = int(input())
ans = [K//50 + i for i in range(50)]
if K%50:
  for i in range(K%50):
    ans[i] += 51
    ans = [a-1 for a in ans]
print(50)
ans = [str(a) for a in ans]
print(" ".join(ans))

Buggy submission (verdict: Runtime Error):
K = int(input())
ans = [K//50 + i for i in range(50)]
if K%50:
  for i in range(K%50):
    ans[i] += 50
print(50)
print(" ".join(ans))

Buggy submission (verdict: Runtime Error):
K = int(input())
ans = [K//50 + i for i in range(50)]
if K%50:
  for i in range(K%50):
    ans[i] += N
print(50)
print(" ".join(ans))
Problem p03662 (python)

Fixed submission:
import sys
sys.setrecursionlimit(100000)

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

prev = [-1]*N
def DFS(start):
    res = 0
    for u in G[start]:
        if u != prev[start]:
            prev[u] = start
            res += DFS(u)
    return res+1

DFS(0)
start = N-1
path = [N-1]
while True:
    path.append(prev[start])
    start = prev[start]
    if start == 0:
        break
path.reverse()
num = len(path)
c, d = (path[(num+1)//2-1], path[(num+1)//2])
G[c].remove(d)
G[d].remove(c)
prev = [-1]*N
DFS0 = DFS(0)
prev = [-1]*N
if DFS0 > DFS(N-1):
    print("Fennec")
else:
    print("Snuke")

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

prev = [-1]*N
dp = [0]*(N+1)
def DFS(start):
    res = 0
    for u in G[start]:
        if u != prev[start]:
            prev[u] = start
            res += DFS(u)
    dp[start] = res+1
    return res+1

DFS(0)
start = N-1
path = [N-1]
while True:
    path.append(prev[start])
    start = prev[start]
    if start == 0:
        break
path.reverse()
num = len(path)
c, d = (path[(num+1)//2-1], path[(num+1)//2])
G[c].remove(d)
G[d].remove(c)
if DFS(0) > DFS(N-1):
    print("Fennec")
else:
    print("Snuke")
Problem p03734 (python)

Fixed submission:
N, W = (int(i) for i in input().split())
w = [0]*N
v = [0]*N
for i in range(N):
  w[i], v[i] = (int(j) for j in input().split())
w0 = w[0]
wh = [a - w0 for a in w]
dp = [[[-1]*(N+1) for i in range(3*N+1)] for j in range(N+1)]
dp[0][0][0] = 0
for i in range(N):
  for j in range(3*N+1):
    for k in range(N+1):
      if dp[i][j][k] != -1:
        dp[i+1][j][k] = max(dp[i+1][j][k], dp[i][j][k])
      if j - wh[i] >=0 and k-1 >=0 and dp[i][j-wh[i]][k-1] != -1:
        dp[i+1][j][k] = max(dp[i+1][j][k], dp[i][j-wh[i]][k-1]+v[i])
res = 0
for j in range(3*N+1):
  for k in range(N+1):
    if j + w0*k <= W:
      res = max(dp[N][j][k], res)
print(res)

Buggy submission (verdict: Runtime Error):
N, W = (int(i) for i in input().split())
w = [0]*N
v = [0]*N
for i in range(N):
  w[i], v[i] = (int(j) for j in input().split())
w0 = w[0]
wh = [a - w0 for a in w]
dp = [[[-1]*(N+1) for i in range(3*N+1)] for j in range(N+1)]
dp[0][0][0] = 0
for i in range(N):
  for j in range(3*N+1):
    for k in range(N+1):
      if dp[i][j][k] != -1:
        dp[i+1][j][k] = max(dp[i+1][j][k], dp[i][j][k])
      if j - wh[i] >=0 and k-1 >=0 and dp[i][j-wh[i]][k-1] != -1:
        dp[i+1][j][k] = max(dp[i+1][j][k], dp[i][j-wh[i]][k-1]+v[i])
res = 0
for k in range(N+1):
  if w0*k <= W:
    Wk = W - w0*k
    ans = 0
    for j in range(Wk+1):
      ans = max(dp[N][j][k], ans)
    res = max(res, ans)
print(res)

Buggy submission (verdict: Runtime Error):
N, W = (int(i) for i in input().split())
w = [0]*N
v = [0]*N
for i in range(N):
  w[i], v[i] = (int(j) for j in input().split())
w0 = w[0]
wh = [a - w0 for a in w]
dp = [[[-1]*(N+1) for i in range(3*N+1)] for j in range(N+1)]
dp[0][0][0] = 0
for i in range(N):
  for j in range(3*N+1):
    for k in range(N+1):
      if dp[i][j][k] != -1:
        dp[i+1][j][k] = max(dp[i+1][j][k], dp[i][j][k])
      if j - wh[i] >=0 and k-1 >=0 and dp[i][j-wh[i]][k-1] != -1:
        dp[i+1][j][k] = max(dp[i+1][j][k], dp[i][j-wh[i]][k-1]+v[i])
res = 0
for j in range(3*N+1):
  for k in range(N+1)
  	if j + w0*k <= W:
      res = max(dp[N][j][k], res)
print(res)

Buggy submission (verdict: Runtime Error):
N, W = (int(i) for i in input().split())
w = [0]*N
w0 = w[0]
wh = [a - w0 for a in W]
v = [0]*N
for i in range(N):
  w[i], v[i] = (int(i) for i in input().split())
dp = [[[0]*(N+1) for i in range(3N+1)] for j in range(N+1)]
for i in range(N):
  for j in range(3N+1):
    for k in range(N+1):
      dp[i+1][j][k] = max(dp[i+1][j][k], dp[i][j][k])
      if j - wh[i] >=0 and k-1 >=0:
        dp[i+1][j][k] = max(dp[i+1][j][k], dp[i][j-wh[i]][k-1]+v[i])
res = 0
for k in range(N+1):
  if w0*k <= W <= (w0+3)*k:
    Wk = W - w0*k
    ans = 0
    for j in range(Wk+1):
      ans = max(dp[N][j][k], ans)
    res = max(res, ans)
print(res)
Problem p03765 (python)

Fixed submission:
S = input()
T = input()
N = len(S)
M = len(T)
Ss = [0]*(N+1)
Ts = [0]*(M+1)
for i in range(N):
  if S[i] == "A":
    temp = 1
  else:
    temp = -1
  Ss[i+1] = Ss[i] + temp
for i in range(M):
  if T[i] == "A":
    temp = 1
  else:
    temp = -1
  Ts[i+1] = Ts[i] + temp
Q = int(input())
for i in range(Q):
  a, b, c, d = (int(i) for i in input().split())
  if (Ss[b] - Ss[a-1] - Ts[d] + Ts[c-1])%3==0:
    print("YES")
  else:
    print("NO")

Buggy submission (verdict: Runtime Error):
S = input()
T = input()
N = len(S)
M = len(M)
Ss = [0]*(N+1)
Ts = [0]*(M+1)
for i in range(N):
  if S[i] == "A":
    temp = 1
  else:
    temp = -1
  Ss[i+1] = Ss[i] + temp
for i in range(M):
  if T[i] == "A":
    temp = 1
  else:
    temp = -1
  Ts[i+1] = Ts[i] + temp
Q = int(input())
for i in range(Q):
  a, b, c, d = (int(i) for i in input().split())
  if a == b:
    print("NO")
    continue
  else:
    if (Ss[b] - Ss[a-1] - Ts[d] + Ts[c-1])%3==0:
      print("YES")
    else:
      print("NO")
Problem p03849 (python)

Fixed submission:
N= int(input())
bit = bin(N)[2:]
k = len(bit)
dp = [[0] * 2 for i in range(len(bit) + 1)]
dp[0][0] = 1
dp[0][1] = 1
for i in range(k):
	j = int(bit[k-i-1])
	a,b,c = [(1,0,0),(1,1,0)][j]
	d,e,f = [(1, 1, 1),(0, 1, 2)][j]
	dp[i+1][0] = (a * dp[i][0] + b * dp[i][1] + c * 3**i) % 1000000007
	dp[i+1][1] = d * dp[i][0] + e * dp[i][1] + f * 3**i % 1000000007

print(dp[k][0])

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

bit = bin(N)[2:]
k = len(bit)
dp = [[0] * 2 for i in range(len(bit) + 1)]
for i in range(k):
	j = int(bit[k-i+1])
	a,b,c = [(1,0,0),(1,1,0)][j]
	d,e,f = [(2, 1, 1),(1, 2, 2)][j]
	dp[i+1][0] = a * dp[i][0] + b * dp[i][1] + c * 3**i
	dp[i+1][1] = d * dp[i][0] + e * dp[i][1] + f * 3**i

print(dp[k][0])

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

def b(N):
    if N < 2:
        res = N
    else:
        if N % 2 == 0:
            res = b(N//2)
        else:
            res = b( (N-1)//2 ) + b( (N+1)//2 )
    return res
def a(N):
    if N > 0:
        res = a(N-1)
    else:
        res = 0
    return res + b(N+1)

print(a(N))
Problem p03878 (python)

Fixed submission:
N = int(input())
L = []
for i in range(N):
  L.append((int(input()),'a'))
for i in range(N):
  L.append((int(input()),'b'))
L.sort()
res = 1
cc = 0
nowcol = None
mo = 1000000007
for i in range(2*N):
  if cc == 0:
    nowcol=L[i][1]
  if nowcol == L[i][1]:
    cc += 1
  else:
    res *= cc
    res %= mo
    cc -= 1
print(res)

Buggy submission (verdict: Runtime Error):
N = int(input())
L = []
for i in range(N):
  L.append((int(input),'a'))
for i in range(N):
  L.append((int(input),'b'))
L.sort()
res = 1
cc = 0
nowcol = None
mo = 1000000007
for i in range(2*N):
  if cc == 0:
    nowcol=L[i][1]
  if nowcol == L[i][1]:
    cc += 1
  else:
    res *= cc
    res %= mo
    cc -= 1
print(res)
Problem p03938 (python)

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

a = [20000*i+1 for i in range(N)]
b = [20000*(N-i) for i in range(N)]

for i in range(N):
  a[A[i]-1] += i

a = [str(i) for i in a]
b = [str(i) for i in b]

print(" ".join(a))
print(" ".join(b))

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

a = [20000*i for i in range(N)]
b = [20000*(N-i) for i in range(N)]

for i in range(N):
  a[A[i]-1] += N-i-1

a = [str(i) for i in a]
b = [str(i) for i in b]

print(" ".join(a))
print(" ".join(b))