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

Fixed submission:
def main():
    from itertools import product
    H, W, K = map(int, input().split())
    G = [list(map(int, list(input()))) for _ in range(H)]

    ans = float('inf')
    for pattern in product([0, 1], repeat=H - 1):
        tmp_ans = 0
        div = [0] + [i for i, p in enumerate(pattern, start=1) if p == 1] + [100]
        grids = []
        for i in range(len(div) - 1):
            grids.append(G[div[i]: div[i + 1]])

        rows = []
        for grid in grids:
            row = []
            for w in range(W):
                v = 0
                for h in range(len(grid)):
                    v += grid[h][w]
                row.append(v)
            rows.append(row)

        w = 0
        d = set()
        df = False
        counts = [0] * len(rows)
        while w < W:
            for i, row in enumerate(rows):
                counts[i] += row[w]

            if [c for c in counts if c > K]:
                if w in d:
                    df = True
                    break
                d.add(w)
                tmp_ans += 1
                counts = [0] * len(rows)
            else:
                w += 1

            if df:
                break
        
        if not df:
            tmp_ans += len(div) - 2
            ans = min(ans, tmp_ans)

    print(ans)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
def main():
    from itertools import product
    H, W, K = map(int, input().split())
    G = [list(map(int, list(input()))) for _ in range(H)]

    ans = float('inf')
    for pattern in product([0, 1], repeat=H-1):
        tmp_ans = 0
        div = [0] + [i for i, p in enumerate(pattern, start=1) if p == 1] + [100]
        grids = []
        for i in range(len(div) - 1):
            grids.append(G[div[i]: div[i + 1]])

        rows = []
        for grid in grids:
            row = []
            for w in range(W):
                v = 0
                for h in range(len(grid)):
                    v += grid[h][w]
                row.append(v)
            rows.append(row)

        w = 0
        dead_flg = False
        counts = [0] * len(rows)
        dead_set = set()
        while w < W:
            for i, row in enumerate(rows):
                counts[i] += row[w]
                if counts[i] > K:
                    if w in dead_set:
                        dead_flg = True
                        break
                    dead_set.add(w)
                    tmp_ans += 1
                    counts = [0] * len(rows)
                    break
            else:
                w += 1

            if dead_flg:
                break
        tmp_ans += len(div) - 2
        ans = min(ans, tmp_ans)

    print(ans)


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

Fixed submission:
from bisect import bisect_left, bisect_right
N, K = map(int, input().split())
A = sorted(list(map(int, input().split())))

negative_end = bisect_left(A, 0)
positive_start = bisect_right(A, 0)

positive_cnt = N - positive_start
negative_cnt = negative_end
zero_cnt = N - (positive_cnt + negative_cnt)

negative_pairs_cnt = positive_cnt * negative_cnt
zero_pairs_cnt = zero_cnt * (positive_cnt + negative_cnt) + (zero_cnt * (zero_cnt - 1) // 2)

if K <= negative_pairs_cnt:
    # にぶたん: X以下になるペアがK個以上あるか？
    ok, ng = 0, -10 ** 18
    while abs(ok - ng) > 1:
        X = (ok + ng) // 2
        or_higher_cnt, r = 0, positive_start
        for l in range(negative_end):
            while (r < N) and (A[l] * A[r] > X):
                r += 1
            or_higher_cnt += positive_cnt - (r - positive_start)

        if or_higher_cnt >= K:
            ok = X
        else:
            ng = X

    print(ok)

elif K <= negative_pairs_cnt + zero_pairs_cnt:
    print(0)

else:
    # にぶたん: X以下になるペアがK個以上あるか？
    K -= (negative_pairs_cnt + zero_pairs_cnt)
    ok, ng = 10 ** 18, 0
    while abs(ok - ng) > 1:
        X = (ok + ng) // 2
        or_higher_cnt = 0

        r = N - 1
        for l in range(positive_start, N):
            while (r < N) and (A[l] * A[r] > X) and (l < r):
                r -= 1
            or_higher_cnt += max(0, r - l)

        l = 0
        for r in range(negative_end - 1, -1, -1):
            while (l < N) and (A[l] * A[r] > X) and (l < r):
                l += 1

            or_higher_cnt += max(0, r - l)

        if or_higher_cnt >= K:
            ok = X
        else:
            ng = X

    print(ok)

Buggy submission (verdict: Runtime Error):
from bisect import bisect_left, bisect_right
N, K = map(int, input().split())
A = sorted(list(map(int, input().split())))

negative_end = bisect_left(A, 0)
positive_start = bisect_right(A, 0)

positive_cnt = N - positive_start
negative_cnt = negative_end
zero_cnt = N - (positive_cnt + negative_cnt)

negative_pairs_cnt = positive_cnt * negative_cnt
zero_pairs_cnt = zero_cnt * (positive_cnt + negative_cnt) + (zero_cnt * (zero_cnt - 1) // 2)

if K <= negative_pairs_cnt:
    # にぶたん: X以下になるペアがK個以上あるか？
    ok, ng = 0, -10 ** 18
    while abs(ok - ng) > 1:
        X = (ok + ng) // 2
        or_higher_cnt, r = 0, positive_cnt
        for l in range(negative_end):
            while (r < N) and (A[l] * A[r] > X):
                r += 1
            or_higher_cnt += positive_cnt - (r - positive_start)
        if or_higher_cnt >= K:
            ok = X
        else:
            ng = X

    print(ok)

elif K <= negative_pairs_cnt + zero_pairs_cnt:
    print(0)

else:
    print(1 / 0)
    # # にぶたん: X以下になるペアがK個以上あるか？
    # K -= (negative_pairs_cnt + zero_pairs_cnt)
    # ok, ng = 10 ** 18, 0
    # while abs(ok - ng) > 1:
    #     X = (ok + ng) // 2
    #     or_higher_cnt = 0
    #     continue_flg = False
    # print(ok)
Problem p02783 (python)

Fixed submission:
from math import ceil
H, A = map(int, input().split())
print(ceil(H / A))

Buggy submission (verdict: Runtime Error):
def main():
    from math import ceil
    from bisect import bisect_right
    N, D, A = map(int, input().split())
    Monsters = [list(map(int, input().split())) for i in range(N)]
    Monsters = sorted([[x, ceil(h / A)] for x, h in Monsters])


    class BIT2:
        """ 区間加算BIT(区間加算・区間合計取得) """

        def __init__(self, N):
            self.N = N
            self.data0 = [0] * N
            self.data1 = [0] * N

        def _add(self, data, k, x):
            while k < self.N:
                data[k] += x
                k += k & -k

        def _get(self, data, k):
            s = 0
            while k:
                s += data[k]
                k -= k & -k
            return s

        def add(self, l, r, x):
            """ 区間[l,r)に値xを追加 """

            self._add(self.data0, l, -x*(l-1))
            self._add(self.data0, r, x*(r-1))
            self._add(self.data1, l, x)
            self._add(self.data1, r, -x)

        def query(self, l, r):
            """ 区間[l,r)の和を取得 """

            return self._get(self.data1, r-1) * (r-1) + self._get(self.data0, r-1) \
                 - self._get(self.data1, l-1) * (l-1) - self._get(self.data0, l-1)


    RUQ = BIT2(2 * N)
    for i, (x, h) in enumerate(Monsters, start=1):
        RUQ.add(i, i + 1, h)


    i = 0
    ans = 0
    while i < N:
        cost = RUQ.query(i + 1, i + 2)
        if cost > 0:
            index = bisect_right(Monsters, [Monsters[i][0] + 2 * D, float('inf')])
            RUQ.add(i + 1, index + 1, -cost)
            ans += cost
        i += 1
        #
        # check = []
        # for j in range(1, N + 1):
        #     check.append(str(RUQ.query(j, j + 1)))
        # print(' '.join(check))

    print(ans)


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

Fixed submission:
from math import ceil
N, M = map(int, input().split())
A = list(map(int, input().split()))


# 2で割ったものに置き換え
A = [a // 2 for a in A]


# 各要素について、2で割り切れる回数が等しいかチェック
count_div_2 = None
for a in A:
    cnt = 0
    while a % 2 == 0:
        a //= 2
        cnt += 1

    if count_div_2 is None:
        count_div_2 = cnt
    elif cnt != count_div_2:
        print(0)
        exit()


# 最大公約数
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


# 最小公倍数
def lcm(a, b):
    return a // gcd(a, b) * b


while len(A) > 1:
    a, b = A.pop(), A.pop()
    my_lcm = lcm(a, b)

    # Mを超えたlcmは意味がない
    if my_lcm > M:
        print(0)
        exit()

    A.append(my_lcm)


print(ceil(M // A[0] / 2))

Buggy submission (verdict: Runtime Error):
from math import ceil
N, M = map(int, input().split())
A = list(map(int, input().split()))
m = min(A)
A = [a // 2 for a in A]


# 最大公約数
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


# 最小公倍数
def lcm(a, b):
    return a * b // gcd(a, b)


while len(A) > 1:
    A.append(lcm(A.pop(), A.pop()))

X = A[0]
print(ceil((M // X) / 2) - int(X / m < 1))
Problem p02855 (python)

Fixed submission:
H, W, K = map(int, input().split())
S = [list(input()) for i in range(H)]

non_placed_h = set()
for h in range(H):
    if S[h].count('#') == 0:
        non_placed_h.add(h)

ans = [[0] * W for i in range(H)]
x = 0

for h in range(H):
    if h in non_placed_h:
        continue

    else:
        x_cnt = 0
        x += 1

        for w in range(W):
            if S[h][w] == '#':
                x_cnt += 1
                if x_cnt >= 2:
                    x += 1
            ans[h][w] = x

for h in range(H - 2, -1, -1):
    for w in range(W):
        if ans[h][w] == 0:
            ans[h][w] = ans[h + 1][w]

for h in range(1, H):
    for w in range(W):
        if ans[h][w] == 0:
            ans[h][w] = ans[h - 1][w]

for h in range(H - 2, -1, -1):
    for w in range(W):
        if ans[h][w] == 0:
            ans[h][w] = ans[h + 1][w]

for h in range(1, H):
    for w in range(W):
        if ans[h][w] == 0:
            ans[h][w] = ans[h - 1][w]

m = float('inf')
for a in ans:
    m = min(m, min(a))

d = m - 1

for i in range(H):
    for j in range(W):
        ans[i][j] -= d

for a in ans:
    print(' '.join(map(str, a)))

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

non_placed_h = set()
for h in range(H):
    if S[h].count('#') == 0:
        non_placed_h.add(h)

ans = [[0] * W for i in range(H)]
x = 0

for h in range(H):
    if h in non_placed_h:
        continue

    else:
        x_cnt = 0
        x += 1

        for w in range(W):
            if S[h][w] == '#':
                x_cnt += 1
                if x_cnt >= 2:
                    x += 1
            ans[h][w] = x

for h in range(H - 1, -1, -1):
    for w in range(W):
        if ans[h][w] == 0:
            ans[h][w] = ans[h + 1][w]

for h in range(1, H):
    for w in range(W):
        if ans[h][w] == 0:
            ans[h][w] = ans[h - 1][w]

for h in range(H - 1, -1, -1):
    for w in range(W):
        if ans[h][w] == 0:
            ans[h][w] = ans[h + 1][w]

for h in range(1, H):
    for w in range(W):
        if ans[h][w] == 0:
            ans[h][w] = ans[h - 1][w]

m = float('inf')
for a in ans:
    m = min(m, min(a))

d = m - 1

for i in range(H):
    for j in range(W):
        ans[i][j] -= d

for a in ans:
    print(' '.join(map(str, a)))
Problem p02888 (python)

Fixed submission:
from bisect import bisect_right
N = int(input())
L = sorted(list(map(int, input().split())))
L = [(l, i) for i, l in enumerate(L)]

ans = 0
for i in range(N):
    for j in range(i + 1, N):
        l1_value, l1_index = L[i]
        l2_value, l2_index = L[j]
        ans += max(0, (bisect_right(L, (l1_value + l2_value, l2_index))) - j - 1)

print(ans)

Buggy submission (verdict: Runtime Error):
from itertools import accumulate
from collections import Counter
N = int(input())
L = sorted(list(map(int, input().split())))


acc = [0] * 1001
for l in L:
    acc[l] += 1
acc = list(accumulate(acc))


ans = 0
for i in range(N):
    for j in range(i + 1, N):
        l1, l2 = L[i], L[j]
        if l1 == l2:
            continue
        ans += acc[min(1000, l1 + l2 - 1)] - acc[l2]

C = Counter(L)
for k, v in C.items():
    if v >= 3:
        ans += v * (v - 1) * (v - 2) // 6

for k, v in C.items():
    if v >= 2:
        ans += v * (v - 1) // 2 * (acc[min(1000, 2 * v - 1)] - acc[v])

print(ans)
Problem p02900 (python)

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

common_divisors = []
for n in range(1, int(min(A, B) ** 0.5) + 1):
    if (A % n == 0) & (B % n == 0):
        common_divisors.append(n)

    if A % n == 0:
        x = A // n
        if B % x == 0:
            common_divisors.append(x)


# ある自然数の素数判定
def is_prime(n):
    if n == 1:
        return False

    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    else:
        return True


ans = 0
for cd in common_divisors:
    ans += is_prime(cd)

print(ans + 1)

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

common_divisors = []
for n in range(1, int(max(A, B) ** 0.5) + 1):
    if (A % n == 0) & (B % n == 0):
        common_divisors.append(n)


# ある自然数未満までのエラトステネスの篩をつくる
def mark(s, x):
    for i in range(x + x, len(s), x):
        s[i] = False


def eratosthenes(n):
    s = [True] * n
    for x in range(2, int(n ** 0.5) + 1):
        if s[x]: mark(s, x)
    return [i for i in range(0, n) if s[i] and i > 1]


Primes = eratosthenes(max(A, B) + 1)
Primes_set = set(Primes)

ans = 0
for cd in common_divisors:
    if cd in Primes_set:
        ans += 1

print(ans + 1)
Problem p02985 (python)

Fixed submission:
N, K = map(int, input().split())
T = [[] for i in range(N)]
MOD = 10 ** 9 + 7
for i in range(N - 1):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    T[a].append(b)
    T[b].append(a)


stack = [0]
visited = [0] * N
child_num = [0] * N
while stack:
    n = stack.pop()
    visited[n] = 1
    for to in T[n]:
        if visited[to]:
            continue
        child_num[n] += 1
        stack.append(to)


# 階乗 & 逆元計算
factorial = [1]
inverse = [1]
for i in range(1, 10 ** 5 + 1):
    factorial.append(factorial[-1] * i % MOD)
    inverse.append(pow(factorial[-1], MOD - 2, MOD))


# 組み合わせ計算
def nCr(n, r):
    if n < r or r < 0:
        return 0
    elif r == 0:
        return 1
    return factorial[n] * inverse[r] * inverse[n - r] % MOD


ans = K
stack = [0]
visited = [0] * N
while stack:
    n = stack.pop()
    visited[n] = 1

    if n == 0:
        ans = ans * nCr(K - 1, child_num[n]) * factorial[child_num[n]] % MOD
    else:
        ans = ans * nCr(K - 2, child_num[n]) * factorial[child_num[n]] % MOD
    for to in T[n]:
        if visited[to]:
            continue
        stack.append(to)

print(ans % MOD)

Buggy submission (verdict: Runtime Error):
N, K = map(int, input().split())
T = [[] for i in range(N)]
MOD = 10 ** 9 + 7
for i in range(N - 1):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    T[a].append(b)
    T[b].append(a)


stack = [0]
visited = [0] * N
child_num = [0] * N
while stack:
    n = stack.pop()
    visited[n] = 1
    for to in T[n]:
        if visited[to]:
            continue
        child_num[n] += 1
        stack.append(to)


# 階乗 & 逆元計算
factorial = [1]
inverse = [1]
for i in range(1, K + 1):
    factorial.append(factorial[-1] * i % MOD)
    inverse.append(pow(factorial[-1], MOD - 2, MOD))


# 組み合わせ計算
def nCr(n, r):
    if n < r or r < 0:
        return 0
    elif r == 0:
        return 1
    return factorial[n] * inverse[r] * inverse[n - r] % MOD


ans = K
stack = [0]
visited = [0] * N
while stack:
    n = stack.pop()
    visited[n] = 1

    if n == 0:
        ans = ans * nCr(K - 1, child_num[n]) * factorial[child_num[n]] % MOD
    else:
        ans = ans * nCr(K - 2, child_num[n]) * factorial[child_num[n]] % MOD
    for to in T[n]:
        if visited[to]:
            continue
        stack.append(to)

print(ans)
Problem p03014 (python)

Fixed submission:
H, W = map(int, input().split())
G = [list(input()) for i in range(H)]

# あるマスから（右・下・左・上）にいくつ障害物ないマスが続くか
right_space = [[-1] * (W + 2) for i in range(H + 2)]
down_space = [[-1] * (W + 2) for i in range(H + 2)]
left_space = [[-1] * (W + 2) for i in range(H + 2)]
up_space = [[-1] * (W + 2) for i in range(H + 2)]

# 左上から更新（上・左に対応）
for h in range(1, H + 1):
    for w in range(1, W + 1):
        if G[h - 1][w - 1] == '.':
            up_space[h][w] = up_space[h - 1][w] + 1
            left_space[h][w] = left_space[h][w - 1] + 1

# 右下から更新（下・右に対応）
for h in reversed(range(1, H + 1)):
    for w in reversed(range(1, W + 1)):
        if G[h - 1][w - 1] == '.':
            down_space[h][w] = down_space[h + 1][w] + 1
            right_space[h][w] = right_space[h][w + 1] + 1

ans = 0
for h in range(1, H + 1):
    for w in range(1, W + 1):
        if G[h - 1][w - 1] == '.':
            tmp_ans = right_space[h][w] + down_space[h][w] + left_space[h][w] + up_space[h][w] + 1
            ans = max(ans, tmp_ans)

print(ans)

Buggy submission (verdict: Runtime Error):
def main():
    H, W = map(int, raw_input().split())
    G = [list(raw_input()) for i in range(H)]


    up = [[0] * W for i in range(H)]  # あるマスから上に連続していくつ障害物のないマスが続くか
    right = [[0] * W for i in range(H)]  # あるマスから右に連続していくつ障害物のないマスが続くか
    down = [[0] * W for i in range(H)]  # あるマスから下に連続していくつ障害物のないマスが続くか
    left = [[0] * W for i in range(H)]  # あるマスから左に連続していくつ障害物のないマスが続くか


    # up
    for w in range(W):
        for h in range(1, H):
            if G[h - 1][w] == '#':
                continue
            up[h][w] = up[h - 1][w] + 1

    # right
    for h in range(H):
        for w in reversed(range(W - 1)):
            if G[h][w + 1] == '#':
                continue
            right[h][w] = right[h][w + 1] + 1

    # down
    for w in range(W):
        for h in reversed(range(H - 1)):
            if G[h + 1][w] == '#':
                continue
            down[h][w] = down[h + 1][w] + 1

    # left
    for h in range(H):
        for w in range(1, W):
            if G[h][w - 1] == '#':
                continue
            left[h][w] = left[h][w - 1] + 1


    ans = 0
    for h in range(H):
        for w in range(W):
            if G[h][w] == '#':
                continue
            ans = max(ans, up[h][w] + right[h][w] + down[h][w] + left[h][w] + 1)

    print(ans)


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

Fixed submission:
import heapq
import sys

inp = sys.stdin.readline

Q = int(input())
B = 0

q, a, b = map(int, inp().split())
L, R = [-a], [a]
L_sum, R_sum = a, a
B = b

for i in range(Q - 1):
    q = list(map(int, inp().split()))
    if len(q) == 3:
        A = q[1]
        B += q[2]

        if A <= -L[0]:
            heapq.heappush(L, -A)
            M = -heapq.heappushpop(L, -A)
            heapq.heappush(R, M)

            L_sum += (2 * A - M)
            R_sum += M
        else:
            heapq.heappush(R, A)
            M = heapq.heappushpop(R, A)
            heapq.heappush(L, -M)

            R_sum += (2 * A - M)
            L_sum += M
    else:
        N = len(L)
        X = -L[0]
        print(X, (abs(L_sum - X * N) + abs(R_sum - X * N)) // 2 + B)

Buggy submission (verdict: Runtime Error):
import heapq

Q = int(input())
B = 0

q, a, b = map(int, input().split())
L, R = [-a], [a]
L_sum, R_sum = a, a
B = b

for i in range(Q - 1):
    q = list(map(int, input().split()))
    if len(q) == 3:
        A = q[1]
        B += q[2]

        if A <= -L[0]:
            heapq.heappush(L, -A)
            M = -heapq.heappushpop(L, -A)
            heapq.heappush(R, M)

            L_sum += (2 * A - M)
            R_sum += M
        else:
            heapq.heappush(R, A)
            M = heapq.heappush(R, A)
            heapq.heappush(L, -A)

            R_sum += (2 * A - M)
            L_sum += M
    else:
        N = len(L)
        X = -L[0]
        print(X, (abs(L_sum - X * N) + abs(R_sum - X * N)) // 2 + B)
Problem p03128 (python)

Fixed submission:
N, M = map(int, input().split())
Costs = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
A = sorted(list(map(int, input().split())), reverse=True)  # 大きい順に


# dp[i]:= マッチ棒をn本使って得られる最大桁数(-infはマッチ棒が使いきれないことを表す)
dp = [-float('inf')] * (N + 1)
dp[0] = 0

# 個数制限なしナップサックと同じ要領
for a in A:
    cost = Costs[a]
    for j in range(N + 1):
        if cost > j:
            continue
        dp[j] = max(dp[j], dp[j - cost] + 1)


# dpの復元
ans = ""
marker = N  # いま何本残っているか
while dp[marker]:  # 0本になるまで回す
    for a in A:  # 大きな数字から見ていく
        cost = Costs[a]
        
        # Python特有のバグ消し
        if marker - cost < 0:
            continue
        
        # marker本ある状態から、マッチ棒をcost本使う数字aを使わなければ、marker本使った場合の桁数-1になる場合、
        # 数字aを使ったことがわかる
        if dp[marker - cost] == dp[marker] - 1:
            ans += str(a)
            marker = marker - cost
            break

print(ans)

Buggy submission (verdict: Runtime Error):
N, M = map(int, input().split())
Costs = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
A = sorted(list(map(int, input().split())), reverse=True)  # 大きい順に


# dp[i]:= マッチ棒をn本使って得られる最大桁数(-infはマッチ棒が使いきれないことを表す)
dp = [-float('inf')] * (N + 1)
dp[0] = 0

# 蟻本P.60みたいなことをします
for i in range(M):
    cost = Costs[A[i]]
    for j in range(N + 1):
        if cost > j:
            continue
        dp[j] = max(dp[j], dp[j - cost] + 1)


# dpの復元
ans = ""
marker = N  # いま何本残っているか
while dp[marker] > 0:  # 0本になるまで回す
    for a in A:  # 大きな数字から見ていく
        cost = Costs[a]
        # marker本ある状態から、マッチ棒をcost本使う数字aを使わなければ、marker本使った場合の桁数-1になる場合、
        # 数字aを使ったことがわかる
        if dp[marker - cost] == dp[marker] - 1:
            ans += str(a)
            marker = marker - cost
            break

print(ans)

Buggy submission (verdict: Runtime Error):
N, M = map(int, input().split())
Costs = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
A = sorted(list(map(int, input().split())), reverse=True)  # 大きい順に


# dp[i]:= マッチ棒をn本使って得られる最大桁数(-infはマッチ棒が使いきれないことを表す)
dp = [-float('inf')] * (N + 1)
dp[0] = 0

# 蟻本P.60みたいなことをします
for i in range(M):
    cost = Costs[A[i]]
    for j in range(N + 1):
        if cost > j:
            continue
        dp[j] = max(dp[j], dp[j - cost] + 1)


# dpの復元
ans = ""
marker = N  # いま何本残っているか
while dp[marker]:  # 0本になるまで回す
    for a in A:  # 大きな数字から見ていく
        cost = Costs[a]
        # marker本ある状態から、マッチ棒をcost本使う数字aを使わなければ、marker本使った場合の桁数-1になる場合、
        # 数字aを使ったことがわかる
        if dp[marker - cost] == dp[marker] - 1:
            ans += str(a)
            marker = marker - cost
            break

print(ans)
Problem p03151 (python)

Fixed submission:
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

A_origin = A[:]

if sum(A) < sum(B):
    print(-1)
    exit()

diff = [[i, a - b] for i, a, b in zip(range(N), A, B)]

order = sorted([[i, x] for i, x in diff if x > 0], key=lambda d: d[1])
C = []

charge = order.pop()
for i in range(N):
    while A[i] - B[i] < 0:
        if charge[1] > B[i] - A[i]:
            A[charge[0]] -= (B[i] - A[i])
            charge[1] -= (B[i] - A[i])
            A[i] = B[i]
        else:
            A[charge[0]] = B[charge[0]]
            A[i] += charge[1]
            charge = order.pop()

ans = 0
for a, ao in zip(A, A_origin):
    if a != ao:
        ans += 1

print(ans)

Buggy submission (verdict: Runtime Error):
from itertools import accumulate
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))


surplus = [(a - b) for a, b in zip(A, B) if (a - b) > 0]
surplus.sort(reverse=True)
surplus = [0] + list(accumulate(surplus))

short = [(b - a) for a, b in zip(A, B) if (b - a) > 0]
need = sum(short)
short_num = len(short)


if need > sum(surplus):
    print(-1)
    exit()
else:
    for i in range(N + 1):
        if surplus[i] >= need:
            print(i + short_num)
            exit()