Problem p02948 (python)

Fixed submission:
#!/usr/bin/env python3

from collections import deque


class PriorityQueue:
    def __init__(self, size):
        self.tree = [None] * size
        self.bottom = 0

    def add(self, data):
        n = self.bottom
        self.bottom += 1
        self.tree[n] = data
        while n != 0:
            parent = (n - 1) // 2
            if self.tree[parent][1] < self.tree[n][1]:
                self.tree[parent], self.tree[n] = (
                    self.tree[n],
                    self.tree[parent],
                )
                n = parent
            else:
                return

    def top(self):
        return self.tree[0]

    def size(self):
        return self.bottom

    def pop_top(self):
        rv = self.tree[0]
        self.tree[0] = self.tree[self.bottom - 1]
        self.bottom -= 1
        n = 0
        while True:
            child1 = 2 * n + 1
            if child1 >= self.bottom:
                return rv
            child2 = 2 * n + 2
            if child2 >= self.bottom:
                child2 = child1

            if (
                self.tree[n][1] > self.tree[child1][1]
                and self.tree[n][1] > self.tree[child2][1]
            ):
                return rv
            elif self.tree[child1][1] > self.tree[child2][1]:
                self.tree[n], self.tree[child1] = (
                    self.tree[child1],
                    self.tree[n],
                )
                n = child1
            else:
                self.tree[n], self.tree[child2] = (
                    self.tree[child2],
                    self.tree[n],
                )
                n = child2
        return rv


def solve(N, M, A, B):
    ans = 0
    # 日付順にソートする
    all_works = deque(sorted(zip(A, B), key=lambda x: x[0]))
    pq = PriorityQueue(N)

    for d in range(1, M+1):
        # print('d=', d)
        # 今日が期限の仕事があれば追加
        while all_works and all_works[0][0] == d:
            work = all_works.popleft()
            pq.add(work)
        # print('all_works', all_works)
        # print('pq=', pq.tree)
        # 優先キューから最優先の仕事をする
        if pq.size():
            work = pq.pop_top()
            ans += work[1]

    return ans


if __name__ == '__main__':
    N, M = map(int, input().split())
    A = [0] * N
    B = [0] * N
    for idx in range(N):
        A[idx], B[idx] = map(int, input().split())

    ans = solve(N, M, A, B)

    print(ans)

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3

def total_money(bs, m, m_max):
    m = min(m, m_max)
    if m == 1:
        mx = 0
        for i in reversed(range(m)):
            if len(bs[i]) > 0:
                if bs[i][0] > mx:
                    mx = bs[i][0]
        return mx

    mx = 0
    max_tmp  = 0
    for i in reversed(range(m)):
        if len(bs[i]) > 0:
            tmp = bs[i][0]
            if tmp > max_tmp:
                max_tmp = tmp
                bs[i] = bs[i][1:]
                subtotal = total_money(bs, m-1, i+1)
                if tmp+subtotal > mx:
                    mx = tmp+subtotal
            bs[i].insert(0, tmp)
    return mx


def solve(N, M, A, B):
    # 下準備
    bs = [[]] * M
    for a,b in zip(A, B):
        if a <= M:
            bs[a-1] = sorted(bs[a-1] + [b], reverse=True)

    return total_money(bs, M, M)


if __name__ == '__main__':
    N, M = map(int, input().split())
    A = [0] * N
    B = [0] * N
    for idx in range(N):
        A[idx], B[idx] = map(int, input().split())

    ans = solve(N, M, A, B)

    print(ans)

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3

def total_money(bs, m):
    if m == 1:
        mx = 0
        for i in reversed(range(m)):
            if len(bs[i]) > 0:
                if bs[i][0] > mx:
                    mx = bs[i][0]
        return mx

    mx = 0
    max_tmp  = 0
    for i in reversed(range(m)):
        if len(bs[i]) > 0:
            tmp = bs[i][0]
            if tmp > max_tmp:
                max_tmp = tmp
                bs[i] = bs[i][1:]
                subtotal = total_money(bs, m-1)
                if tmp+subtotal > mx:
                    mx = tmp+subtotal
            bs[i].insert(0, tmp)
    return mx


def solve(N, M, A, B):
    # 下準備
    bs = [[]] * M
    for a,b in zip(A, B):
        if a <= M:
            bs[a-1] = sorted(bs[a-1] + [b], reverse=True)

    return total_money(bs, M)


if __name__ == '__main__':
    N, M = map(int, input().split())
    A = [0] * N
    B = [0] * N
    for idx in range(N):
        A[idx], B[idx] = map(int, input().split())

    ans = solve(N, M, A, B)

    print(ans)

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3

def total_money(bs, m):
    if m == 1:
        mx = 0
        for i in sorted(range(m)):
            if len(bs[i]) > 0:
                if bs[i][0] > mx:
                    mx = bs[i][0]
        return mx

    mx = 0
    for i in range(m):
        if len(bs[i]) > 0:
            tmp = bs[i][0]
            bs[i] = bs[i][1:]
            subtotal = total_money(bs, m-1)
            if tmp+subtotal > mx:
                mx = tmp+subtotal
            bs[i].insert(0, tmp)
    return mx


def solve(N, M, A, B):
    # 下準備
    bs = [[]] * M
    for a,b in zip(A, B):
        if a <= M:
            bs[a-1] = sorted(bs[a-1] + [b], reverse=True)

    return total_money(bs, M)


if __name__ == '__main__':
    N, M = map(int, input().split())
    A = [0] * N
    B = [0] * N
    for idx in range(N):
        A[idx], B[idx] = map(int, input().split())

    ans = solve(N, M, A, B)

    print(ans)

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3

def total_money(bs, m):
    if m == 1:
        mx = 0
        for i in range(m):
            if len(bs[i]) > 0:
                if bs[i][0] > mx:
                    mx = bs[i][0]
        return mx

    mx = 0
    for i in range(m):
        if len(bs[i]) > 0:
            tmp = bs[i][0]
            bs[i] = bs[i][1:]
            subtotal = total_money(bs, m-1)
            if tmp+subtotal > mx:
                mx = tmp+subtotal
            bs[i].insert(0, tmp)
    return mx


def solve(N, M, A, B):
    # 下準備
    bs = [[]] * M
    for a,b in zip(A, B):
        if a <= M:
            bs[a-1] = sorted(bs[a-1] + [b], reverse=True)

    return total_money(bs, M)


if __name__ == '__main__':
    N, M = map(int, input().split())
    A = [0] * N
    B = [0] * N
    for idx in range(N):
        A[idx], B[idx] = map(int, input().split())

    ans = solve(N, M, A, B)

    print(ans)