Problem p03128 (python)

Fixed submission:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import sys

input = sys.stdin.readline

MATCH_NUM = [-1, 2, 5, 5, 4, 5, 6, 3, 7, 6]

def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))

    # N 本で作れる桁の数
    dp = [-1 for _ in range(N+1)]
    dp[0] = 0
    for i in range(N+1):
        for a in A:
            if i < MATCH_NUM[a]:
                continue
            dp[i] = max(dp[i], dp[i-MATCH_NUM[a]] + 1)

    max_digit_num = dp[N]

    res = ''
    for _ in range(max_digit_num):
        m = -1
        for a in A:
            if N < MATCH_NUM[a]:
                continue
            if dp[N-MATCH_NUM[a]] == dp[N]-1:
                if a > m:
                    m = a
        res += str(m)
        N -= MATCH_NUM[m]
    print(res)
main()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import sys

input = sys.stdin.readline

MATCH_NUM = [-1, 2, 5, 5, 4, 5, 6, 3, 7, 6]

def main():
    N, M = [int(e) for e in input().split()]
    A = [int(e) for e in input().split()]

    # N 本で作れる桁の数
    dp = [-1 for _ in range(N+1)]
    dp[0] = 0
    dp[1] = 0
    for i in range(N+1):
        for a in A:
            if i-MATCH_NUM[a] < 0:
                continue
            dp[i] = max(dp[i], dp[i-MATCH_NUM[a]] + 1)

    max_digit_num = dp[N]

    A.sort(reverse=True)

    min_cost = 10
    for a in A:
        if MATCH_NUM[a] < min_cost:
            min_cost = MATCH_NUM[a]

    res = ''
    for _ in range(max_digit_num):
        for a in A:
            if dp[N-MATCH_NUM[a]] == dp[N]-1:
                if N-MATCH_NUM[a] < min_cost and N-MATCH_NUM[a] != 0:
                    continue
                res += str(a)
                N -= MATCH_NUM[a]
                break
    print(res)
main()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import sys

input = sys.stdin.readline

MATCH_NUM = [-1, 2, 5, 5, 4, 5, 6, 3, 7, 6]

def main():
    N, M = [int(e) for e in input().split()]
    A = [int(e) for e in input().split()]

    # N 本で作れる桁の数
    dp = [-1 for _ in range(N+1)]
    dp[0] = 0
    dp[1] = 0
    for i in range(N+1):
        for a in A:
            dp[i] = max(dp[i], dp[i-MATCH_NUM[a]] + 1)

    max_digit_num = dp[N]

    A.sort(reverse=True)

    min_cost = 10
    for a in A:
        if MATCH_NUM[a] < min_cost:
            min_cost = MATCH_NUM[a]

    res = ''
    for _ in range(max_digit_num):
        for a in A:
            if dp[N-MATCH_NUM[a]] == dp[N]-1:
                if N-MATCH_NUM[a] <= min_cost and N-MATCH_NUM[a] != 0:
                    continue
                res += str(a)
                N -= MATCH_NUM[a]
                break
    print(res)
main()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import sys

input = sys.stdin.readline

MATCH_NUM = [-1, 2, 5, 5, 4, 5, 6, 3, 7, 6]

def main():
    N, M = [int(e) for e in input().split()]
    A = [int(e) for e in input().split()]

    # N 本で作れる桁の数
    dp = [-1 for _ in range(N+1)]
    dp[0] = 0
    dp[1] = 0
    for i in range(N+1):
        for a in A:
            dp[i] = max(dp[i], dp[i-MATCH_NUM[a]] + 1)

    max_digit_num = dp[N]

    A.sort(reverse=True)

    min_cost = 10
    for a in A:
        if MATCH_NUM[a] < min_cost:
            min_cost = MATCH_NUM[a]

    res = ''
    for i in range(max_digit_num):
        for a in A:
            if dp[N-MATCH_NUM[a]] == dp[N]-1:
                if N-MATCH_NUM[a] < min_cost and N-MATCH_NUM[a] != 0:
                    continue
                res += str(a)
                N -= MATCH_NUM[a]
                break
    print(res)
main()

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-

import sys

#          x  1  2  3  4  5  6  7  8  9
num     = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
rev_num = [0, 6, 7, 3, 6, 5, 4, 5, 5, 2]

inf = 10000000000

def main():
    sp = [int(e) for e in input().split(" ")]
    n = sp[0]
    m = sp[1]

    # 使える桁が入る
    A = [int(e) for e in input().split(" ")]

    # 最大桁を求める
    # マッチ数が同じ場合、桁の大きい方で順位づけする
    # 0 <= i < n において、マッチ i 本をちょうど使って作成できる最大の桁を求める
    dp = [0] * (n+1)

    for i in range(1, n+1):
        max = 0
        matched = False
        for j in A:
            if dp[i-num[j]] == -inf or i-num[j] < 0:
                continue
            matched = True
            tmp = dp[i-num[j]] + 1
            if tmp > max:
                max = tmp
        if not matched:
            dp[i] = -inf
        else:
            dp[i] = max

    A.sort()
    A.reverse()

    # print(dp[n], dp)

    n2 = n;
    while n2 != 0:
        # print("--- n = {} --".format(n2))
        for e in A:
            # print("e = {}, dp[n-num(e)] = {}, dp[n]-1 = {}".format(e, dp[n2-num[e]], dp[n2]-1))
            if dp[n2-num[e]] == dp[n2]-1:
                # print('select = {} ({})'.format(e, num[e]))
                n2 -= num[e]
                print(e, end="")
                break
    print()

main()