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

Fixed submission:
import math
N, D, A = map(int, input().split())

M = []
for i in range(N):
    X, H = map(int, input().split())
    M.append((X, H))
M.sort(key=lambda x: x[0])

d = []
i = 0

ans = 0
B = 0
for X, H in M:
    while i != len(d) and X > d[i][0]:
        B -= d[i][1]
        i += 1
    if H > B:
        t = math.ceil((H-B)/A)
        ans += t
        B += t*A
        d.append((X+2*D, t*A))


print(ans)

Buggy submission (verdict: Runtime Error):
import math
import heapq
N, D, A = map(int, input().split())

M = []
for i in range(N):
    X, H = map(int, input().split())
    M.append((X, H))
M.sort(key=lambda x: x[0])


hq = []
heapq.heapify(hq)  # リストhqのheap化
ans = 0
B = 0
dx = M[0][0]+2*D
dd = math.ceil(M[0][1]/A)*A
for i, (x, h) in enumerate(M):
    while x > dx:
        B -= dd
        if B == 0:
            break
        dx, dd = heapq.heappop(hq)
    if h > B:
        t = math.ceil((h-B)/A)
        ans += t
        B += t*A
        if i != 0:
            heapq.heappush(hq, (x+2*D, t*A))
            if len(hq) == 1:
                dx = x+2*D
                dd = t*A


print(ans)

Buggy submission (verdict: Runtime Error):
import math
import heapq
N, D, A = map(int, input().split())

M = []
for i in range(N):
    X, H = map(int, input().split())
    M.append((X, H))
M.sort(key=lambda x: x[0])


hq = []
heapq.heapify(hq)  # リストhqのheap化
ans = 0
B = 0
dx = M[0][0]+2*D
dd = math.ceil(M[0][1]/A)*A
for i, (x, h) in enumerate(M):
    while x > dx:
        B -= dd
        if B == 0:
            break
        dx, dd = heapq.heappop(hq)
    if h > B:
        t = math.ceil((h-B)/A)
        ans += t
        B += t*A
        if i != 0:
            heapq.heappush(hq, (x+2*D, t*A))
        if len(hq) == 1:
            dx = x+2*D
            dd = t*A


print(ans)

Buggy submission (verdict: Runtime Error):
import math
import heapq
N, D, A = map(int, input().split())

M = []
for i in range(N):
    X, H = map(int, input().split())
    M.append((X, H))
M.sort(key=lambda x: x[0])


hq = []
heapq.heapify(hq)  # リストhqのheap化
ans = 0
B = 0
dx = M[0][0]+2*D
dd = math.ceil(M[0][1]/A)*A
for i, (x, h) in enumerate(M):
    while x > dx:
        B -= dd
        if B == 0:
            break
        dx, dd = heapq.heappop(hq)
    if h > B:
        t = math.ceil((h-B)/A)
        ans += t
        B += t*A
        if i != 0:
            heapq.heappush(hq, (x+2*D, t*A))
        # if len(hq)==1:
        #     dx=x+2*D
        #     dd=t*A


print(ans)
Problem p02804 (python)

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

mod = 10**9+7  # 出力の制限


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


maxn = 10**5+10
g1 = [1, 1]  # 元テーブル
g2 = [1, 1]  # 逆元テーブル
inverse = [0, 1]  # 逆元テーブル計算用テーブル

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


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

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


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


def lcm(nums):
    return functools.reduce(multiple, nums)


lcm = lcm(A)
hlcm = lcm//2
# print(lcm, hlcm)
for a in A:
    if a % 2 == 1:
        print(0)
        exit()
    if lcm//a % 2 == 0:
        print(0)
        exit()

if hlcm > M:
    print(0)
else:
    print(M//hlcm//2+1)
Problem p02854 (python)

Fixed submission:
import bisect
import math

N = int(input())
A = [int(i) for i in input().split()]
sa = sum(A)
g = sa/2

S = []
s = 0
for a in A:
    s += a
    S.append(s)


i = bisect.bisect_left(S, g)
print(min(math.ceil(sa-S[i-1]*2), math.ceil(S[i]*2-sa)))

Buggy submission (verdict: Runtime Error):
import bisect
N = int(input())
A = [int(i) for i in input().split()]
g = sum(A)/2

S = []
s = 0
for a in A:
    s += a
    S.append(s)

i = bisect.bisect_left(S, g)

if int(g) in S:
    print(0)
else:
    print(min(S[i]-S[i-1], S[i+1]-S[i]))
Problem p02882 (python)

Fixed submission:
import math
a, b, x = map(int, input().split())

if a**2*b == x:
    print(0)
elif x > (a**2*b)/2:
    p = a/(2*(b-x/a**2))
    print(90-math.degrees(math.atan(p)))
else:
    p = 2*x/(a*b**2)
    print(90-math.degrees(math.atan(p)))

Buggy submission (verdict: Runtime Error):
import math
a, b, x = map(int, input().split())

if a**2*b == x:
    print(0)
if x > (a**2*b)/2:
    p = a/(2*(b-x/a**2))
    print(90-math.degrees(math.atan(p)))
else:
    p = 2*x/(a*b**2)
    print(90-math.degrees(math.atan(p)))
Problem p02883 (python)

Fixed submission:
N, K = map(int, input().split())
A = sorted([int(i) for i in input().split()])
F = sorted([int(i) for i in input().split()], reverse=True)

if sum(A) <= K:
    print(0)
    exit()
else:
    OK = 10**12
    NG = -1

    while OK-NG > 1:
        mid = (OK+NG)//2
        cnt = 0

        for i, a in enumerate(A):
            cnt += max(0, a-mid//F[i])
        if cnt <= K:
            OK = mid
        else:
            NG = mid

print(OK)

Buggy submission (verdict: Runtime Error):
import heapq
N, K = map(int, input().split())
A = sorted([int(i) for i in input().split()], reverse=True)
F = sorted([int(i) for i in input().split()])

if sum(A) <= K:
    print(0)
    exit()
else:
    hq = [-(A[i]*F[i]) for i in range(N)]
    heapq.heapify(hq)  # リストhqのheap化

    for i in range(K):
        c, a, f = heapq.heappop(hq)  # heap化されたリストhqから最小値を削除＆その最小値を出力

        a -= 1
        heapq.heappush(hq, (-(a*f), a, f))

    c, a, f = heapq.heappop(hq)  # heap化されたリストhqから最小値を削除＆その最小値を出力
    print(-c)
Problem p02901 (python)

Fixed submission:
N, M = map(int, input().split())
# print(N)

# DPテーブルを初期化
dp = [10**9] * 2**(N+1)  # dp[010100011010]: 状態010100011010に到達するための最小コスト
dp[0] = 0

# ループを回す
for i in range(M):
    a, b = map(int, input().split())
    c = [int(i) for i in input().split()]

    bit = 0
    for cb in c:
        bit += 2**(cb-1)

    for fromb in range(2**N):
        dp[fromb | bit] = min(dp[fromb | bit], dp[fromb]+a)

if dp[2**N-1] == 10**9:
    print(-1)
else:
    print(dp[2**N-1])

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

# DPテーブルを初期化
dp = [10**9] * ((2**N) + 30)  # dp[010100011010]: 状態010100011010に到達するための最小コスト
dp[0] = 0

# ループを回す
for i in range(M):
    a, b = map(int, input().split())
    c = [int(i) for i in input().split()]

    bit = 0
    for cb in c:
        bit += 2**(cb-1)

    for fromb in range(2**N+1):
        dp[fromb | bit] = min(dp[fromb | bit], dp[fromb]+a)

if dp[2**N-1] == 10**9:
    print(-1)
else:
    print(dp[2**N-1])
Problem p02975 (python)

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

if set(A) == {0}:
    print('Yes')
    exit()


if N % 3 != 0:
    print('No')
    exit()

c = collections.Counter(A)

for v in c.values():
    if v % (N//3) != 0:
        print('No')
        exit()


if len(c) == 2 and c.most_common()[1][0] == 0 and c.most_common()[0][0] ^ 0 == c.most_common()[0][0]:
    print('Yes')
    exit()
elif len(c) == 3 and \
        (c.most_common()[0][0] ^ c.most_common()[1][0] ^ c.most_common()[2][0]) == 0:
    print('Yes')
    exit()


else:
    print('No')

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


if N % 3 != 0:
    print('No')
    exit()

c = collections.Counter(A)

for v in c.values():
    if v % (N//3) != 0:
        print('No')
        exit()


if len(c) == 1 and c.most_common()[0][0] == 0:
    print('Yes')
    exit()
elif len(c) == 2 and c.most_common()[1][0] == 0 and c.most_common()[0][0] ^ 0 == c.most_common[0]:
    print('Yes')
    exit()
elif len(c) == 3 and \
        (c.most_common()[0][0] ^ c.most_common()[1][0] ^ c.most_common()[2][0]) == 0:
    print('Yes')
    exit()


else:
    print('No')
    exit()

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


if N % 3 != 0:
    print('No')
    exit()

c = collections.Counter(A)
# print(len(c))
# print(c.most_common()[0][0] ^ c.most_common()[1][0] ^ c.most_common()[2][0])

for v in c.values():
    # print(v)
    if v % (N//3) != 0:
        print('No')
        exit()


if len(c) == 1 and c.most_common[0] == 0:
    print('Yes')
    exit()
elif len(c) == 2 and c.most_common()[1][0] == 0 and c.most_common()[0][0] ^ 0 == c.most_common[0]:
    print('Yes')
    exit()
elif len(c) == 3 and \
        (c.most_common()[0][0] ^ c.most_common()[1][0] ^ c.most_common()[2][0]) == 0:
    print('Yes')
    exit()


else:
    print('No')
    exit()
Problem p02993 (python)

Fixed submission:
S=input()
if S[0]==S[1] or S[1]==S[2] or S[2]==S[3]:
    print('Bad')
else:
    print('Good')

Buggy submission (verdict: Runtime Error):
S=input()
if S[0]==S[1] or S[1]==S[2] or S[3]==S[4]:
    print('Bad')
else:
    print('Good')
Problem p03001 (python)

Fixed submission:
W,H,x,y=map(int,input().split())

print(W*H/2, 1 if W==2*x and H==2*y else 0)

Buggy submission (verdict: Runtime Error):
W,H,x,y=map(int,input().split())

print(W*H/2, 1 if W=2*x and H=2*y else 0)
Problem p03006 (python)

Fixed submission:
from collections import defaultdict
N = int(input())

if N == 1:
    print(1)
    exit()

xy = []
for i in range(N):
    x, y = map(int, input().split())
    xy.append((x, y))

d = defaultdict(int)

for i in range(N):
    for j in range(N):
        if i == j:
            continue
        p, q = (xy[i][0]-xy[j][0], xy[i][1]-xy[j][1])
        d[(p, q)] += 1

print(N-max(d.values()))

Buggy submission (verdict: Runtime Error):
from collections import defaultdict
N = int(input())

xy = []
for i in range(N):
    x, y = map(int, input().split())
    xy.append((x, y))

d = defaultdict(int)

for i in range(N):
    for j in range(N):
        if i == j:
            continue
        p, q = (xy[i][0]-xy[j][0], xy[i][1]-xy[j][1])
        d[(p, q)] += 1

print(N-max(d.values()))

Buggy submission (verdict: Runtime Error):
from collections import defaultdict
N = int(input())

xy = []
for i in range(N):
    x, y = map(int, input().split())
    xy.append((x, y))

d = defaultdict(int)

for i in range(N):
    for j in range(N):
        if i == j:
            continue
        p, q = (xy[i][0]-xy[j][0], xy[i][1]-xy[j][1])
        d[(p, q)] += 1

print(N-max(d.values()))
Problem p03007 (python)

Fixed submission:
import bisect

N = int(input())
A = sorted([int(i) for i in input().split()])

zp = bisect.bisect_left(A, 0)
ans = []

M = A[0]
for i in range(max(zp, 1), N-1):
    ans.append((M, A[i]))
    M -= A[i]

ans.append((A[N-1], M))
M = A[N-1]-M

for i in range(1, min(zp, N-1)):
    ans.append((M, A[i]))
    M -= A[i]


print(M)
for a, b in ans:
    print(a, b)

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

M = 0
ans = []

if A[0] >= 0:
    ans.append((A[0], A[-1]))
    M = A[0]-A[-1]
    for i in range(1, N-1):
        if i != N-2:
            ans.append((M, A[i]))
            M -= A[i]
        else:
            ans.append((A[i], M))
            M = A[i]-M
elif A[-1] < 0:
    ans.append((A[0], A[-1]))
    M = A[0]-A[-1]
    for i in range(1, N-1):
        ans.append(M, A[i])
        M -= A[i]
else:
    exit()

print(M)
for t in ans:
    print(*t)

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

M = 0
ans = []

if A[0] >= 0:
    ans.append((A[0], A[-1]))
    M = A[0]-A[-1]
    for i in range(1, N-1):
        if i != N-2:
            ans.append((M, A[i]))
            M -= A[i]
        else:
            ans.append((A[i], M))
            M = A[i]-M
elif A[-1] < 0:
    ans.append((A[0], A[-1]))
    M = A[0]-A[-1]
    for i in range(1, N-1):
        ans.append(M, A[i])
        M -= A[i]
else:
    exit()
Problem p03014 (python)

Fixed submission:
import numpy as np

H, W = map(int, input().split())
S = np.array([list(input()) for _ in range(H)]) == "."

D = np.zeros((H, W), dtype=int)
U = np.zeros((H, W), dtype=int)
R = np.zeros((H, W), dtype=int)
L = np.zeros((H, W), dtype=int)

for i in range(H):
    U[i] = (U[i-1]+1)*S[i]
    D[-i - 1] = (D[-i] + 1) * S[-i - 1]

for i in range(W):
    L[:, i] = (L[:, i - 1] + 1) * S[:, i]
    R[:, -i - 1] = (R[:, -i] + 1) * S[:, -i - 1]

print(np.max(D + U + R + L) - 3)

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(1000000)
import numpy as np

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

m_horizontal=[[0 for i in range(W)] for j in range(H)]
m_vertical=[[0 for i in range(W)] for j in range(H)]


for y in range(H):
    for x in range(W):
        if S[y][x]=='#':
            m_horizontal[y][x]=0
        elif x==0 or m_horizontal[y][x-1]==0:
            cnt=0
            i=x
            while S[y][i]=='.':
                cnt+=1
                i+=1
                if i==W:
                    break
            m_horizontal[y][x]=cnt
        else:
            m_horizontal[y][x]=m_horizontal[y][x-1]


        if S[y][x]=='#':
            m_vertical[y][x]=0
        elif y==0 or m_vertical[y-1][x]==0:
            cnt=0
            i=y
            while S[i][x]=='.':
                cnt+=1
                i+=1
                if i==H:
                    break
            m_vertical[y][x]=cnt
        else:
            m_vertical[y][x]=m_vertical[y-1][x]

ho=np.array(m_horizontal)
ve=np.array(m_vertical)
hv=ho+ve
print(np.amax(hv)-1)
Problem p03031 (python)

Fixed submission:
N,M=map(int,input().split())
sw=[]
for _ in range(M):
    sw.append(list(map(int,input().split()))[1:])
p=[int(i) for i in input().split()]

ans=0
for i in range(1<<N):
    flg=True

    for c,s in enumerate(sw):
        s_on=0
        for bit in s:
            if ((i >> (bit-1)) & 1) == 1:
                s_on+=1
        if s_on%2!=p[c]:
            flg=False

    if flg:
        ans+=1

print(ans)

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

lst = []
for i in range(N):
    ks = list(map(int,input().split()))
    lst.append(ks[1:])

p = list(map(int, input().split()))

c = 0

for j in range(2**N):
    for k, l in enumerate(p):
        msk = 0
        for b in lst[k]:
            msk += 2**(b-1)
        if bin(j&msk).count('1') % 2 != l:
            break
    else:
        c += 1

print(c)
Problem p03071 (python)

Fixed submission:
a, b = map(int, input().split())

if abs(a-b) <= 1:
  print(a+b)
else:
  print(max(a, b)*2-1)

Buggy submission (verdict: Runtime Error):
a, b = map(int, input().split())

if abs(a-b) <= 1:
  print(a+b)
else print(max(a, b)*2-1)
Problem p03086 (python)

Fixed submission:
import re

S=input()

ans=0
for i in range(10):
  for j in range(i,10+1):
    str=S[i:j]
    if re.search(r'^[AGCT]+$' ,str):
      ans=max(ans,len(str))

print(ans)

Buggy submission (verdict: Runtime Error):
import re

S = input()

print(len(max(re.findall('[ATCG]+', S))))

Buggy submission (verdict: Runtime Error):
import re

S = input()

print(max(re.findall('[ATCG]+', S)))
Problem p03096 (python)

Fixed submission:
from collections import defaultdict

N=int(input())
C=[int(input()) for _ in range(N)]

d = defaultdict(int)

ans=1
for i,c in enumerate(C):
    if i>=1 and C[i-1]==C[i]:
        continue
    else:
        ans+=d[c]
        d[c]=ans
        
        ans%=10**9+7
        d[c]%=10**9+7
print(ans)

Buggy submission (verdict: Runtime Error):
N = int(input())
C = [int(input()) for _ in range(N)]

L = [-1]*(10**5+10)
dp = [-1]*(10**5+10)
dp[0] = 1

for i in range(N):
    if L[C[i]] == -1:
        dp[i+1] = dp[i]
    elif C[i] == C[i-1]:
        dp[i+1] = dp[i]
    else:
        dp[i+1] = dp[i]+dp[L[C[i]]]
    L[C[i]] = i+1
print(dp[N])
Problem p03101 (python)

Fixed submission:
H, W = map(int, input().split())
h, w = map(int, input().split())

print((W-w) * (H-h))

Buggy submission (verdict: Runtime Error):
H, W = map(int, input())
h, w = map(int, input())

print((W-w) * (H-h))

Buggy submission (verdict: Runtime Error):
H, W = map(int, input())
h, w = map(int, input())

print((H-h) * (H-h))
Problem p03112 (python)

Fixed submission:
import bisect
A, B, Q = map(int, input().split())
S = [int(input()) for _ in range(A)]
T = [int(input()) for _ in range(B)]
X = [int(input()) for _ in range(Q)]

for x in X:
    p0, p1, p2, p3 = (10**12 for _ in range(4))
    si = bisect.bisect_left(S, x)
    ti = bisect.bisect_left(T, x)

    if si != 0 and ti != 0:
        p0 = max(x-S[si-1], x-T[ti-1])
    if si != 0 and ti != B:
        p1 = min(x-S[si-1], T[ti]-x)*2+max(x-S[si-1], T[ti]-x)
    if si != A and ti != 0:
        p2 = min(S[si]-x, x-T[ti-1])*2+max(S[si]-x, x-T[ti-1])
    if si != A and ti != B:
        p3 = max(S[si]-x, T[ti]-x)
    print(min(p0, p1, p2, p3))

Buggy submission (verdict: Runtime Error):
import bisect
A, B, Q = map(int, input().split())
S = [int(input()) for _ in range(A)]
T = [int(input()) for _ in range(B)]
X = [int(input()) for _ in range(Q)]

A = []
for x in X:
    SL, SR, TL, TR = 10**20, 10**20, 10**20, 10**20
    i = bisect.bisect_left(S, x)
    if i != 0:
        SL = x-S[i-1]
    if i != A:
        SR = S[i]-x

    j = bisect.bisect_left(T, x)
    if j != 0:
        TL = x-T[j-1]
    if j != B:
        TR = T[j]-x

    ans = min(max(SL, TL), min(2*SL+TR, SL+2*TR),
              min(2*TL+SR, TL+2*SR), max(SR, TR))
    A.append(ans)
print(*A, sep='\n')
Problem p03142 (python)

Fixed submission:
from collections import deque, defaultdict

N, M = map(int, input().split())
ab = []
for _ in range(N + M - 1):
    ab.append(tuple(map(int, input().split())))

in_cnt = defaultdict(int)
rev = defaultdict(list)
outs = defaultdict(list)
for a, b in ab:
    in_cnt[b - 1] += 1
    outs[a - 1].append(b - 1)
    rev[b - 1].append(a - 1)

res = []
queue = deque([i for i in range(N) if in_cnt[i] == 0])
while queue:
    v = queue.popleft()
    res.append(v)
    for v2 in outs[v]:
        in_cnt[v2] -= 1
        if in_cnt[v2] == 0:
            queue.append(v2)

order = [i for i, v in sorted(enumerate(res), key=lambda x: x[1])]

ans = [0] * N
ans[res[0]] = 0
for v in res[:0:-1]:
    ans[v] = max([(order[v2], v2) for v2 in rev[v]])[1] + 1

for a in ans:
    print(a)

Buggy submission (verdict: Runtime Error):
from collections import deque, defaultdict

N, M = map(int, input().split())
ab = []
for _ in range(N + M - 1):
    ab.append(tuple(map(int, input().split())))

in_cnt = defaultdict(int)
outs = defaultdict(list)
for a, b in ab:
    in_cnt[b - 1] += 1
    outs[a - 1].append(b - 1)

res = []
queue = deque([i for i in range(N) if in_cnt[i] == 0])
while queue:
    v = queue.popleft()
    res.append(v)
    for v2 in outs[v]:
        in_cnt[v2] -= 1
        if in_cnt[v2] == 0:
            queue.append(v2)

order = [i for i, v in sorted(enumerate(res), key=lambda x: x[1])]

ans = [0] * N
ans[res[0]] = 0
for v in res[:0:-1]:
    ans[v] = max([(order[v2], v2) for v2 in rev[v]])[1] + 1

for a in ans:
    print(a)
Problem p03148 (python)

Fixed submission:
import heapq

N, K = map(int, input().split())
sushi = []

for _ in range(N):
    t, d = map(int, input().split())
    sushi.append((t, d))
sushi = sorted(sushi, key=lambda x: -x[1])

d_sushi = []  # 捨てる候補の寿司
heapq.heapify(d_sushi)  # リストaのheap化

fp = 0
tp = set()

for i in range(K):
    fp += sushi[i][1]
    if sushi[i][0] in tp:
        heapq.heappush(d_sushi, sushi[i][1])
    else:
        tp.add(sushi[i][0])
ans = fp+len(tp)**2

if N == K:
    print(ans)
    exit()

j = K
while d_sushi and len(tp) <= N:
    while sushi[j][0] in tp:
        j += 1
        if j == N:
            print(ans)
            exit()
    fp = fp-heapq.heappop(d_sushi)+sushi[j][1]
    tp.add(sushi[j][0])
    ans = max(ans, fp+len(tp)**2)

print(ans)

Buggy submission (verdict: Runtime Error):
import heapq

N, K = map(int, input().split())
sushi = []

for _ in range(N):
    t, d = map(int, input().split())
    sushi.append((t, d))
sushi = sorted(sushi, key=lambda x: -x[1])

d_sushi = []  # 捨てる候補の寿司
heapq.heapify(d_sushi)  # リストaのheap化

fp = 0
tp = set()

for i in range(K):
    fp += sushi[i][1]
    if sushi[i][0] in tp:
        heapq.heappush(d_sushi, sushi[i][1])
    else:
        tp.add(sushi[i][0])
ans = fp+len(tp)**2

j = K
while d_sushi and len(tp) <= N:
    while sushi[j][0] in tp:
        j += 1
        if j == N:
            print(ans)
            exit()
    fp = fp-heapq.heappop(d_sushi)+sushi[j][1]
    tp.add(sushi[j][0])
    ans = max(ans, fp+len(tp)**2)

print(ans)
Problem p03157 (python)

Fixed submission:
import collections
import sys
sys.setrecursionlimit(1000000)


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


seen = [[False] * W for i in range(H)]
move = ((-1, 0), (1, 0), (0, -1), (0, 1))

q = collections.deque()


def bfs(i, j):
    b, w = 0, 0
    seen[i][j] = True
    q.append((i, j))

    while q:
        ci, cj = q.popleft()

        if S[ci][cj] == '#':
            b += 1
        else:
            w += 1

        for di, dj in move:
            ni = ci+di
            nj = cj+dj
            if 0 <= ni < H and 0 <= nj < W:
                if seen[ni][nj] is False and S[ci][cj] != S[ni][nj]:
                    seen[ni][nj] = True
                    q.append((ni, nj))

    return b*w


ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '#' and seen[i][j] is False:
            ans += bfs(i, j)

print(ans)

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

ans = set()


def f(i, j):
    seen[i][j] = 1
    if S[i][j] == '.':
        ans.add((s, (i, j)))
    if i != 0:
        if seen[i-1][j] == 0 and S[i-1][j] != S[i][j]:
            f(i-1, j)
    if i != H-1:
        if seen[i+1][j] == 0 and S[i+1][j] != S[i][j]:
            f(i+1, j)
    if j != 0:
        if seen[i][j-1] == 0 and S[i][j-1] != S[i][j]:
            f(i, j-1)
    if j != W-1:
        if seen[i][j+1] == 0 and S[i][j+1] != S[i][j]:
            f(i, j+1)


for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            seen = [[0] * W for i in range(H)]
            s = (i, j)
            f(i, j)

print(len(ans))
Problem p03161 (python)

Fixed submission:
N,K=map(int,input().split())
h=[int(i) for i in input().split()] + [0 for i in range(K)]

ans=[10**20 for i in range(N+K)]
ans[0]=0

for i in range(N):
    for j in range(1,K+1):
        ans[i+j]=min(ans[i+j],ans[i]+abs(h[i]-h[i+j]))

print(ans[N-1])

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

ans=[10**20 for i in range(N+K)]
ans[0]=0

for i in range(N):
    for j in range(1,K+1):
        ans[i+j]=min(ans[i+j],ans[i]+abs(h[i]-h[i+j]))

print(ans[N-1])
Problem p03163 (python)

Fixed submission:
# dp[i][w_sum]: i番目までの品物で重さがw_sumを超えないように選んだときの、価値の総和の最大値

N,W=map(int,input().split())
items=[tuple(map(int,input().split())) for i in range(N)]
items.insert(0, (0,0))

dp=[[0 for _ in range(W+1)] for _ in range(N+1)]

for i in range(1,N+1):
    for j in range(W+1):
        # take item
        if j-items[i][0]>=0:
            dp[i][j]=dp[i-1][j-items[i][0]]+items[i][1]
        
        dp[i][j]=max(dp[i][j],dp[i-1][j])

print(dp[N][W])

Buggy submission (verdict: Runtime Error):
# dp[i][w_sum]: i-1番目までの品物で重さがw_sumを超えないように選んだときの、価値の総和の最大値

N, W = map(int, input().split())
items = [tuple(map(int, input().split())) for i in range(N)]

dp = [[0 for w_sum in range(W)] for i in range(N)]

for i in range(N):
    for w_sum in range(W):

        # i-1番目の品物を選ぶ場合
        # 重量的に入れられるなら入れてみる
        if w_sum-items[i][0] >= 0:
            dp[i+1][w_sum] = max(dp[i+1][w_sum],
                                 dp[i][w_sum-items[i][0]]+items[i][1])

        # i-1番目の品物を選ばない場合
        dp[i+1][w_sum] = max(dp[i+1][w_sum], dp[i][w_sum])

print(dp[N][W])