Problem:


Score : 400 points

Problem Statement

Find the largest integer that can be formed with exactly N matchsticks, under the following conditions:

Every digit in the integer must be one of the digits A_1, A_2, ..., A_M (1 \leq A_i \leq 9).

The number of matchsticks used to form digits 1, 2, 3, 4, 5, 6, 7, 8, 9 should be 2, 5, 5, 4, 5, 6, 3, 7, 6, respectively.

Constraints

All values in input are integers.

2 \leq N \leq 10^4

1 \leq M \leq 9

1 \leq A_i \leq 9

A_i are all different.

There exists an integer that can be formed by exactly N matchsticks under the conditions.

Input

Input is given from Standard Input in the following format:

N M
A_1 A_2 ... A_M

Output

Print the largest integer that can be formed with exactly N matchsticks under the conditions in the problem statement.

Sample Input 1

20 4
3 7 8 4

Sample Output 1

777773

The integer 777773 can be formed with 3 + 3 + 3 + 3 + 3 + 5 = 20 matchsticks, and this is the largest integer that can be formed by 20 matchsticks under the conditions.

Sample Input 2

101 9
9 8 7 6 5 4 3 2 1

Sample Output 2

71111111111111111111111111111111111111111111111111

The output may not fit into a 64-bit integer type.

Sample Input 3

15 3
5 4 6

Sample Output 3

654



Sample input:
20 4
3 7 8 4


Sample output:
777773

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
A = list(map(int,input().split()))
weight = [0,2,5,5,4,5,6,3,7,6]
dp=[-1]*(N+1)
dp[0] = 0

for i in range(N+1):
  if dp[i] == -1: continue
  for a in A:
    if i+weight[a]<N+1:
      dp[i+weight[a]] = max(dp[i+weight[a]],dp[i]*10+a)
      print(dp)

print(dp[-1])

Submission status: Runtime Error

Solution code:

from heapq import heappop, heappush
N, M = map(int, input().split())
A = list(map(int, input().split()))

queue = []

for a in A:
  if a == 1:
    heappush(queue, (2, 1))
  elif a == 2:
    heappush(queue, (5, 2))
  elif a == 3:
    heappush(queue, (5, 3))
  elif a == 4:
    heappush(queue, (4, 4))
  elif a == 5:
    heappush(queue, (5, 5))
  elif a == 6:
    heappush(queue, (6, 6))
  elif a == 7:
    heappush(queue, (3, 7))
  elif a == 8:
    heappush(queue, (7, 8))
  elif a == 9:
    heappush(queue, (6, 9))

x, y = heappop(queue)
mod = N % x
ans = [y] * ((N - N % x) // x)
baseX = x

while mod != 0:
  ans = ans[1:]
  mod += baseX
  x, y = heappop(queue)
  ans.append(y)
  mod %= x

for a in sorted(ans, reverse=True):
  print(a, end="")

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
A = list(map(int,input().split()))
weight = [2,5,5,4,5,6,3,7,6]
dp=[-1]*(N+1)
dp[0] = 0
for i in range(N+1):
    if dp[i] == -1:continue
    for a in A:
        if i+weight[a]<N+1:
            dp[i+weight[a]] = max(dp[i+weight[a]],dp[i]*10+a)
print(dp[-1])

Submission status: Runtime Error

Solution code:
import bisect
N, M = map(int, input().split())
A = list(map(int, input().split()))
num = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
num = [(i, num[i]) for i in range(10) if i in A]
num.sort(key=lambda x: x[0], reverse=True)
num.sort(key=lambda x: x[1])
dp = ["" for i in range(N+1)]
ans = 0
tmp = set()
for x in num:
    if x > N:
        continue
    for i in range(1, N+1-x[1]):
        for n, k in num:
            if i - k in tmp:
                dp[i] = dp[i-k]+str(n)
                tmp.add(i)
                break
            else:
                if i == k:
                    dp[i] = str(n)
                    tmp.add(k)
                    break
    tmp2 = list(dp[N-x[1]])
    tmp2.append(str(x[0]))
    tmp2.sort(reverse=True)
    ans = max(int("".join(map(str, tmp2))), ans)
print(ans)

Submission status: Runtime Error

Solution code:
import bisect
N, M = map(int, input().split())
A = list(map(int, input().split()))
num = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
num = [(i, num[i]) for i in range(10) if i in A]
num.sort(key=lambda x: x[0], reverse=True)
num.sort(key=lambda x: x[1])
dp = ["" for i in range(N+1)]
ans = 0
for x in num:
    tmp = set()

    for i in range(1, N+1-x[1]):
        for n, k in num:
            if i - k in tmp:
                dp[i] = dp[i-k]+str(n)
                tmp.add(i)
                break
            else:
                if i == k:
                    dp[i] = str(n)
                    tmp.add(k)
                    break
    tmp2 = list(dp[N-x[1]])
    tmp2.append(str(x[0]))
    tmp2.sort(reverse=True)
    ans = max(int("".join(map(str, tmp2))), ans)
print(ans)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
a = map(int, input().split())

t = ['_', 2, 5, 5, 4, 5, 6, 3, 7, 6]

# n 本使ってできる最大の桁数
dp = [-1 for _ in range(n + 1)]
dp[0] = 0

digs = [[] for _ in range(n + 1)]

available = {}
for x in a:
    available[t[x]] = x

for k, v in available.items():
    for i in range(len(dp)):
        if dp[i] >= 0 and i + k < len(dp):
            if dp[i + k] < dp[i] + 1:
                dp[i + k] = dp[i] + 1
                s = digs[i].copy()
                s.append(v)
                digs[i + k] = list(reversed(sorted(s)))
            elif dp[i + k] == dp[i] + 1:
                s = digs[i].copy()
                s.append(v)
                nxt = list(reversed(sorted(s)))
                if digs[i + k] < nxt:
                    dp[i + k] = dp[i] + 1
                    digs[i + k] = nxt

print(''.join(map(str, reversed(sorted(digs[n])))))

Submission status: Runtime Error

Solution code:
import os, sys, re, math

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

match = [10000000,2,5,5,4,5,6,3,7,6]
memo = {}

def doit(m):
    if m in memo:
        return memo[m]
    if m == 0:
        return ""

    ret = None
    for a in A:
        tmp = None
        if m - match[a] >= 0:
            tmp = doit(m - match[a])
            if tmp is not None:
                tmp = max(str(a) + tmp, tmp + str(a))
                if ret is not None:
                    if len(ret) < len(tmp) or (len(ret) == len(tmp) and tmp > ret):
                        ret = tmp
                else:
                    ret = tmp

    memo[m] = ret
    return ret

print(doit(N))

Submission status: Runtime Error

Solution code:
import os, sys, re, math

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

match = [-1,2,5,5,4,5,6,3,7,6]
memo = {}

def doit(m):
    if m in memo:
        return memo[m]
    if m == 0:
        return ""

    ret = None
    for a in A:
        tmp = None
        if m - match[a] >= 0:
            tmp = doit(m - match[a])
            if tmp is not None:
                tmp = max(str(a) + tmp, tmp + str(a))
                if ret is not None:
                    if len(ret) < len(tmp) or (len(ret) == len(tmp) and tmp > ret):
                        ret = tmp
                else:
                    ret = tmp

    memo[m] = ret
    return ret

print(doit(N))

Submission status: Runtime Error

Solution code:
import os, sys, re, math

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

match = [-1,2,5,5,4,5,6,3,7,6]
memo = {}

def doit(m):
    if m in memo:
        return memo[m]
    if m == 0:
        return ""

    ret = None
    for a in A:
        tmp = None
        if m - match[a] >= 0:
            tmp = doit(m - match[a])
            if tmp is not None:
                tmp = str(a) + tmp
                if ret is not None:
                    if len(ret) < len(tmp) or (len(ret) == len(tmp) and tmp > ret):
                        ret = tmp
                else:
                    ret = tmp

    memo[m] = ret
    return ret

print(doit(N))

Submission status: Runtime Error

Solution code:
import os, sys, re, math

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

match = [-1,2,5,5,4,5,6,3,7,6]
memo = {}

def doit(m):
    if m in memo:
        return memo[m]

    max_v = 0
    for a in A:
        if m - match[a] == 0:
            max_v = max(int(max_v), int(str(a)))
        elif m > match[a]:
            tmp = doit(m - match[a])
            if tmp != '0':
                max_v = max(int(max_v), int(str(a) + doit(m - match[a])))

    memo[m] = str(max_v)
    return str(max_v)

print(doit(N))

Submission status: Runtime Error

Solution code:
import os, sys, re, math

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

match = [-1,2,5,5,4,5,6,3,7,6]
memo = {}

def doit(m):
    if m in memo:
        return memo[m]
    if m <= 0:
        return ''

    max_v = '0'
    for a in A:
        tmp = doit(m - match[a])
        if m >= match[a] and tmp is not None:
            max_v = max(max_v, str(a) + doit(m - match[a]),key= lambda x: int(x))

    if max_v != '0':
        memo[m] = max_v
        return max_v
    else:
        return None

print(doit(N))

Submission status: Runtime Error

Solution code:
import os, sys, re, math

N,M = list(map(int,input().split(' ')))
A = list(map(int,input().split(' ')))
print(A)

match = [-1,2,5,5,4,5,6,3,7,6]
memo = {}

def doit(m):
    if m in memo:
        return memo[m]
    if m <= 0:
        return ''

    max_v = '0'
    for a in A:
        tmp = doit(m - match[a])
        if m >= match[a] and tmp is not None:
            max_v = max(max_v, str(a) + doit(m - match[a]),key= lambda x: int(x))

    if max_v != '0':
        memo[m] = max_v
        return max_v
    else:
        return None

print(doit(N))

Submission status: Runtime Error

Solution code:
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)))

Submission status: Runtime Error

Solution code:
import os, sys, re, math

N,M = list(map(int,input().split(' ')))
A = list(map(int,input().split(' ')))
print(A)

match = [-1,2,5,5,4,5,6,3,7,6]
memo = {}

def doit(m):
    if m in memo:
        return memo[m]

    max_v = '-9'
    for a in A:
        if m - match[a] == 0:
            max_v = max(max_v, str(a), key=lambda x: int(x))
        elif m - match[a] >= 0:
            max_v = max(max_v, doit(m - match[a]) + str(a), key=lambda x: int(x))
    if max_v != '':
        memo[m] = str(max_v)
        return str(max_v)
    else:
        return '-9'

print(doit(N))

Submission status: Runtime Error

Solution code:
#解答例
N,M=map(int,input().split())
A=list(map(int,input().split()))#使える数字の種類
weight=[0,2,5,5,4,5,6,3,7,6]#作るのに何本必要か、また0は作れないので0になっている
dp=[-1]*(N+1)#とりあえずこれくらい確保しておけばok
dp[0]=0#0本では0しか作れない
#dp[i]はちょうどi本で作れる最高の数を入れることにする
for i in range(N+1):#N本あるから、一本ずつ増やしていって最大N本
    if dp[i] == -1:continue
    for a in A:
        if i+weight[a]<N+1:#今あるi本にa本を加えてもN本を超えないか
            dp[i+weight[a]]=max(dp[i+weight[a]],dp[i]*10+a)#今まで作ったi+weight[a]のときのdpの値と、今作ったdp[i]*10+aの値を比べ、大きい方を格納する
                                                           #なぜdp[i]*10+aになるのかに関しては、右から数字を追加していく場合のみを考えることで、重複せずに全通り試せるから
                                                        　 #もし一通りもなかった場合、-1が格納されたままになるため問題がない
print(dp[N])

Submission status: Runtime Error

Solution code:
import os, sys, re, math

N,M = list(map(int,input().split(' ')))
A = list(map(int,input().split(' ')))
print(A)

match = [-1,2,5,5,4,5,6,3,7,6]
memo = {}

def doit(m):
    if m in memo:
        return memo[m]

    max_v = 0
    for a in A:
        if m - match[a] == 0:
            max_v = max(int(max_v), int(str(a)))
        elif m > match[a]:
            tmp = doit(m - match[a])
            if tmp != '0':
                max_v = max(int(max_v), int(str(a) + doit(m - match[a])))

    memo[m] = str(max_v)
    return str(max_v)

print(doit(N))

Submission status: Runtime Error

Solution code:
l = list(map(int, input().split(' ')))
d = {}  # key=match, val=num
d[2] = [1]
d[3] = [7]
d[4] = [4]
d[5] = [5, 3, 2]
d[6] = [9, 6]
d[7] = [8]
enable = [False] * 10
for a in l:
  enable[a] = True
memo = {}
# マッチをk(=2..7)本使う場合の一番大きい値を総当たり
def f(nokori, current):
  k = (nokori, current)
  if k in memo:
    return memo[k]
  if nokori <= 0:
    return current if nokori == 0 else -1
  temps = []
  for key, nums in list(d.items())[::-1]:
    for num in nums:
      if enable[num]:
        temps.append(f(nokori-key, current*10+num))
        break
  memo[k] = max(temps)
  return memo[k]
 
# 余裕があるうちは一番マッチの本数が少ないモノをヤケクソで詰めまくる
hoge = False
for key, nums in list(d.items()):
    for num in nums:
      if enable[num]:
        hoge = True
        break
    if hoge:
      break
cs = []
while n > 50:
  n -= key
  cs.append(str(num))

# ヤケクソで詰めたやつと総当たりで調べたマックスを並び替えて辞書順で大きくする
ans = str(f(n, 0))
print(''.join(sorted(list(ans) + cs)[::-1]))

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
a = list(map(int, input().split()))
memo = {}
matches = [100, 2, 5, 5, 4, 5, 6, 3, 7, 6]

def doit(n):
    if n == 0:
        return ""
    if not n in memo:
        ret = None
        for d in a:
            m = matches[d]
            if n - m >= 0 and doit(n - m) is not None:
                r = max(doit(n - m) + str(d), str(d) + doit(n - m))
                if ret is None or len(r) > len(ret) or len(r) == len(ret) and r > ret:
                    ret = r
        memo[n] = ret
    return memo[n]

print(doit(n))

Submission status: Runtime Error

Solution code:
NUM = (None, 2, 5, 5, 4, 5, 6, 3, 7, 6)

nSticks, n = map(int, input().split())
a = list(map(int, input().split()))

# maximum value to make using exactly sticks
dp = [0] * (nSticks + 1)
for digit in a:
    if NUM[digit] <= nSticks:
        dp[NUM[digit]] = digit
for sticks in range(2, nSticks + 1):
    for digit in a:
        if dp[sticks - NUM[digit]] > 0 and sticks - NUM[digit] >= 0:
            dp[sticks] = max(dp[sticks], dp[sticks - NUM[digit]] * 10 + digit)
print(dp[-1])

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort(reverse=True)
nums=[0,2,5,5,4,5,6,3,7,6]
dp=[-1]*(n+1)
dp[0]=0
for i in range(1,n+1):
    for x in a:
        if i-nums[x]>=0:
            dp[i]=max(dp[i-nums[x]]+1,dp[i])
k=dp[n]
ans=[]
for i in range(k):
    for x in a:
        if dp[n-nums[x]]==dp[n]-1:
            n-=nums[x]
            ans.append(x)
            break
print("".join(list(map(str,ans))))

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
a = list(map(int, input().split()))

x = [-float('inf')] * (n + 1)
x[0] = 0
l = [0] * (n + 1)
_c = [2,5,5,4,5,6,3,7,6]
c = dict()
for i in range(m):
    c[a[i]] = _c[a[i] - 1]
# print(c)

for i in range(1, n + 1):
    tmp_xl = []
    for digit in c.keys():
        left = i - c[digit]
        if left >= 0:
            tmp_xl.append([digit * (10 ** l[left]) + x[left], l[left] + 1])

    if len(tmp_xl):
        tmp_xl = sorted(tmp_xl, key=lambda x:x[0])
        x[i] = tmp_xl[-1][0]
        l[i] = tmp_xl[-1][1]
print(x[-1])

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

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

COUNT = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]

dic = {}
for a in A:
    dic[COUNT[a]] = a

C = sorted(dic.keys(), key=lambda x: -dic[x])
min_c = min(C)
C.remove(min_c)
#print(C)

def dfs(remain, l, now, L):
    #print(remain, l, now)
    if remain == 0:
        L.append(now)
        return L
    if l == len(C):
        return L
    loop = remain//(C[l]-min_c)
    for h in reversed(range(loop+1)):
        L = dfs(remain-(C[l]-min_c)*h, l+1, now+[dic[C[l]]]*h, L)
    return L


k = 0
while True:
    r = N%min_c + k*min_c
    p = N//min_c - k
    if r == 0:
        ans = {dic[min_c]: p}
        break
    L = dfs(r, 0, [], [])
    #print(L)
    ans = []
    for now in L:
        l = len(now)
        if l > p: continue
        P = sorted(now+[dic[min_c]]*(p-l), reverse=True)
        #print(P)
        if not ans:
            ans = P
            continue
        ok = True
        for i in range(p):
            if P[i] < ans[i]:
                ok = False
                break
            elif P[i] > ans[i]:
                ok = True
                break
        if ok:
            ans = P

    if ans: break
    k += 1

ans.sort(reverse=True)
print("".join([str(a) for a in ans]))

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)

table = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
a = [table[i] for i in A]

# ちょうどi本のマッチ棒を使って、条件を満たす整数を作るときの最大桁数
INF = float('inf')
dp = [-INF] * (N + 1)
dp[0] = 0
cost = set(a)

for i in range(1, N + 1):
    for j in cost:
        if i - j >= 0 and dp[i] < dp[i - j] + 1:
            dp[i] = dp[i - j] + 1

answer = []
for i in A:
    x = table[i]
    while dp[N] == dp[N - x] + 1:
        answer.append(i)
        N -= x

print(''.join(map(str, answer)))

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)

table = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
a = [table[i] for i in A]

# ちょうどi本のマッチ棒を使って、条件を満たす整数を作るときの最大桁数
INF = 10 ** 9
dp = [-INF] * (N + 1)
dp[0] = 0
cost = set(a)

for i in range(1, N + 1):
    for j in cost:
        if i - j >= 0 and dp[i] < dp[i - j] + 1:
            dp[i] = dp[i - j] + 1

answer = []
for i in A:
    x = table[i]
    while N:
        if dp[N] == dp[N - x] + 1:
            answer.append(i)
            N -= x
        else:
            break

print(''.join(map(str, answer)))

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)

table = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
a = [table[i] for i in A]

# ちょうどi本のマッチ棒を使って、条件を満たす整数を作るときの最大桁数
INF = float('inf')
dp = [-INF] * (N + 1)
dp[0] = 0
cost = set(a)

for i in range(1, N + 1):
    for j in cost:
        if i - j >= 0 and dp[i] < dp[i - j] + 1:
            dp[i] = dp[i - j] + 1

answer = []
for i in A:
    while N:
        if dp[N] == dp[N - table[i]] + 1:
            answer.append(i)
            N -= table[i]
        else:
            break

print(''.join(map(str, answer)))

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()

table = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
a = [table[i] for i in A]

# ちょうどi本のマッチ棒を使って、条件を満たす整数を作るときの最大桁数
INF = float('inf')
dp = [-INF] * (N + 1)
dp[0] = 0
cost = set(a)

for i in range(1, N + 1):
    for j in cost:
        if i - j >= 0 and dp[i] < dp[i - j] + 1:
            dp[i] = dp[i - j] + 1

answer = []
for i in A[::-1]:
    while N:
        if dp[N] == dp[N - table[i]] + 1:
            answer.append(i)
            N -= table[i]
        else:
            break

print(''.join(map(str, answer)))

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
a=list(map(int,input().split()))
mm=[0,2,5,5,4,5,6,3,7,6]

dp=[0]
m = [mm[i] for i in range(10) if i in a]
for i in range(1,n+1):
    tres=[-10**10]
    for sm in m:
        if i - sm >= 0:
            tres.append(dp[i-sm]+1)
    dp.append(max(tres))
k=dp[n]
res = []
a.sort(reverse=True)
while n > 0:
    for sa in a:
        if dp[n-mm[sa]]==dp[n]-1:
            res.append(sa)
            n -= mm[sa]
            break

print("".join(map(str,res)))

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
a=list(map(int,input().split()))
mm=[0,2,5,5,4,5,6,3,7,6]

dp=[0]
m = [mm[i] for i in range(n) if i in a]
for i in range(1,n+1):
    tres=[-10**10]
    for sm in m:
        if i - sm >= 0:
            tres.append(dp[i-sm]+1)
    dp.append(max(tres))
k=dp[n]
res = []
a.sort(reverse=True)
while n > 0:
    for sa in a:
        if dp[n-mm[sa]]==dp[n]-1:
            res.append(sa)
            n -= mm[sa]
            break

print("".join(map(str,res)))

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
a=list(map(int,input().split()))
mm=[0,2,5,5,4,5,6,3,7,6]

dp=[0]
m = [mm[i] for i in range(n) if i in a]
for i in range(1,n+1):
    tres=[-10**10]
    for sm in m:
        if i - sm >= 0:
            tres.append(dp[i-sm]+1)
    dp.append(max(tres))
k=dp[n]
res = []
a.sort(reverse=True)
for i in range(k):
    for sa in a:
        if dp[n-mm[sa]]==dp[n]-1:
            res.append(sa)
            n -= mm[sa]
            break

print("".join(map(str,res)))

Submission status: Runtime Error

Solution code:
# D - Match Matching

N, M = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse = True)

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

dp = [-1] * (N+1) # dp[i]はちょうどi本のマッチ棒で作れる最も桁数の多い整数の桁数

dp[0] = 0
for idx in range(1,N+1):
    tmp = []
    for x in A:
        if idx - n_match[x] >= 0:
            tmp.append(dp[idx - n_match[x]] + 1)
    if tmp:
        dp[idx] = max(tmp)

ans = ""
rest_match = N
while len(ans) <= N//2 and rest_match > 0:
    for x in A:
        if dp[rest_match - n_match[x]] == dp[rest_match] - 1:
            ans += str(x)
            rest_match -= n_match[x]
            break
            
print(ans)

Submission status: Runtime Error

Solution code:
from bisect import bisect_left
N, M = map(int, input().split())
nums = list(map(int, input().split()))
nums.sort(reverse=True)

matchNum = {
    1 : 2,
    2 : 5,
    3 : 5,
    4 : 4,
    5 : 5,
    6 : 6,
    7 : 3,
    8 : 7,
    9 : 6,
}

makeDigit = [0] * (N + 1)
for n in range(1, N + 1):
    d = makeDigit[n]
    for k in nums:
        cnt = n - matchNum[k]
        if cnt >= 0:
            d = max(d, makeDigit[cnt] + 1)
    if makeDigit[n] < d:
        makeDigit[n] = d

ans = []
for d in range(makeDigit[N])[:: -1]:
    for k in nums:
        cnt = N - matchNum[k]
        if makeDigit[cnt] == d:
            ans.append(k)
            N = cnt
            break

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

Submission status: Runtime Error

Solution code:
from bisect import bisect_left
N, M = map(int, input().split())
nums = list(map(int, input().split()))

matchNum = {
    1 : 2,
    2 : 5,
    3 : 5,
    4 : 4,
    5 : 5,
    6 : 6,
    7 : 3,
    8 : 7,
    9 : 6,
}

dp = [''] * (N + 1)
for n in range(1, N + 1):
    for k in nums:
        d = 0
        cnt = n - matchNum[k]
        if cnt >= 0 and (dp[cnt] != '' or (cnt == 0 and dp[n] <= dp[cnt] * 10)):
            oldVal = list(str(dp[cnt]))[:: -1]
            adder = bisect_left(oldVal, str(k))
            newVal = oldVal[:adder] + [str(k)] + oldVal[adder:]
            newVal = int(''.join(newVal[:: -1]))
            d = max(d, newVal)
        if d == 0:
            continue
        elif dp[n] == '':
            dp[n] = d
        else:
            dp[n] = max(dp[n], d)

print(dp[N])

Submission status: Runtime Error

Solution code:
n,m=map(int, input().split())
List=list(map(int, input().split()))
#d=[0]*n*9+[-1]*n*9
print(d)
for i in range(1, n+1):
    d[i]=max(d[i-int("0255456376"[a])]*10+a for a in List)
print(d[n])

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
arr=list(map(int,input().split()))
arr=sorted(arr,reverse=True)
dic={1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}
dp=[0]*(n+1)
for i in range(n+1):
  for val in arr:
    if i-dic[val]<0:
      continue
    else:
      dp[i]=max(dp[i],dp[i-dic[val]]+1)
ans=''
tmp=n
while tmp>0:
  for val in arr:
    if tmp-dic[val]<0:
      continue
    if dp[tmp]==dp[tmp-dic[val]]+1:
      ans+=str(val)
      tmp-=dic[val]
      break
  else:
    break
last=dic[int(ans[-1])]
cand=[]
for val in arr:
  if dic[val]-last==tmp:
    cand.append(val)
cand=sorted(cand,reverse=True)
ans=ans[:-1]+str(cand[0])
print(ans)

Submission status: Runtime Error

Solution code:
N,M = map(int, input().split())
A = [int(a) for a in input().split()]

data = {1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6}
inf = -10**9
dp = [inf for i in range(N+1)]
dp[0] = 0
for i in range(1, N+1):
    for j in range(M):
        if i-data[A[j]] >= 0:
            dp[i] = max(dp[i], dp[i-data[A[j]]]+1)
            
ans = 0
A.sort(reverse=True)
n = dp[N]
i = n-1
temp = N
while i >= 0:
    j = 0
    while j < M:
        if dp[temp-data[A[j]]] == dp[temp]-1:
            temp -= data[A[j]]
            ans += A[j]*10**i
            j = M
        j += 1
    i -= 1
    
print(ans)