Problem p03128 (python)

Fixed submission:
Matches = {num: c for num, c in zip([1, 2, 3, 4, 5, 6, 7, 8, 9], [2, 5, 5, 4, 5, 6, 3, 7, 6])}


def solve(N, M, As):
    dp = [-1 for _ in range(N + 1)]
    dp[0] = 0
    for a in sorted(As, reverse=True):
        c = Matches[a]
        for i in range(N - c + 1):
            if dp[i] == -1:
                continue
            dp[i + c] = max(dp[i+c],
                            dp[i] * 10 + a)
    return dp[N]

if __name__ == "__main__":
    N, M = tuple(map(int, input().split(" ")))
    As = list(map(int, input().split(" ")))
    print(solve(N, M, As))

Buggy submission (verdict: Runtime Error):
Matches = {num: c for num, c in zip([1, 2, 3, 4, 5, 6, 7, 8, 9], [2, 5, 5, 4, 5, 6, 3, 7, 6])}


def solve(N, M, As):
    dp = [-1 for _ in range(N + 1)]
    dp[0] = 0
    As = sorted(As, reverse=True)
    for i in range(N + 1):
        for a in As:
            c = Matches[a]
            if dp[i - c] == -1:
                continue
            if 0 <= i - c:
                dp[i] = max(dp[i],
                            dp[i - c] * 10 + a)
    return dp[N]

if __name__ == "__main__":
    N, M = tuple(map(int, input().split(" ")))
    As = list(map(int, input().split(" ")))
    print(solve(N, M, As))

Buggy submission (verdict: Runtime Error):
Matches = {num: c for num, c in zip([1, 2, 3, 4, 5, 6, 7, 8, 9], [2, 5, 5, 4, 5, 6, 3, 7, 6])}


def solve(N, M, As):
    dp = [-1 for _ in range(N + 1)]
    dp[0] = 0
    As = sorted(As, reverse=True)
    for i in range(N + 1):
        for a in As:
            c = Matches[a]
            if dp[i - c] == -1:
                continue
            if 0 <= i - c <= N:
                dp[i] = max(dp[i],
                                dp[i-c] * 10 + a)
    return dp[N]

if __name__ == "__main__":
    N, M = tuple(map(int, input().split(" ")))
    As = list(map(int, input().split(" ")))
    print(solve(N, M, As))

Buggy submission (verdict: Runtime Error):
Matches = {num: c for num, c in zip([1, 2, 3, 4, 5, 6, 7, 8, 9], [2, 5, 5, 4, 5, 6, 3, 7, 6])}

memos = {}

def psolve(N, digit, Ms):
    if N == 0:
        return digit
    if N < min([m for m in Ms.values()]):
        return -1
    ans = 0
    if (N, digit) in memos:
        return memos[(N, digit)]

    for (dc, dnum) in sorted([(c, num) for (num, c) in Ms.items()], key=lambda x: -x[0]):
        if digit + str(dnum) > str(dnum) + digit:
            p = psolve(N - dc, digit + str(dnum), Ms)
            if p != -1:
                ans = max(ans, int(p))
        else:
            p = psolve(N - dc, str(dnum) + digit, Ms)
            if p != -1:
                ans = max(ans, int(p))
    memos[(N, digit)] = ans
    return memos[(N, digit)]


def solve(N, M, As):
    Ms = {num: c for num, c in Matches.items() if num in As}
    return psolve(N, "", Ms)

if __name__ == "__main__":
    N, M = tuple(map(int, input().split(" ")))
    As = list(map(int, input().split(" ")))
    print(solve(N, M, As))

Buggy submission (verdict: Runtime Error):
Matches = {num: c for num, c in zip([1, 2, 3, 4, 5, 6, 7, 8, 9], [2, 5, 5, 4, 5, 6, 3, 7, 6])}

def psolve(N, digit, Ms):
    if N == 0:
        return digit
    if N < min([m for m in Ms.values()]):
        return -1
    ans = 0
    for (dc, dnum) in [(c, num) for (num, c) in Ms.items()]:
        if digit + str(dnum) > str(dnum) + digit:
            p = psolve(N - dc, digit + str(dnum), Ms)
            if p != -1:
                ans = max(ans, int(p))
        else:
            p = psolve(N - dc, str(dnum) + digit,  Ms)
            if p != -1:
                ans = max(ans, int(p))
    return ans

def solve(N, M, As):
    Ms = {num: c for num, c in Matches.items() if num in As}
    return psolve(N, "", Ms)


if __name__ == "__main__":
    N, M = tuple(map(int, input().split(" ")))
    As = list(map(int, input().split(" ")))
    print(solve(N, M, As))