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: Accepted

Solution code:
MINUS_INF = "-"
MATCHES = [-1, 2, 5, 5, 4, 5, 6, 3, 7, 6]

def char_max(a, b):
    if a == MINUS_INF:
        return b
    la, lb = len(a), len(b)
    if la < lb:
        return b
    elif la == lb and a < b:
        return b
    return a


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

dp = [MINUS_INF]*(10**4+10)
dp[0] = ""
for i in range(N+1):
    if dp[i] == MINUS_INF:
        continue
    for a in A:
        # 配るdp?
        dp[i+MATCHES[int(a)]] = char_max(
            dp[i+MATCHES[int(a)]],
            dp[i] + a
        )

print(dp[N])

Submission status: Accepted

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

#import fractions #fractions.gcd() python~3.4
sys.setrecursionlimit(1000000)

N, M = map(int,input().split())
A = list(map(int, input().split()))
INF = 1e+10
def f(x):
    if x == 1:
        return 2
    if x == 2:
        return 5
    if x == 3:
        return 5
    if x == 4:
        return 4
    if x == 5:
        return 5
    if x == 6:
        return 6
    if x == 7:
        return 3
    if x == 8:
        return 7 
    if x == 9:
        return 6

A.sort(reverse=True)

dp=[-INF]*(N+1)
dp[0] = 0
for i in range(1,N+1):
    for j in range(M):
        if i-f(A[j]) >= 0:
            dp[i] = max(dp[i],dp[i-f(A[j])]+1)
 
ans = ""
remain = dp[N]
match = N

while match > 0:
    for i in range(M):
        if match - f(A[i]) >=0 and dp[match - f(A[i])] == remain - 1:
            ans += str(A[i])
            match -= f(A[i])
            remain -= 1
            
            break
            
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

n, m = map(int, input().split())
A = list(map(int, input().split()))
dic = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
usable = defaultdict(int)

for num in A:
    use = dic[num]
    if usable[use] < num:
        usable[use] = num

DP = [-1]*(n+10)
DP[0] = 0

for i in range(n):
    digits = DP[i]
    if digits < 0:
        continue

    for use in usable.keys():
        if i+use <= n and DP[i+use] < digits + 1:
            DP[i+use] = digits + 1
        else:
            continue

digits = DP[n]
num_of_match = n
ans = ''

for _ in range(n):
    if digits == 0:
        break

    for num in sorted(usable.values(), reverse=True):
        use = dic[num]
        if DP[num_of_match - use] == digits - 1:
            digits -= 1
            num_of_match -= use
            ans += str(num)
            break
        else:
            continue

print(ans)

Submission status: Accepted

Solution code:
def main():
    N, M = map(int, input().split())
    A = [int(a) for a in input().split()]
    d1 = {1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6}

    # for a given number of matches, give the largest digit
    d2 = dict()
    for a in A:
        if d1[a] not in d2: d2[d1[a]] = a
        else: d2[d1[a]] = max(a, d2[d1[a]])

    # for these digit, give the match count
    lv = []
    for a in d2.values(): lv.append(a)

    dp = [None for _ in range(N+1)]
    dp[0] = ""
    for i in range(1, N+1):
        for a in lv:
            j = i - d1[a]
            if j >= 0 and dp[j] != None:
                if dp[i] == None:
                    dp[i] = dp[j] + str(a)
                elif len(dp[i]) < len(dp[j]) + 1:
                    dp[i] = dp[j] + str(a)
                elif len(dp[i]) == len(dp[j]) + 1:
                    dp[i] = max(dp[i], dp[j] + str(a))
                # print(dp[i], i)
    # print(dp)
    return dp[N]




if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
AList = list(map(int,input().split()))
AList.sort(reverse=True)
NList=[0,2,5,5,4,5,6,3,7,6]
CList=[]
minnum = (-1)*(10**10)
dp = [0]*(N+1)

for a in AList:
    u = NList[a]
    if (u in CList) == False:
        CList.append(u)

dp[0] = 0
for n in range(1,N+1):
    max1 = minnum
    for c in CList:
        if c <= n:
            if dp[n-c] == minnum:
                num = minnum
            else:
                num = dp[n-c]+1
            if max1 < num:
                max1 = num
    dp[n] = max1
keta = dp[N]
s = ''
nn = N
for n in range(keta):
    for a in AList:
        if nn >= NList[a] and dp[nn-NList[a]] == dp[nn]-1:
            s += str(a)
            nn -= NList[a]
            break
print(s)

Submission status: Accepted

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

su = [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 j in A:
    if i >= su[j]:
      dp[i] = max(dp[i],dp[i-su[j]]*10+j)
      
print(dp[-1])

Submission status: Accepted

Solution code:
I = lambda: map(int, input().split())
nums = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
minf = -float('inf')
n, _ = I()
*A, = sorted(I(), reverse = True)
digs = [0]*(n+1)+[-1]*9
for i in range(1, n+1):
    d = []
    for a in A :
        before = i-nums[a]
        d.append(minf if before < 0 else digs[before]+1)
    digs[i] = max(d)
ans = []
while n > 0:
    for a in A:
        if digs[n-nums[a]] == digs[n]-1:
            ans.append(a)
            n -= nums[a]
            break
print(*ans, sep = '')

Submission status: Accepted

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

needs = [9,2,5,5,4,5,6,3,7,6]
table = [-1] * (n+10)
table[0] = 0

for i in range(n):
    if table[i] != -1:
        for j in a:
            table[i + needs[j]] = max(table[i]*10 + j, table[i + needs[j]])

print(table[n])

Submission status: Accepted

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


dp = [None  for _ in range(n+1)]
dp[0] = 0
for i in range(0, n+1):
  for j in a:
    if i+ use[j] < n+1 and dp[i] != None:
      if dp[i+use[j]] == None:
        dp[i+use[j]] = dp[i]*10+j
      else:
        dp[i+use[j]] = max(dp[i]*10+j, dp[i+use[j]])

print(dp[n])

Submission status: Accepted

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):
    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[n])

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
a = list(map(int, input().split()))
mn = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]

msort = lambda s: -s[0]

b = list(map(lambda i: [i, mn[i]], a))
b.sort(key = msort)
dp = [-100] * (N + 1)
dp[0] = 0
for i in range(2, N + 1):
  for n in b:
    if i >= n[1] and dp[i - n[1]] >= 0:
      dp[i] = max([dp[i], dp[i - n[1]] + 1])

match = N
ans = ''
while match > 0:
  for n in b:
    if match >= n[1] and dp[match] == dp[match - n[1]] + 1:
      ans += str(n[0])
      match -= n[1]
      break
    
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

dp = dict.fromkeys(range(n + 1))  # dp[n]: n本使うときの桁数
dp[0] = 0

num = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
anum = sorted(
    dict(filter(lambda e: e[0] in a, num.items())).items(), reverse=True
)  # 後の計算用にsortしておく

for i in range(n):
    dp[i + 1] = -float("inf")
    for e in anum:
        if i + 1 - e[1] >= 0:
            dp[i + 1] = max(dp[i + 1], dp[i + 1 - e[1]] + 1)

ans = ""
while dp[n] > 1:
    for e in anum:  # anum は降順sortされているので, 大きい順に確認
        if n - e[1] >= 0:
            if dp[n - e[1]] == dp[n] - 1:
                ans += str(e[0])
                n -= e[1]
                break

# 末尾桁は n =0(ちょうど使い切るように決定)
ans += str(list(filter(lambda e: e[1] == n, anum))[0][0])

print(ans)

Submission status: Accepted

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

INF = 10**9
matches = [2, 5, 5, 4, 5, 6, 3, 7, 6]

dp = [-INF for _ in range(N+100)]
dp[0] = 0

for i in range(N+1):
    for a in As:
        dp[i+matches[a-1]] = max(dp[i+matches[a-1]], dp[i]+1)

ans = ''
while N != 0:
    for a in As:
        if dp[N-matches[a-1]] == dp[N]-1:
            ans = ans+str(a)
            N -= matches[a-1]
            break

print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
A = sorted([int(i) for i in input().split()], reverse=True)
INF = 10**10
matches = [2, 5, 5, 4, 5, 6, 3, 7, 6]

dp = [-INF for _ in range(N+100)]
dp[0] = 0

for i in range(N+1):
    for a in A:
        dp[i+matches[a-1]] = max(dp[i+matches[a-1]], dp[i]+1)

ans = ''
while N != 0:
    for a in A:
        if dp[N-matches[a-1]] == dp[N]-1:
            ans = ans+str(a)
            N -= matches[a-1]
            break

print(ans)

Submission status: Accepted

Solution code:
n , m = map(int, input().split(' '))
s = [0,2,5,5,4,5,6,3,7,6]
a = list(map(int, input().split(' ')))
r = []
for i in range(len(a)):
    r.append([s[a[i]],a[i]])
r.sort()
d = [-1]*(n+1)
d[0] = 0
for i in range(1,n+1):
    j = 0
    while j < len(a):
        if i-s[r[j][1]] < 0:
            j += 1
        elif d[i-s[r[j][1]]] >= 0:
            d[i] = d[i-s[r[j][1]]] +1
            break
        else:
            j+= 1
result = []
a.sort(reverse = True)
while n > 0:
    j = 0
    while j < len(a):
        if n < s[a[j]]:
            j += 1
        elif d[n-s[a[j]]] +1 == d[n]:
            result.append(a[j])
            n -= s[a[j]]
            break
        else:
            j += 1
print(''.join(list(map(str, result))))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, fractions, itertools

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

def solve(N: int, M: int, A: "List[int]"):
    dp = [-1] * (N+10) # 初期化
    dp[0] = 0 # 初期化
    for i in range(N-1): # 各桁について考える
        for s in A: # 各使える数字をみる
            if dp[i] == -1 and i!=0: # 条件を満たすように作れない場合、continue
                continue
            if dp[i + l[s]] < dp[i]*10+s:
                dp[i + l[s]] = dp[i]*10+s
    print(dp[N])
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [ int(next(tokens)) for _ in range(M) ]  # type: "List[int]"
    solve(N, M, A)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

dp = [-1 for i in range(N+10)]
l = [0,2,5,5,4,5,6,3,7,6]
dp[0] = 0
for i in range(N-1):
    for s in A:
        if dp[i] == -1 and i!=0:
            continue
        if dp[i + l[s]] < dp[i]*10+s:
            dp[i + l[s]] = dp[i]*10+s
print(dp[N])

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
*a, = map(int, input().split())
sorted_a = sorted(a, reverse=True)

needs = [9,2,5,5,4,5,6,3,7,6]
table = [-1] * (n+10)
table[0] = 0

for i in range(n):
    if table[i] != -1:
        for j in sorted_a:
            table[i + needs[j]] = max(table[i]*10 + j, table[i + needs[j]])

print(table[n])

Submission status: Accepted

Solution code:
# ABC 118 D

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

    costs = [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 a in A:
            if i - costs[a] < 0:
                continue
            dp[i] = max(dp[i-costs[a]] + 1, dp[i])

    ans = ""
    remain = dp[N]
    match = N

    minCosts = 10
    for a in A:
        minCosts = min(minCosts, costs[a])

    while match > 0:
        for a in A:
            if match - costs[a] < 0 or 1<= match - costs[a] < minCosts:
                continue

            if dp[match-costs[a]] == remain-1:
                ans += str(a)
                match -= costs[a]
                remain -= 1
                break

    print(ans)


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)
cost = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [-1] * (n + 10)
dp[0] = 0

for i in range(n):
    for ai in a:
        if dp[i] >= 0:
            dp[i + cost[ai]] = dp[i] + 1

ans = []
i = n
while dp[i] > 0:
    for ai in a:
        if dp[i - cost[ai]] == dp[i] - 1:
            ans.append(str(ai))
            i -= cost[ai]
            break

print(''.join(ans))

Submission status: Accepted

Solution code:
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
# 一次元累積和
from itertools import accumulate
from bisect import bisect_left, bisect_right

import re
# import numpy as np
# from scipy.misc import comb

# 再帰がやばいとき
# import sys
# sys.setrecursionlimit(10**9)

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e50)
MOD = int(1e9)+7 # 10^9 + 7

# field[H][W]
def create_grid(H, W, value = 0):
    return [[ value for _ in range(W)] for _ in range(H)]

########

def main():
    H, M = l_inpl()
    A = l_inpl()
    d = {
        "1": 2,
        "2": 5,
        "3": 5,
        "4": 4,
        "5": 5,
        "6": 6,
        "7": 3,
        "8": 7,
        "9": 6
    }

    new_d = {}
    for Ai in A:
        new_d[Ai] = d[str(Ai)]

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

    for i in range(1, H+1):
        tmp = []
        for k, v in new_d.items():
            if i-v < 0:
                tmp.append(-INF)
            else:
                tmp.append(dp[i-v]+1)
        dp[i] = max(tmp)

    s = sorted(new_d.items(), key=lambda x:-x[0])

    ans = ""
    remain = H

    while remain > 0:
        for k, v in s:
            if remain >= v and dp[remain-v] != -INF and dp[remain-v] == dp[remain] - 1: # 一桁だけ減少している
                ans += str(k)
                remain -= v
                break
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))
num = [2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = {0: 0}
for i in range(1, N + 1):
    dp[i] = -float('inf')
    for j in range(8, -1, -1):
        if j + 1 in A and i - num[j] >= 0:
            dp[i] = max(dp[i], dp[i - num[j]] + 1)

ans = []
while N > 0:
    for j in range(8, -1, -1):
        if j + 1 in A and N - num[j] in dp and dp[N - num[j]] == dp[N] - 1:
            ans.append(j + 1)
            N -= num[j]
            break

print(*ans, sep='')

Submission status: Accepted

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

c = [0] * 8

mt = set()
for aa in a:
    if aa == 1:
        c[2] = 1
        mt.add(2)
    if aa == 2:
        c[5] = max(c[5], 2)
        mt.add(5)
    if aa == 3:
        c[5] = max(c[5], 3)
        mt.add(5)
    if aa == 4:
        c[4] = 4
        mt.add(4)
    if aa == 5:
        c[5] = max(c[5], 5)
        mt.add(5)
    if aa == 6:
        c[6] = max(c[6], 6)
        mt.add(6)
    if aa == 7:
        c[3] = 7
        mt.add(3)
    if aa == 8:
        c[7] = 8
        mt.add(7)
    if aa == 9:
        c[6] = max(c[6], 9)
        mt.add(6)
dp = [-1] * (n+1)
dp[0] = 0
for i in range(n+1):
    tmp = [dp[i]]
    for mtt in mt:
        if i-mtt>= 0 and dp[i-mtt] >= 0:
            tmp.append(dp[i-mtt]*10+c[mtt])
    dp[i] = max(tmp)
print(dp[n])

Submission status: Accepted

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

dp=[-1]*(n+10) #needsを探索できるようにするため
dp[0]=0

for i in range(n): #小さい桁数から全探索する
  if dp[i]!=-1:
    for k in sorted(a, reverse=True): #aのうち大きい数字から試す
      matchs = needs[k] #必要なマッチの本数
      dp[i+matchs] = max(dp[i+matchs], dp[i]*10+k) #dpからの遷移
print(dp[n])

Submission status: Accepted

Solution code:
N, M, *A = map(int, open(0).read().split())

match = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
dp = [[0] * M for _ in range(N + 1)]

for i in range(N + 1):
    for j in range(M):
        for k in range(M):
            if (i - match[A[k]] == 0) or \
                   (i - match[A[k]] > 0 and dp[i - match[A[k]]][j] != 0):
                dp[i][k] = max(dp[i][k], 
                               dp[i - match[A[k]]][j] * 10 + A[k])

print(max(dp[-1]))

Submission status: Accepted

Solution code:
def main():

    """ convenient functions
    # for i, a in enumerate(iterable)
    # q, mod = divmod(a, b)
    # divmod(x, y) returns the tuple (x//y, x%y)
    # Higher-order function: reduce(operator.mul, xyz_count, 1)
    # manage median(s) using two heapq https://atcoder.jp/contests/abc127/tasks/abc127_f
    """

    """convenient decorator
    # @functools.lru_cache():
    # to facilitate use of recursive function
        # ex:
        # from functools import lru_cache
        # import sys
        # sys.setrecursionlimit(10**9)
        # @lru_cache(maxsize=None)
        # def fib(n):
        #     if n < 2:
        #         return n
        #     return fib(n-1) + fib(n-2)
        # print(fib(1000))
    """
    
    # import numpy as np
    import sys
    sys.setrecursionlimit(10**7)
    from itertools import accumulate, combinations, permutations, product # https://docs.python.org/ja/3/library/itertools.html
    # accumulate() returns iterator! to get list: list(accumulate())
    from math import factorial, ceil, floor, sqrt
    def factorize(n):
        """return the factors of the Arg and count of each factor
        
        Args:
            n (long): number to be resolved into factors
        
        Returns:
            list of tuples: factorize(220) returns [(2, 2), (5, 1), (11, 1)]
        """
        fct = []  # prime factor
        b, e = 2, 0  # base, exponent
        while b * b <= n:
            while n % b == 0:
                n = n // b
                e = e + 1
            if e > 0:
                fct.append((b, e))
            b, e = b + 1, 0
        if n > 1:
            fct.append((n, 1))
        return fct
    def combinations_count(n, r):
        """Return the number of selecting r pieces of items from n kinds of items.
        
        Args:
            n (long): number
            r (long): number
        
        Raises:
            Exception: not defined when n or r is negative
        
        Returns:
            long: number
        """
        # TODO: How should I do when n - r is negative?
        if n < 0 or r < 0:
            raise Exception('combinations_count(n, r) not defined when n or r is negative')
        if n - r < r: r = n - r
        if r < 0: return 0
        if r == 0: return 1
        if r == 1: return n
        numerator = [n - r + k + 1 for k in range(r)]
        denominator = [k + 1 for k in range(r)]
        for p in range(2,r+1):
            pivot = denominator[p - 1]
            if pivot > 1:
                offset = (n - r) % p
                for k in range(p-1,r,p):
                    numerator[k - offset] /= pivot
                    denominator[k] /= pivot
        result = 1
        for k in range(r):
            if numerator[k] > 1:
                result *= int(numerator[k])
        return result
    def combinations_with_replacement_count(n, r):
        """Return the number of selecting r pieces of items from n kinds of items allowing individual elements to be repeated more than once.
        
        Args:
            n (long): number
            r (long): number
        
        Raises:
            Exception: not defined when n or r is negative
        
        Returns:
            long: number
        """
        if n < 0 or r < 0:
            raise Exception('combinations_with_replacement_count(n, r) not defined when n or r is negative')
        elif n == 0:
            return 1
        else:
            return combinations_count(n + r - 1, r)
    from bisect import bisect_left, bisect_right
    from collections import deque, Counter, defaultdict # https://docs.python.org/ja/3/library/collections.html#collections.deque
    from heapq import heapify, heappop, heappush, heappushpop, heapreplace,nlargest,nsmallest # https://docs.python.org/ja/3/library/heapq.html
    from copy import deepcopy, copy # https://docs.python.org/ja/3/library/copy.html
    import operator
    from operator import itemgetter
    # ex1: List.sort(key=itemgetter(1))
    # ex2: sorted(tuples, key=itemgetter(1,2))
    from functools import reduce, lru_cache
    def chmin(x, y):
        """change minimum
        if x > y, x = y and return (x, True).
        convenient when solving problems of dp[i]
        
        Args:
            x (long): current minimum value
            y (long): potential minimum value
        
        Returns:
            (x, bool): (x, True) when updated, else (x, False)
        """
        if x > y:
            x = y
            return (x, True)
        else:
            return (x, False)
    def chmax(x, y):
        """change maximum
        if x < y, x = y and return (x, True).
        convenient when solving problems of dp[i]
        
        Args:
            x (long): current maximum value
            y (long): potential maximum value
        
        Returns:
            (x, bool): (x, True) when updated, else (x, False)
        """
        if x < y:
            x = y
            return (x, True)
        else:
            return (x, False)

    from fractions import gcd # Deprecated since version 3.5: Use math.gcd() instead.
    def gcds(numbers):
        return reduce(gcd, numbers)
    def lcm(x, y):
        return (x * y) // gcd(x, y)
    def lcms(numbers):
        return reduce(lcm, numbers, 1)

    # first create factorial_list
    # fac_list = mod_factorial_list(n)
    INF = 10 ** 18
    MOD = 10 ** 9 + 7
    modpow = lambda a, n, p = MOD: pow(a, n, p) # Recursive function in python is slow!
    def modinv(a, p = MOD):
        # evaluate reciprocal using Fermat's little theorem:
        # a**(p-1) is identical to 1 (mod p) when a and p is coprime
        return modpow(a, p-2, p)
    def modinv_list(n, p = MOD):
        if n <= 1:
            return [0,1][:n+1]
        else:
            inv_t = [0,1]
            for i in range(2, n+1):
                inv_t += [inv_t[p % i] * (p - int(p / i)) % p]
            return inv_t
    def modfactorial_list(n, p = MOD):
        if n == 0:
            return [1]
        else:
            l = [0] * (n+1)
            tmp = 1
            for i in range(1, n+1):
                tmp = tmp * i % p
                l[i] = tmp
            return l
    def modcomb(n, k, fac_list = [], p = MOD):
        # fac_list = modfactorial_list(100)
        # print(modcomb(100, 5, modfactorial_list(100)))
        from math import factorial
        if n < 0 or k < 0 or n < k: return 0
        if n == 0 or k == 0: return 1
        if len(fac_list) <= n:
            a = factorial(n) % p
            b = factorial(k) % p
            c = factorial(n-k) % p
        else:
            a = fac_list[n]
            b = fac_list[k]
            c = fac_list[n-k]
        return (a * modpow(b, p-2, p) * modpow(c, p-2, p)) % p
    def modadd(a, b, p = MOD):
        return (a + b) % MOD
    def modsub(a, b, p = MOD):
        return (a - b) % p
    def modmul(a, b, p = MOD):
        return ((a % p) * (b % p)) % p
    def moddiv(a, b, p = MOD):
        return modmul(a, modpow(b, p-2, p))

    class UnionFindTree:
        """union find tree class
        TODO: fix this description...
        how to use (example):
        >>  uf = UnionFindTree(N) 
        >>  if uf.find_root(a) == uf.find_root(b):
        >>      do something
        >>  else:
        >>      do something
        >>      uf.unite(a, b)
        """
        def __init__(self, N):
            self.root = [-1] * (N+1)
            self.rank   = [0]  * (N+1)
            self.connected_num = [1] * (N+1)
    
        def find_root(self,x):
            root = self.root
            while root[x] != -1:
                x = root[x]
            return x
    
        def unite(self,x,y):
            root = self.root
            rank = self.rank
            connected_num = self.connected_num
            find_root = self.find_root
    
            rx = find_root(x)
            ry = find_root(y)
            if rx != ry:
                if rank[rx] < rank[ry]:
                    root[rx] = ry
                    rx,ry = ry,rx
                else:
                    if rank[rx] == rank[ry]:
                        rank[rx] += 1
                    root[ry] = rx       
                connected_num[rx] += connected_num[ry]

    """ initialize variables and set inputs
    # initialize variables
        # to initialize list, use [0] * n
        # to initialize two dimentional array, use [[0] * N for _ in range(N)]
    # set inputs
        # open(0).read() is a convenient method:
        # ex) n, m, *x = map(int, open(0).read().split())
        #     min(x[::2]) - max(x[1::2])
        # ex2) *x, = map(int, open(0).read().split())
        #     don't forget to add comma after *x if only one variable is used
    # preprocessing
        # transpose = [x for x in zip(*data)]
        # ex) [[1, 2, 3], [4, 5, 6], [7, 8, 9]] => [(1, 4, 7), (2, 5, 8), (3, 6, 9)]
        # flat = [flatten for inner in data for flatten in inner]
        # ex) [[1, 2, 3], [4, 5, 6], [7, 8, 9]] => [1, 2, 3, 4, 5, 6, 7, 8, 9]
    # calculate and output
        # output pattern
        # ex1) print(*l) => when l = [2, 5, 6], printed 2 5 6
    """

    # functions used
    r = lambda: sys.stdin.readline().strip()
    r_int = lambda: int(r())
    R = lambda: list(map(int, r().split()))
    Rmap = lambda: map(int, r().split())
    Rfloat = lambda: list(map(float, r().split()))
    Rtuple = lambda: tuple(map(int, r().split()))

    """ how to treat input
    # single int: int(r())
    # single string: r()
    # single float: float(r())
    # line int: R()
    # line string: r().split()
    # line (str, int, int): [j if i == 0 else int(j) for i, j in enumerate(r().split())]
    # lines int: [R() for _ in range(n)]
    """

    if __name__ != '__main__':
        # for test
        sys.stdin = open('sample.txt')
        
    # ----------------------------------
    # main

    N, M = R()
    A = R()
    A.sort()
    
    Dic = {1: 2, 2: 5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6}
    dp = [-INF] * (N+10)
    dp[0] = 0
    memo = [0] * (N+10)
    for i in A:
        stroke = Dic[i]
        for j in range(N):
            if dp[j] + 1 >= dp[j+stroke]:
                dp[j+stroke] = dp[j] + 1
                memo[j+stroke] = i
    ans = []
    k = N
    while k:
        tmp = memo[k]
        ans.append(tmp)
        k -= Dic[tmp]
    print(*sorted(ans,reverse=True),sep='')
    # end of main
    # ----------------------------------

    """memo: how to use defaultdict of list
    # initialize
    Dic = defaultdict(list)
    # append / extend
    Dic[x].append(y)
    # three methods for loop: keys(), values(), items()
    for k, v in Dic.items():
    """
    
    """memo: how to solve binary problems
    # to make binary digits text
    >>> a = 5
    >>> bin_str_a = format(a, '#06b')
    >>> print(bin_str_a)
    0b0101 # first 2 strings (='0b') indicates it is binary
    """
    
    """memo: how to solve the problem
    creating simple test/answer
    greed
    simple dp
    graph
    """

if __name__ == '__main__':
    main()

Submission status: Accepted

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

costs = [None, 2, 5, 5, 4, 5, 6, 3, 7, 6]

# 優先度：桁数, [要素(降順)]
dp = [[0, []] for _ in range(N + 1)]
for a in A:
	cost = costs[a]
	for n in range(N):
		if n != 0 and dp[n][0] == 0:
			continue
		ni = n + cost
		if N < ni:
			break
		np = [dp[n][0] + 1, sorted(dp[n][1] + [a], reverse=True)]
		if dp[ni] < np:
			dp[ni] = np

print(*sorted(dp[N][1], reverse=True), sep="")

Submission status: Accepted

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

needs = [10,2,5,5,4,5,6,3,7,6]
table = [-1] * (n + 10)
table[0] = 0

for i in range(n):
    if table[i] != -1:
        for number in sorted(a, reverse = True):
            matchs = needs[number]
            if table[i+matchs] == 0:
                table[i+matchs] = table[i] * 10 + number
            else:
                table[i+matchs] = max(table[i+matchs], table[i] * 10 + number)

print(table[n])

Submission status: Accepted

Solution code:
match = [0,2,5,5,4,5,6,3,7,6]
n,m = map(int,input().split())
a = [int(_) for _ in input().split()]
dp = [-1]*(n+10)
dp[0] = 0
for i in range(n+1):
    if dp[i]== -1:
        continue
    else:
        for j in a:
            dp[i+match[j]]= max(dp[i+match[j]],dp[i]*10+j)
print(dp[n])