Problem p03128 (python)

Fixed submission:
def chmax(x, y):
    if x == '-':
        return y

    lx = len(x)
    ly = len(y)
    if lx < ly:
        return y
    elif lx == ly:
        if x < y: return y
        else: return x
    else:
        return x


N, M = map(int, input().split())
a = list(map(int, input().split()))

cnt = [N + 1, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = ['-' for _ in range(N + 10 + 1)]
dp[0] = ''
# dp[j]: j 本使ってできる最大の数

for i in range(N + 1):
    # print(dp)
    if dp[i] == '-': continue
    for aa in a:
        dp[i + cnt[aa]] = chmax(dp[i + cnt[aa]], dp[i] + str(aa))

print(dp[N])

Buggy submission (verdict: Runtime Error):
inf = 1 << 20
need = -1, 2, 5, 5, 4, 5, 6, 3, 7, 6

n, m = map(int, input().split())
a = map(int, input().split())
d = {need[x]: x for x in sorted(a)}
# {必要本数:数字}
# sortedで昇順にすることで、同じ本数のとき最大値が残る

dp = [-inf] * (n + 1)
dp[0] = 0
# dp[k]:=k本で構成可能な最大桁数

for j in range(1, n + 1):
    dp[j] = max((dp[j - cnt] for cnt in d if j - cnt >= 0), default=-inf) + 1

ret = []
r = dp[n]

curr = n
while r > 0:
    for cnt, num in sorted(d.items(), key=lambda x: x[1], reverse=True):
        if dp[curr - cnt] == r - 1:
            ret.append(num)
            r -= 1
            curr -= cnt
            break

ret.sort(reverse=True)
print(''.join(map(str, ret)))

Buggy submission (verdict: Runtime Error):
import sys

sys.setrecursionlimit(10 ** 6)

inf = 10 ** 4


def larger(x, y):
    lx, ly = len(x), len(y)
    if lx > ly:
        return x
    elif lx < ly:
        return y
    else:
        x.sort(reverse=True)
        y.sort(reverse=True)
        for xx, yy in zip(x, y):
            if xx > yy:
                return x
            elif xx < yy:
                return y
        return x


def dfs(rest):
    if memo[rest] is not None:
        return memo[rest]

    res = []
    for use, number in d.items():
        if dp[rest - use] == dp[rest] - 1:
            res = larger(res, [number] + dfs(rest - use))

    memo[rest] = res
    return res


n, m = map(int, input().split())
a = tuple(map(int, input().split()))

needs = [inf, 2, 5, 5, 4, 5, 6, 3, 7, 6]
# needs[i] : 数字iを作るのに必要なマッチの本数

for i in range(1, 10):
    if i not in a:
        needs[i] = inf

d = {needs[i]: i for i in range(1, 10) if needs[i] != inf}
# d[本数] = その本数で作れる最大の数値

dp = [-inf] * (n + 1)
dp[0] = 0
# dp[j] : j本から構成できる桁数の最大値

for j in range(2, n + 1):
    for use, number in d.items():
        if j - use >= 0:
            dp[j] = max(dp[j], dp[j - use] + 1)

# print(dp)

memo = [None] * (n + 1)

ans = dfs(n)
ans.sort(reverse=True)
print(*ans, sep='')

Buggy submission (verdict: Runtime Error):
import sys

sys.setrecursionlimit(10 ** 6)

inf = float('inf')


def larger(x, y):
    lx, ly = len(x), len(y)
    if lx > ly:
        return x
    elif lx < ly:
        return y
    else:
        x.sort(reverse=True)
        y.sort(reverse=True)
        for xx, yy in zip(x, y):
            if xx > yy:
                return x
            elif xx < yy:
                return y
        return x


def dfs(rest):
    res = []
    for use, number in d.items():
        if dp[rest - use] == dp[rest] - 1:
            res = larger(res, [number] + dfs(rest - use))
    return res


n, m = map(int, input().split())
a = tuple(map(int, input().split()))

needs = [inf, 2, 5, 5, 4, 5, 6, 3, 7, 6]
# needs[i] : 数字iを作るのに必要なマッチの本数

for i in range(1, 10):
    if i not in a:
        needs[i] = inf

d = {needs[i]: i for i in range(1, 10) if needs[i] != inf}
# d[本数] = その本数で作れる最大の数値

dp = [0] * (n + 1)
# dp[j] : j本から構成できる桁数の最大値

for j in range(2, n + 1):
    for use, number in d.items():
        if j - use >= 0:
            dp[j] = max(dp[j], dp[j - use] + 1)

for j in range(1, n + 1):
    if dp[j] == 0:
        dp[j] = -10
    else:
        break
# dp[j] == 0 となる点をdp[0]だけにすることで、
# if dp[now - use] == dp[now] - 1:
# で、最後0本にたどり着くようになる

ans = dfs(n)
ans.sort(reverse=True)
print(*ans, sep='')

Buggy submission (verdict: Runtime Error):
from math import inf
from sys import setrecursionlimit

setrecursionlimit(10 ** 6)


def larger(x, y):
    lx, ly = len(x), len(y)
    if lx > ly:
        return x
    elif lx < ly:
        return y
    else:
        x.sort(reverse=True)
        y.sort(reverse=True)
        for xx, yy in zip(x, y):
            if xx > yy:
                return x
            elif xx < yy:
                return y
        return x


def dfs(rest):
    res = []
    for use, number in d.items():
        if dp[rest - use] == dp[rest] - 1:
            res = larger(res, [number] + dfs(rest - use))
    return res


n, m = map(int, input().split())
a = tuple(map(int, input().split()))

needs = [inf, 2, 5, 5, 4, 5, 6, 3, 7, 6]
# needs[i] : 数字iを作るのに必要なマッチの本数

for i in range(1, 10):
    if i not in a:
        needs[i] = inf

d = {needs[i]: i for i in range(1, 10) if needs[i] != inf}
# d[本数] = その本数で作れる最大の数値

dp = [0] * (n + 1)
# dp[j] : j本から構成できる桁数の最大値

for j in range(2, n + 1):
    for use, number in d.items():
        if j - use >= 0:
            dp[j] = max(dp[j], dp[j - use] + 1)

for j in range(1, n + 1):
    if dp[j] == 0:
        dp[j] = -10
    else:
        break
# dp[j] == 0 となる点をdp[0]だけにすることで、
# if dp[now - use] == dp[now] - 1:
# で、最後0本にたどり着くようになる

ans = dfs(n)
ans.sort(reverse=True)
print(*ans, sep='')

Buggy submission (verdict: Runtime Error):
from operator import itemgetter

n, m = map(int, input().split())
a = tuple(map(int, input().split()))

needs = [2, 5, 5, 4, 5, 6, 3, 7, 6]
lst_use = tuple(needs[aa - 1] for aa in a)
num_use = tuple(sorted(tuple(zip(a, lst_use)), key=itemgetter(0), reverse=True))
# print(num_use)
dp = [0] * (n + 1)
# dp[j] : j本から構成できる桁数の最大値

for j in range(2, n + 1):
    for use in lst_use:
        if j - use >= 0:
            dp[j] = max(dp[j], dp[j - use] + 1)

for j in range(1, n + 1):
    if dp[j] == 0:
        dp[j] = -10
    else:
        break
# dp[j] == 0 となる点をdp[0]だけにすることで、
# if dp[now - use] == dp[now] - 1:
# で、最後0本にたどり着くようになる

# print(dp)
now = n
ans = ''

# dp[1] = -10
# dp[2] = -10
while now > 0:
    for number, use in num_use:
        if dp[now - use] == dp[now] - 1:
            ans += str(number)
            now -= use
            # print(ans)
            break
    else:
        break

assert now == 0, now

print(ans)