Problem p03128 (python)

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

tab = [6, 2, 5, 5, 4, 5, 6, 3, 7, 6]
A_cmp = {}
for Ai in sorted(A):
    A_cmp[tab[Ai]] = Ai
A = list(A_cmp.values())
A.sort(key=lambda x: -x)

memo = [None] * (N + 1)
memo[0] = 0

import sys
sys.setrecursionlimit(100000)

def dp(X):
    if X < 0: return -(1000000007)
    if memo[X] != None: return memo[X]
    #
    rets = []
    for i, Ai in enumerate(A):
        rets.append(dp(X - tab[Ai]) + 1)
    #
    ret = max(rets)
    memo[X] = ret
    return ret

ans_len = dp(N)

N_tmp = N
ans = ''
for i in range(ans_len):
    for j, Aj in enumerate(A):
        if dp(N_tmp) - 1 == dp(N_tmp - tab[Aj]):
            ans += str(Aj)
            N_tmp -= tab[Aj]
            break

print(ans)

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

tab = [6, 2, 5, 5, 4, 5, 6, 3, 7, 6]
A_cmp = {}
for Ai in sorted(A):
    A_cmp[tab[Ai]] = Ai
A = list(A_cmp.values())
A = A[::-1]
# print("#", A)

memo = [None] * (N + 1)
memo[0] = 0

import sys
sys.setrecursionlimit(100000)

def dp(X):
    if memo[X] != None: return memo[X]
    if X < 0: return -(1000000007)
    #
    rets = []
    for i, Ai in enumerate(A):
        rets.append(dp(X - tab[Ai]) + 1)
    #
    ret = max(rets)
    memo[X] = ret
    return ret

ans_len = dp(N)

N_tmp = N
ans = ''
for i in range(ans_len):
    for j, Aj in enumerate(A):
        if dp(N_tmp) - 1 == dp(N_tmp - tab[Aj]):
            ans += str(Aj)
            N_tmp -= tab[Aj]
            break

print(ans)

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

tab = [6, 2, 5, 5, 4, 5, 6, 3, 7, 6]
A_cmp = {}
for Ai in sorted(A):
    A_cmp[tab[Ai]] = Ai
A = list(A_cmp.values())
A = A[::-1]
# print("#", A)

memo = [None] * (N + 1)
memo[0] = 0

import sys
sys.setrecursionlimit(100000)

def dp(X):
    if memo[X] != None: return memo[X]
    if X < 0: return -(1000000007)
    #
    rets = []
    for i, Ai in enumerate(A):
        rets.append(dp(X - tab[Ai]) + 1)
    #
    ret = max(rets)
    memo[X] = ret
    return ret

ans_len = dp(N)

N_tmp = N
ans = ''
for i in range(ans_len):
    for j, Aj in enumerate(A):
        if j < j_str: continue
        if dp(N_tmp) - 1 == dp(N_tmp - tab[Aj]):
            ans += str(Aj)
            N_tmp -= tab[Aj]
            break

print(ans)

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

tab = [6, 2, 5, 5, 4, 5, 6, 3, 7, 6]
A_cmp = {}
for Ai in sorted(A):
    A_cmp[tab[Ai]] = Ai
A = list(A_cmp.values())
A = A[::-1]
# print("#", A)

memo = [None] * (N + 1)
memo[0] = 0

import sys
sys.setrecursionlimit(10000)

def dp(X):
    if memo[X] != None: return memo[X]
    if X < 0: return -(1000000007)
    #
    rets = []
    for i, Ai in enumerate(A):
        rets.append(dp(X - tab[Ai]) + 1)
    #
    ret = max(rets)
    memo[X] = ret
    return ret

ans_len = dp(N)

N_tmp = N
ans = ''
j_str = 0
for i in range(ans_len):
    for j, Aj in enumerate(A):
        if j < j_str: continue
        if dp(N_tmp) - 1 == dp(N_tmp - tab[Aj]):
            ans += str(Aj)
            N_tmp -= tab[Aj]
            j_str = j
            break

print(ans)

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

tab = [6, 2, 5, 5, 4, 5, 6, 3, 7, 6]
A_cmp = {}
for Ai in sorted(A):
    A_cmp[tab[Ai]] = Ai
A = list(A_cmp.values())
A.sort(key=lambda x: -x)

memo = [None] * (N + 1)
memo[0] = 0

import sys
sys.setrecursionlimit(10000)

def dp(X):
    if memo[X] != None: return memo[X]
    if X < 0: return -(1000000007)
    #
    rets = []
    for i, Ai in enumerate(A):
        rets.append(dp(X - tab[Ai]) + 1)
    #
    ret = max(rets)
    memo[X] = ret
    return ret

ans_len = dp(N)

N_tmp = N
ans = ''
for i in range(ans_len):
    for j, Aj in enumerate(A):
        if dp(N_tmp) - 1 == dp(N_tmp - tab[Aj]):
            ans += str(Aj)
            N_tmp -= tab[Aj]
            break

print(ans)

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

tab = [(1, 2),
       (2, 5),
       (3, 5),
       (4, 4),
       (5, 5),
       (6, 6),
       (7, 3),
       (8, 7),
       (9, 6)]
# tab.sort(key=lambda x: (x[1], -x[0]))

memo = [None] * (N + 1)

def dp(X):
    # print("#", X)
    if X == 0: return ''
    if X < 0: return 'a'
    if memo[X] != None: return memo[X]
    len_max = 0
    rets = []
    for Ai in A:
        if X - tab[Ai - 1][1] < 0: continue
        ret_tmp = str(Ai) + dp(X - tab[Ai - 1][1])
        if 'a' in ret_tmp: continue
        ret_tmp = ''.join(sorted(list(ret_tmp), key=lambda x: -int(x)))
        rets.append(ret_tmp)
        len_max = max(len_max, len(ret_tmp))
    for i in range(len(rets)):
        rets[i] = '0' * (len_max - len(rets[i])) + rets[i]
    #
    rets.sort()
    # print("#", rets)
    if len(rets) == 0:
        ret = 'a'
    else:
        ret = rets[-1].replace('0', '')
    #
    memo[X] = ret
    return ret

print(dp(N))