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:
def intlog10(n):
    if n <= 0:
        return -1
    i = 0
    while 10**i <= n:
        i += 1
    return i-1

N, M = map(int, input().split())
A = [int(a) for a in input().split()]
    
L = [2, 5, 5, 4, 5, 6, 3, 7, 6]
B = [[A[i], L[A[i]-1]] for i in range(M)]



best = sorted(B, key = lambda x: x[1]*10-x[0])[0]

adj = 0
if N > 500:
    adj = (N - 500)//best[1]
    N -= best[1] * adj

X = [0] + [-10**9] * N
bpre = -1
ll = 1
for i in range(1, N+1):
    if i > 50 and i < N-50:
        X[i] = X[i-best[1]]*10 + best[0]
    else:
        for b in B:
            if b[1] <= i:
                if X[i-b[1]] == 0:
                    if b[0] > X[i]:
                        X[i] = b[0]
                        bpre = b
                        ll = 0
                else:
                    if X[i-b[1]]*10 + b[0] < X[i-b[1]] + b[0] * (10**intlog10(X[i-b[1]])):
                        lll = 1

                    if max(X[i-b[1]]*10 + b[0], X[i-b[1]] + b[0] * (10**intlog10(X[i-b[1]]))) > X[i]:
                        X[i] = max(X[i-b[1]]*10 + b[0], X[i-b[1]] + b[0] * (10**intlog10(X[i-b[1]])))
                        ll = lll
                        bpre = b
                

ans = str(X[N])
if adj > 0:
    ans = ans[:50] + str(best[0]) * adj + ans[50:]

print(ans)
# print(len(ans))

Submission status: Accepted

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

dp = [[] for k in range(n+1)]

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

#dpの初期化
for i in range(m):
    if cost[a[i]] <= n:
        dp[cost[a[i]]]= [a[i]]


for i in range(0,n+1):
    for k in range(m):
        if i > cost[a[k]]:
            #print(cost[a[k]])
            tmp = copy.copy(dp[i-cost[a[k]]])
            tmp.append(a[k])
            tmp.sort(reverse = True)
            #print(i,tmp)
            if len(tmp) > len(dp[i]) and len(tmp) != 1:
                dp[i] = tmp
            elif len(tmp) == len(dp[i]) and len(tmp) != 1:
                big = 0

                for s in range(len(tmp)):
                    if tmp[s] > dp[i][s]:
                        big = 1
                        break
                    elif tmp[s] < dp[i][s]:
                        big = 0
                        break
                if(big):
                    dp[i] = tmp
            #print(dp)

ans = ""
for cha in dp[n]:
    ans = ans + str(cha)
print(ans)

Submission status: Accepted

Solution code:
import copy

N, M = map(int, input().split())
A = [int(x) for x in input().split()]
cost = [0,2,5,5,4,5,6,3,7,6]

dp = [[0 for _ in range(10)] for i in range(N+10)]

A = sorted(A, reverse=True)

for num in A:
    c = cost[num]
    if dp[c][0] == 0:
        dp[c][0] = 1
        dp[c][num] = 1

for i in range(1, N+1):
    for num in A:
        c = cost[num]
        prev = copy.deepcopy(dp[i])
        if prev[0] != 0:
            if dp[i + c][0] > dp[i][0] + 1:
                continue
            elif dp[i + c][0] == dp[i][0] + 1:
                nxt = prev
                nxt[num] += 1
                nxt[0] += 1
                for number in range(9, 0, -1):
                    if dp[i + c][number] < nxt[number]:
                        dp[i + c] = copy.deepcopy(nxt)
                        break
                    if dp[i + c][number] > nxt[number]:
                        break
            else:
                nxt = prev
                nxt[num] += 1
                nxt[0] += 1
                dp[i + c] = copy.deepcopy(nxt)

# print(dp[N])
ans = ""
for number in range(9, 0, -1):
    for _ in range(dp[N][number]):
        ans = ans + str(number)

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)

N, M = map(int, input().split())
numbers = list(map(int, input().split()))
costs = [2,5,5,4,5,6,3,7,6] # <- 1,2,3,4,5,6,7,8,9
costmap = {}
for num in numbers:
  cost = costs[num-1]
  if cost in costmap and num < costmap[cost]:
    continue
  costmap[cost] = num

from functools import lru_cache
@lru_cache(None)
def recursive(remain=N):
  maxval = costmap[remain] if remain in costmap else 0
  for cost, num in costmap.items():
    if remain > cost:
      val = recursive(remain-cost)
      if val == 0:
        continue
      val = val * 10 + num
      if val > maxval:
        maxval = val
  return maxval
 
print(recursive(N))

Submission status: Accepted

Solution code:
# cook your dish here
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
n,m = map(int,input().split())
a = list(map(int,input().split()))
if 2 in a and 3 in a:
    a.remove(2)
    m -=1
if 2 in a and 5 in a:
    a.remove(2)
    m -=1
if 3 in a and 5 in a:
    a.remove(3)
    m -=1
if 6 in a and 9 in a:
    a.remove(6)
    m -=1
for w in range(1,10):
    if n < f(w) and w in a:
        a.remove(w)
        m -=1
a.sort()
m = len(a)

dp = [[0]*(m+1) for i in range(n+2)]


def g(k):
    cand = [0]*(m+1)
    for i in range(m):
        if k - f(a[i])>=0:
            if cand[0] <= dp[k-f(a[i])][0]+1 and dp[k-f(a[i])][0] != 0:
                for r in range(m+1):
                    cand[r] = dp[k-f(a[i])][r]
                cand[0] += 1
                cand[i+1] += 1
    if sum(cand) != 0:
        dp[k] = cand
for i in range(m):
    if f(a[i]) <= n:
        dp[f(a[i])][0] = 1
        dp[f(a[i])][i+1] = 1

for j in range(1,n+1):
    g(j)

ass = ''

for i in range(m):
    for k in range(dp[n][m-i]):
        ass += str(a[m-i-1])
print(ass)

Submission status: Accepted

Solution code:
import math
N, M = map(int, input().split())
A = [int(x) for x in input().split()]
mp = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
dp = [''] * (N+1)
for i in range(1, N+1):
    cand = []
    for x in A:
        if i - mp[x] < 0:
            continue
        if dp[i-mp[x]] == '' and mp[x] != i:
            continue
        if dp[i-mp[x]] == '':
            cand.append(x)
        else:
            before = dp[i - mp[x]]
            pre = (int(math.log10(before)) + 1) * 10 * x + before
            suf = before * 10 + x
            cand.append(max(pre, suf))
    if cand:
        dp[i] = max(cand)
    else:
        dp[i] = ''
print(dp[N])

Submission status: Accepted

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

d = [2,5,5,4,5,6,3,7,6]
a.sort()
dic = {}
for ai in a:
    dic[d[ai-1]] = ai

dp = [""] + ["0"] * n
for i in range(n + 1):
    for j, k in dic.items():
        if i - j >= 0 and dp[i - j] != '0':
            temp = str(k) + dp[i - j]
            if len(temp) >= len(dp[i]) and temp > dp[i]:
                dp[i] = temp
                
print(dp[-1])

Submission status: Accepted

Solution code:
n,m = map(int, input().split())
b = [0,2,5,5,4,5,6,3,7,6]
a = [0]+list(map(int, input().split()))
f = [-1]*10010
f[0]=0
for i in range(1,n+1):
    for j in range(1,m+1):
        x = a[j]
        if(i-b[x]<0):
            continue
        f[i] = max(f[i],f[i-b[x]]*10 + x)
print(f[n])

Submission status: Accepted

Solution code:
from copy import deepcopy
NUM = [10000, 2 , 5 , 5 , 4 , 5 , 6 , 3 , 7 , 6]
n, m = map(int, input().split())
aa = list(map(int, input().split()))

dp = [[-1 for j in range(9)] for i in range(n + 1)]
for j in range(9):
    dp[0][j] = 0
for i in range(1, n + 1):
    for a in aa:
        if i - NUM[a] >= 0 and dp[i - NUM[a]][0] != -1:
            tmp = deepcopy(dp[i - NUM[a]])
            tmp[9 - a] += 1
            if sum(tmp) > sum(dp[i]) or (sum(tmp) == sum(dp[i]) and tmp > dp[i]):
                dp[i] = tmp
ans = ""
for j in range(9):
    for k in range(dp[n][j]):
        ans += str(9 - j)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
math_inf = float('inf')  # the Python of AtCoder is too old

def solve(n, m, a):
    cost = [ math_inf, 2, 5, 5, 4, 5, 6, 3, 7, 6 ]
    dp = [ None ] * (n + 1)
    dp[0] = 0
    for i in range(1, len(dp)):
        dp[i] = max([ dp[i - cost[a_i]] * 10 + a_i for a_i in a if cost[a_i] <= i ] + [ - math_inf ])
    return str(dp[n])


n, m = map(int, input().split())
a = list(map(int, input().split()))
print(solve(n, m, a))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(150000)


d = [2,5,5,4,5,6,3,7,6]

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

memo = [ "-" for _ in range(N + 1)]

def find(N):
    global memo
    if memo[N] != "-":
        return memo[N]

    mval = ""
    val = ""
    for a in A:
        if d[a - 1] < N:
            val = find(N - d[a - 1])
            if val == "":
                continue
            val = val + str(a)
        elif d[a - 1] == N:
            val = str(a)
        else:
            continue

        if len(mval) < len(val) or (len(mval) == len(val) and mval < val):
            mval = val
    memo[N] = mval
    return memo[N]

m = find(N)
print(m)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))
C = (100, 2, 5, 5, 4, 5, 6, 3, 7, 6)

dp = [[0 for _ in range(10)] for _ in range(N + 1)]
dp2 = [-100 for _ in range(N + 1)]
dp2[0] = 0

for i in range(2, N+1):
    x = -1
    opt = -1
    for a in A:
        c = C[a]
        if i >= c and (dp2[i - c] > opt or (dp2[i - c] == opt and a > x)):
            x = a
            opt = dp2[i - c]
    if x == -1:
        continue
    dp2[i] = dp2[i - C[x]] + 1
    c = C[x]
    for a in A:
        if x == a:
            dp[i][a] = dp[i - c][a] + 1
        else:
            dp[i][a] = dp[i - c][a]

ans = ''.join(str(a) * dp[N][a] for a in sorted(A, reverse=True))
print(ans)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
import math
import bisect
import random
def LI(): return list(map(int, input().split()))
def II(): return int(input())
def LS(): return input().split()
def S(): return list(input())
def IIR(n): return [II() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
mod = 1000000007

#A
"""
a,b = LI()
if b % a == 0:
    print(a+b)
else:
    print(b-a)
"""

#B
"""
n,m = LI()
lis = [0 for i in range(m)]
for i in range(n):
    k = LI()
    for j in k[1:]:
        lis[j-1] += 1
ans = 0
for i in lis:
    if i == n:ans += 1
print(ans)
"""

#C
"""
def gcd(a,b):
    if a == 0:
        return b
    return gcd(b%a,a)
n = II()
a = LI()
ans = a[0]
for i in range(1,n):
    ans = gcd(ans,a[i])
print(ans)
"""

#D
n,m = LI()
a = LI()
f = [0,2,5,5,4,5,6,3,7,6]
for i in range(m):
    a[i] = [a[i],f[a[i]]]
a.sort(key = lambda x:x[1])
dp = [[] for i in range(n+10)]
for i in a:
    dp[i[1]] = [i[0]]
for i in range(n+1):
    for j in a:
        if i-j[1] >= 0 and len(dp[i-j[1]]) > 0:
            if len(dp[i]) < len(dp[i-j[1]])+1:
                dp[i] = dp[i-j[1]]+[j[0]]
                dp[i].sort()
                dp[i] = dp[i][::-1]
            else:
                if len(dp[i]) == len(dp[i-j[1]])+1:
                    d = sorted(dp[i-j[1]]+[j[0]])
                    d = d[::-1]
                    k = [dp[i],d]
                    k.sort()
                    if k[1] == d:
                        dp[i] = d
ans = 0
k = 1
l = len(dp[n])
for i in range(l):
    ans += k*dp[n][l-i-1]
    k *= 10
print(ans)

#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Accepted

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

#         0 1 2 3 4 5 6 7 8 9
SEGTBL = [6,2,5,5,4,5,6,3,7,6]

maxnum = [None] * (N + 1 + 10)
maxnum[0] = (0, 0)

if 9 in A and 6 in A:
    A.remove(6)

if 5 in A and 2 in A:
    A.remove(2)
if 5 in A and 3 in A:
    A.remove(3)

if 3 in A and 2 in A:
    A.remove(2)

if 1 in A and 4 in A:
    A.remove(4)
if 1 in A and 6 in A:
    A.remove(6)
if 1 in A and 9 in A:
    A.remove(9)

if 7 in A and 6 in A:
    A.remove(6)
if 7 in A and 9 in A:
    A.remove(9)

# print(A)

i = 0
while i < N:
    n = maxnum[i]
    if not n is None:
        for a in A:
            m = (n[0] + 1, 10 ** n[0] * a + n[1])
            j = i + SEGTBL[a]
            prem = maxnum[j]
            maxnum[j] = m if prem is None else max(prem, m)
    i += 1

print(maxnum[N][1])

Submission status: Accepted

Solution code:
n, m = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
K = (0, 2, 5, 5, 4, 5, 6, 3, 7, 6)

A.sort()
DP = [0] * (n+1)

for i in range(n):
    for a in A:
        if i + 1 - K[a] < 0:
            continue
        DP[i+1] = max(DP[i+1], DP[i + 1 - K[a]] * 10 + a)
    if DP[i+1] == 0:
        DP[i+1] = -1

print(DP[n])

Submission status: Accepted

Solution code:
from fractions import gcd

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

A = set(map(int,input().split()))
D = [None,2,5,5,4,5,6,3,7,6]

B = set(D[i] for i in range(1,10) if i in A)


dp = [-1]*(N+1) # dp[i] = # of digits using i matches
dp[0] = 0

for i in range(N+1):
  for d in B:
    if i-d >= 0 and dp[i-d] >= 0:
      dp[i] = max(dp[i],1 + dp[i-d])


res = []

digits = dp[N]
C = sorted(((i,D[i]) for i in range(1,10) if i in A), reverse=True)

i = N

for remaining in reversed(range(digits)):
  for v,d in C:
    if i-d >= 0 and dp[i-d] == remaining:
      res.append(v)
      i -= d
      break

print(*res,sep='')

Submission status: Accepted

Solution code:

def main():
    # N=int(input())
    N,M = list(map(int,input().split()))
    a = list(map(int,input().split()))
    c = [2,5,5,4,5,6,3,7,6]
    dp = [int(-1e7) for _ in range(N+1)]
    dp[0] = 0
    for i in range(1,N+1):
        for j in a:
            if i-c[j-1]>=0:
                dp[i] = max(dp[i],dp[i-c[j-1]]+1)
    ans = ""
    now = N
    for _ in range(dp[N]):
        ag = -1
        ma = -1
        for j in a:
            if now - c[j-1] < 0:
                continue
            if dp[now]!=dp[now-c[j-1]]+1:
                continue
            if j > ma:
                ma = j
        now -= c[ma-1]
        ans += str(ma)
    print(ans)

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
a = list(map(int, input().split()))
c = [0,2,5,5,4,5,6,3,7,6]
f = [-1]*10010
f[0] = 0
for i in range(1, n+1):
	for x in a:
		if i-c[x] >= 0:
			f[i] = max(f[i], f[i-c[x]]*10+x)
print(f[n])

Submission status: Accepted

Solution code:
matches = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]

n, m = map(int, input().split())
alist = list(map(int, input().split()))
alist.sort(reverse=True)

dp = [-1 for _ in range(n + 1)]
dp[0] = 0
for a in alist:
    match = matches[a]
    for i in range(n - match + 1):
        if dp[i] == -1: continue
        dp[i + match] = max(dp[i + match], dp[i] * 10 + a)

print(dp[-1])

Submission status: Accepted

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

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

T = [(-10**8,0)]*(N+1)
T[0] = (0, 0)
for i in range(1, N+1):
  for a in A:
    if i-C[a]>=0:
      T[i] = max(T[i], (T[i-C[a]][0]+1, a))

ans = ""
p = N
while p>0:
  ans += str(T[p][1])
  p -= C[T[p][1]]
print ans

Submission status: Accepted

Solution code:
N, m = map(int, raw_input().split())
a = map(int, raw_input().split())
C = [-1, 2, 5, 5, 4, 5, 6, 3, 7, 6]

C = [C[A] for A in a]

dp = [-float('inf')] * (N + 1)
dp[0] = 0
for i in range(1, N + 1):
    for j in range(len(C)):
        if C[j] <= i:
            dp[i] = max(dp[i], dp[i - C[j]] * 10 + a[j])

print dp[N]

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
l=list(map(int,input().split()))
l.sort()
dict={1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}
dp=[0]*(N+1)
for j in l:
   nu,val=j,dict[j]
   dp[val]=max(dp[val],int(nu))
for i in range(N):
   if dp[i]!=0:
      for j in l:
         nu,val=j,dict[j]
         if i+val<=N:
            dp[i+val]=max(dp[i+val],int(str(dp[i])+str(nu)))
print(dp[N])

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, m = map(int, input().split())
    A = list(map(int, input().split()))

    L = [(1, 2), (2, 5), (3, 5), (4, 4), (5, 5), (6, 6), (7, 3), (8, 7), (9, 6)]
    B = []
    for num, cost in L:
        if num in A:
            B.append([num, cost])
    B.sort(key=lambda x: -x[0])
    dp = [-f_inf] * (n + 1)
    dp[0] = 0
    for i in range(n + 1):
        for _, cost in B:
            if i - cost == 0:
                dp[i] = max(dp[i], dp[0] + 1)
            elif dp[i - cost] != 0:
                dp[i] = max(dp[i], dp[i - cost] + 1)
    j = 0
    k = n
    res = ""
    while k > 0 and j < n:
        num, cost = B[j]
        if k - cost >= 0 and dp[k] - dp[k - cost] == 1:
            res += str(num)
            k -= cost
        else:
            j += 1
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Runtime Error

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

a.sort(reverse=True)
num_of_matches = [6, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [-1] * (n+1)
dp[0] = 0
for i in range(1, n+1):
    val = -1
    for aa in a:
        if i - num_of_matches[aa] < 0:
            continue
        if i - num_of_matches[aa] == 0:
            val = 1
        elif dp[i - num_of_matches[aa]] > 0:
            val = max(val, dp[i - num_of_matches[aa]] + 1)
    dp[i] = val

res = ''
remain = dp[n]
match = n
while match > 0:
    for i in range(m):
        if remain - 1 == dp[match-num_of_matches[a[i]]] and match - num_of_matches[a[i]] >= 0:
            match -= num_of_matches[a[i]]
            remain -= 1
            res += str(a[i])
            break
print(res)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
num_of_matches = [6, 2, 5, 5, 4, 5, 6, 3, 7, 6]
# a = [(i, num_of_matches[i]) for i in map(int, input().split())]
a = list(map(int, input().split()))

a.sort(reverse=True)
dp = [-1] * (n+1)
dp[0] = 0
for i in range(1, n+1):
    val = -1
    for aa in a:
        if i - num_of_matches[aa] < 0:
            continue
        if i - num_of_matches[aa] == 0:
            val = 1
        elif dp[i - num_of_matches[aa]] > 0:
            val = max(val, dp[i - num_of_matches[aa]] + 1)
    dp[i] = val

res = ''
remain = dp[n]
match = n
while match > 0:
    for i in range(m):
        if remain - 1 == dp[match-num_of_matches[a[i]]]:
            match -= num_of_matches[a[i]]
            remain -= 1
            res += str(a[i])
            break
print(res)

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 = [-10**18]*(N+1)
dp[0] = 0

for i in range(N):
    for Ai in A:
        if i+nums[Ai]<=N:
            dp[i+nums[Ai]] = max(dp[i+nums[Ai]], dp[i]+1)

ans = []
now = N

for i in range(dp[N]):
    for Ai in A:
        if dp[now-nums[Ai]]==dp[N]-i-1:
            now -= nums[Ai]
            ans.append(str(Ai))
            break

print(''.join(ans))

Submission status: Runtime Error

Solution code:
import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


def main():
    N, M = NMI()
    A = NLI()

    match_dict = {i+1: m for i, m in enumerate([2,5,5,4,5,6,3,7,6])}
    usable_list = [[a, match_dict[a]] for a in A]
    usable_list.sort(key=lambda x: (x[1], -x[0]))

    ans = []
    def dfs(now_num, n):
        if n == 0:
            now = list(str(now_num))
            now.sort(reverse=True)
            ans.append(int("".join(now)))

        for num, m in usable_list:
            if n < m:
                break
            dfs(now_num*10+num, n-m)
            if n > 20:
                break

    dfs(0, N)
    print(max(ans))


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))
D = "0255456376"
A_num = [int(D[a]) for a in A]
dp = [0]*(N+1)
for i in range(1, N+1):
  L = [dp[i-a]+1 for a in A_num if i-a>=0]
  if L==[]:
    dp[i]=-10**18
  else:
    dp[i]=max(dp[i-a]+1 for a in A_num if i-a>=0)
S = []
while N>0:
  m = max(a for a in A if dp[N]-1==dp[N-int(D[a])])
  S.append(m)
  N -= int(D[m])
print(*S, sep="")

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
a=list(map(int,input().split()))
table={
  1:2,
  2:5,
  3:5,
  4:4,
  5:5,
  6:6,
  7:3,
  8:7,
  9:6,
}
dp=[-1]*(n+1)
dp[0]=0
for i in range(1,n+1):
  mx=-1
  for j in a:
    #print(i,i-table[j],dp[i-table[j]],j)
    if dp[i-table[j]]<0:
      continue
    if mx < dp[i-table[j]]*10+j:
      mx =dp[i-table[j]]*10+j
  dp[i]=mx
print(dp[n])

Submission status: Runtime Error

Solution code:
import math

n,_,*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}
a=sorted(a)

num=[0]*8

for d in a:
    num[match[d]]=d

dig=set(num)
dig.remove(0)
dig=sorted(list(dig),reverse=True)

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

for i in range(n+1):
    for d in dig:
        if i-match[d]<0:
            continue

        dp[i]=max(dp[i],dp[i-match[d]]+1)

ans=''

i=n
while i>0:
    for d in dig:
        if dp[i]==dp[i-match[d]]+1:
            ans=ans+str(d)
            break
    
    i-=match[d]

print(ans)

Submission status: Runtime Error

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

def nax(a, b):
    if a == '-':
        return b
    if len(a) != len(b):
        return a if len(a)>len(b) else b
    return a if a>b else b


match = [2,5,5,4,5,6,3,7,6]
# dp[i]  : iほんのマッチを使ってできる数値の最大値
dp = ['-'] * 10001
dp[0] = ''

for i in range(N+1):
    if dp[i] == '-':
        continue
    for a in A:
        dp[i+match[a-1]] = nax(dp[i+match[a-1]], dp[i] + chr(ord('0') + a))

print(dp[N])

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
from collections import defaultdict
a=list(map(int,input().split()))
dic={i:[2,5,5,4,5,6,3,7,6][i-1]for i in range(1,10)}
s={}
for i in a:
    if dic[i] in s:
        s[dic[i]]=max(s[dic[i]],i)
    else:
        s[dic[i]]=i
ok=list(s.items())#hon,digit
dp=[0]*(n+1)
for i in range(1,n+1):
    for h,d in ok:
        if h<=i:
            dp[i]=max(dp[i],dp[i-h]+1)
from operator import itemgetter as it 
ok.sort(reverse=1,key=it(1))
ans=''
now=n
keta=dp[n]
while keta>1:
    for h,d in ok:
        if now>h and dp[now]==dp[now-h]+1:
            ans+=str(d);now-=h;keta-=1;break
print(ans+str(s[now]))

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
from collections import defaultdict
a=list(map(int,input().split()))
dic={i:[2,5,5,4,5,6,3,7,6][i-1]for i in range(1,10)}
s={}
for i in a:
    if dic[i] in s:
        s[dic[i]]=max(s[dic[i]],i)
    else:
        s[dic[i]]=i
ok=list(s.items())#hon,digit
dp=defaultdict(int)
for i in range(1,n+1):
    for h,d in ok:
        if h<=i:
            dp[i]=max(dp[i],dp[i-h]+1)
from operator import itemgetter as it 
ok.sort(reverse=1,key=it(1))
ans=''
now=n
keta=dp[n]
while keta>1:
    for h,d in ok:
        if now>h and dp[now]==dp[now-h]+1:
            ans+=str(d);now-=h;keta-=1;break
print(ans+str(s[now]))

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
from collections import defaultdict
a=list(map(int,input().split()))
dic={i:[2,5,5,4,5,6,3,7,6][i-1]for i in range(1,10)}
s={}
for i in a:
    if dic[i] in s:
        s[dic[i]]=max(s[dic[i]],i)
    else:
        s[dic[i]]=i
ok=list(s.items())#hon,digit
dp=defaultdict(int)
for i in range(1,n+1):
    for h,d in ok:
        if h<=i:
            dp[i]=max(dp[i],dp[i-h]+1)
from operator import itemgetter as it 
ok.sort(reverse=1,key=it(1))
ans=''
now=n
keta=dp[n]
while keta>1:
    for h,d in ok:
        if now>=h and dp[now]==dp[now-h]+1:
            ans+=str(d);now-=h;keta-=1;break
print(ans+str(s[now]))

Submission status: Runtime Error

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

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

need =[2,5,5,4,5,6,3,7,6]

if 2 in A and 3 in A:
  del A[A.index(2)]
if 3 in A and 5 in A:
  del A[A.index(3)]
if 6 in A and 9 in A:
  del A[A.index(6)]
if 1 in A and 4 in A:
  del A[A.index(4)]
if 6 in A and 7 in A:
  del A[A.index(6)] 
if 7 in A and 9 in A:
  del A[A.index(9)] 
if 1 in A and 6 in A:
  del A[A.index(6)] 
if 1 in A and 9 in A:
  del A[A.index(9)] 
  
M = len(A)

dp = [[0]*(N+1) for _ in range(M)]
dpmax = [0]*(N+1)

for j in range(2,N+1):
  tmpmax = 0
  for i in range(M):
    tmp = need[A[i]-1]
    if j == tmp:
      res = A[i]
    elif j > tmp:
      if dpmax[j-tmp] != 0:
        tmp2 = dpmax[j-tmp]
        res = max(A[i]*(10**len(str(tmp2)) + tmp2,tmp2*10+A[i]))
    if tmpmax < res:
      tmpmax = res
    dp[i][j] = res
  dpmax[j] = tmpmax
  
print(dpmax[-1])

Submission status: Runtime Error

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
from math import sqrt, pi
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

num = [2, 5, 5, 4, 5, 6, 3, 7, 6]

N, M = getNM()
A = getList()

digit = []
for i in A:
    digit.append([i, num[i - 1]])
digit.sort(key = lambda i: i[1])

dp = [-float('inf')] * (N + 1)
dp[0] = 0

# 桁数を調べる
for i in range(1, N + 1):
    for j in range(M):
        if i >= digit[j][1]:
            dp[i] = max(dp[i], dp[i - digit[j][1]] + 1)

# 数字を組み上げる
ans = ''
now = N
digit.sort(reverse = True)
while now > 0:
    for j in range(M):
        if dp[now] == dp[now - digit[j][1]] + 1:
            now -= digit[j][1]
            ans += str(digit[j][0])
            break
print(ans)

Submission status: Runtime Error

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
from math import sqrt, pi
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

num = [2, 5, 5, 4, 5, 6, 3, 7, 6]

N, M = getNM()
A = getList()

digit = []
for i in A:
    digit.append([i, num[i - 1]])
digit.sort(key = lambda i: i[1])

dp = [-float('inf')] * (N + 1)
dp[0] = 0

# 桁数を調べる
for i in range(1, N + 1):
    for j in range(M):
        if i >= digit[j][1]:
            dp[i] = max(dp[i], dp[i - digit[j][1]] + 1)

# 数字を組み上げる
ans = ''
now = N
digit.sort(reverse = True)
for i in range(dp[N]):
    for j in range(M):
        if dp[now] == dp[now - digit[j][1]] + 1:
            now -= digit[j][1]
            ans += str(digit[j][0])
            break
print(ans)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
aas = list(map(int, input().split()))
needs = {1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}
dp = {}
def rc(rn):
    if rn in dp:
        return dp[rn]
    if rn == 0:
        return ""
    ret = 0
    for i in aas:
        if needs[i] <= rn:
            try:
                ret = max(ret, int(str(i)+str(rc(rn-needs[i]))))
            except:
                pass
    if ret == 0:
        return "err"
    dp[rn] = ret
    return ret
print(rc(n))