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:
n,m = map(int,input().split())
a = list(map(int,input().split()))
a.sort(reverse = True)
l = [0,2,5,5,4,5,6,3,7,6]

dp = [-1**10]*(n+1)
dp[0] = 0
for i in range(1,n+1):
    
    for j in range(m):
        if i >= l[a[j]] and dp[i] < dp[i-l[a[j]]]+1:
            dp[i] = dp[i-l[a[j]]]+1
            

ans = []
remain = dp[-1]
now = n
for i in a:
    x = l[i]
    while now -x >= 0 and dp[now] == dp[now-x]+1:
        ans.append(i)
        now -= x 
print(*ans,sep="")

Submission status: Accepted

Solution code:
# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# あえてAからループで回す場合、本当はマッチ棒の本数で先にループを回すのが良い
N, M = lr()
A = lr()
A.sort(reverse=True)
dp = [-1] * (N+1)
dp[0] = 0
match = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
for a in A:
    for x in range(1, N+1):
        y = match[a]
        if x - y < 0 or dp[x-y] == -1:
            continue
        dp[x] = max(dp[x], dp[x-y] * 10 + a)

answer = dp[N]
print(answer)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, M = lr()
A = lr()
dp = [-1] * (N+1)
dp[0] = 0
match = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
for x in range(N):
    for a in A:
        y = match[a]
        if x + y > N:
            continue
        dp[x+y] = max(dp[x+y], dp[x] * 10 + a)

answer = dp[N]
print(answer)
# 32

Submission status: Accepted

Solution code:
# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, M = lr()
A = lr()
dp = [-1] * (N+1)
dp[0] = 0
for x in range(N):
    for a in A:
        y = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6][a]
        if x + y > N:
            continue
        dp[x+y] = max(dp[x+y], dp[x] * 10 + a)

answer = dp[N]
print(answer)
# 32

Submission status: Accepted

Solution code:
nim,mike = map(int,input().split())
array = list(map(int,input().split()))

dp = [-1 for i in range(nim+10)]
l = [0,2,5,5,4,5,6,3,7,6]
dp[0] = 0
for i in range(nim-1):
    for s in array:
        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[nim])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

def main():
    n, m = map(int, input().split())
    a = list(map(int, input().split()))

    # dig: マッチ本数 -> 使える数字
    nm = [999, 2, 5, 5, 4, 5, 6, 3, 7, 6]
    dig = [None for i in range(8)]
    for x in sorted(a):
        dig[nm[x]] = x

    # dp[j]: j本のマッチを使って作れる最大の数 tuple(桁数d, prevj, lastdig)
    dp = [None for j in range(n + 1)]
    dp[0] = (0, None, None)
    for j in range(1, n + 1):  # もらう
        for use in [2, 3, 4, 5, 6, 7]:
            jp = j - use
            if jp < 0:
                continue
            if dig[use] is None:
                continue
            if dp[jp] is None:
                continue
            d = dp[jp][0] + 1
            tup = (d, jp, dig[use])
            if (dp[j] is None) or (dp[j][0] < d) or (dp[j][0] == d and dp[j][2] < dig[use]):
                dp[j] = tup

    res = []
    j = n
    while True:
        d, jp, i = dp[j]
        if jp is None:
            break
        res.append(str(i))
        j = jp
    assert len(res) == dp[n][0]

    print("".join(res))

if __name__ == "__main__":
    main()

Submission status: Accepted

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

a = [int(i) for i in input().split()]

l = [0,2,5,5,4,5,6,3,7,6]
inf = float("INF")
dp = [-inf] * (n+10)
d = [-inf] * (n+10)
dp[0] = 0
d[0] = 0
for i in range(n):
  if dp[i] == -inf: continue
  tmp = dp[i]
  k = d[i]
  for ai in a:
    dp[l[ai] + i] = max(dp[l[ai] + i], dp[i] + k * ai, dp[i] * 10 + ai)
    d[i + l[ai]] = max(d[i + l[ai]], k + 1)
print(dp[n])

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
    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=[-n-n]*(n+1)
    dp[0]=0
    ans=[]
    for i in range(1,n+1):
        for j in a:
            if i>=cost[j]:
                dp[i]=max(dp[i],dp[i-cost[j]]+1)
    cnt=n
    while cnt:
        for j in a:
            if cnt>=cost[j] and dp[cnt-cost[j]]==dp[cnt]-1:
                ans.append(j)
                cnt-=cost[j]
                break
    for j in ans:
        print(j, end="")
    print("")

if __name__ == '__main__':
    main()

Submission status: Accepted

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

A.sort()
A.reverse()

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

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

for i in range(1, N + 1):
  for j in A:
    if i >= match[j]:
      dp[i] = max(dp[i], dp[i - match[j]] + 1)

max_list = []
while N:
  for j in A:
    if N >= match[j] and dp[N] == dp[N - match[j]] + 1:
      max_list.append(j)
      N -= match[j]
      break

for j in max_list:
  print(j, end="")
print("")

Submission status: Accepted

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

A.sort()
A.reverse()

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

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

for i in range(1, N + 1):
  for j in A:
    if i >= match[j]:
      dp[i] = max(dp[i], dp[i - match[j]] + 1)

max_list = []
while N:
  for j in A:
    if N >= match[j] and dp[N] == dp[N - match[j]] + 1:
      max_list.append(j)
      N -= match[j]
      break

for j in max_list:
  print(j, end="")
print("")

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
A=list(map(int,input().split()))
A.sort(reverse=True)
numk={1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}
dp=[0]+[-1]*(N+1)
for i in range(N):
    for j in A:
        if i+numk[j]<=N:
            dp[i+numk[j]]=max(dp[i+numk[j]],dp[i]+1)
m=N
ans=[]
while m>0:
    for i in A:
        if m-numk[i]>=0 and dp[m-numk[i]]+1==dp[m]:
            ans.append(str(i))
            m-=numk[i]
            break
print(''.join(ans))

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
l=list(map(int,input().split()))
l.sort()
x=[0,2,5,5,4,5,6,3,7,6]
d=dict()
for j in l:
    d[x[j]]=j
INF=float('inf')
dp=[-INF for i in range(n+1)]
dp[0]=0
l=d.keys()
for i in range(2,n+1):
    for j in d.keys():
        if j<=i:
            dp[i]=max(dp[i],dp[i-j]*10+d[j])
print(dp[n])

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
A=list(map(int,input().split()))
A.sort(reverse=True)
numk={1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}
dp=[0]+[-1]*(N+1)
for i in range(N):
    for j in A:
        if i+numk[j]<=N:
            dp[i+numk[j]]=max(dp[i+numk[j]],dp[i]+1)
m=N
ans=[]
while m>0:
    for i in A:
        if m-numk[i]>=0 and dp[m-numk[i]]==dp[m]-1:
          ans.append(str(i))
          m-=numk[i]
          break
print(''.join(ans))

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
A=list(map(int,input().split()))
A.sort(reverse=True)
numk={1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}
dp=[0]+[-1]*(N+1)
for i in range(N):
    for j in A:
        if i+numk[j]<=N:
            dp[i+numk[j]]=max(dp[i+numk[j]],dp[i]+1)
m=N
ans=[]
while m>0:
    for i in A:
        if m-numk[i]>=0 and dp[m-numk[i]]==dp[m]-1:
          m-=numk[i]
          ans.append(str(i))
          break
print("".join(ans))

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
num={1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}
A=list(map(int,input().split()))
A.sort(reverse = True)
dp = [0]+[-1]*(N+1)
for i in range(N):
    for j in A:
        if i+num[j]<=N:
            dp[i+num[j]] = max(dp[i+num[j]],dp[i]+1)
ans = []
m=N
while m>0:
    for i in A:
        if m-num[i]>=0 and dp[m-num[i]]==dp[m]-1:
          m-=num[i]
          ans.append(str(i))
          break
print("".join(ans))

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()

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

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

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

dp = ["0"] * 10010

dp[0] = ""

def greater(x, y):
    if len(x) == len(y):
        return max(x, y)
    else:
        return x if len(x) > len(y) else y

for i in range(N):
    if dp[i] != "0":
        for num in A:
            dp[i+match_dict[num]] = greater(dp[i+match_dict[num]], dp[i]+str(num))

print(dp[N])

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
A=reversed(sorted(map(int,input().split())))
M=[2,5,5,4,5,6,3,7,6]
D={}
E={}
for a in A:
    if M[a-1] in D:
        continue
    else:
        D[M[a-1]]=a
        E[a]=M[a-1]
S=list(reversed(sorted(E)))
        
dp=[0]*(n+2)
for i in range(1,n+2):
    cnt=-1
    for d in D:
        if i-d>=0:
            if dp[i-d]!=-1:
                cnt=max(dp[i-d]+1,cnt)
    dp[i]=cnt    
k=dp[n]
ans=""

while k>0:
    for s in S:
        x=E[s]
        if n-x<0:
            continue
        if dp[n-x]==k-1:
            ans+=str(s)
            k-=1
            n-=x
            break
print(ans)

Submission status: Accepted

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

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

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

for i in range(n):
  for j in A:
    if i + li[j - 1] <= n:
      dp[i + li[j - 1]] = max(dp[i + li[j - 1]], dp[i] * 10 + j)
print(dp[-1])

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()

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

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

def greater(a, b):
    if len(a) == len(b):
        return max(a, b)
    elif len(a) > len(b):
        return a
    else:
        return b        

dp = ["0"] * 11000

dp[0] = "" 

for i in range(N+1):
    
    for a in A:
        if i - match_dict[a] >= 0 and dp[i-match_dict[a]] != '0':
            dp[i] = greater(dp[i - match_dict[a]] + str(a), dp[i])

print(dp[N])

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()

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

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

#桁数のMAX
dp = [-1] * (N+1)
dp[0] = 0

for a in A:
    for i in range(match_dict[a], N+1):
        if dp[i - match_dict[a]] >= 0:
            dp[i] = max(dp[i], dp[i - match_dict[a]] + 1)

ans = ''
A.sort(reverse=True)

i = N
while i:
    for a in A:
        if i - match_dict[a] >= 0 and dp[i - match_dict[a]] == dp[i] - 1:
            ans += str(a)
            i -= match_dict[a]
            break

print(ans)

Submission status: Accepted

Solution code:
def main():
    N, M = map(int, input().split())
    lst = list(map(int, input().split()))
    mapk = {1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6}
    
    dp = [0 for _ in range(N+1)] # ちょうどi本使ったときの最大桁数
    for i in range(1, N+1):
        tmp = []
        for k in lst:
            if (i-mapk[k])>=0:
                tmp.append(dp[i-mapk[k]] + 1)
            else:
                tmp.append(-float('inf'))
        dp[i] = max(tmp)
    #print(dp)
    
    ans = ''
    X = N
    lst = sorted(lst, reverse=True)
    for _ in range(dp[N]):
        for k in lst:
            if (X-mapk[k]>=0) and (dp[X - mapk[k]] == dp[X] - 1):
                ans += str(k)
                X -= mapk[k]
                break
    print(ans)
main()

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,m = inpl()
a = sorted(inpl(), reverse = True)
b = [0,2,5,5,4,5,6,3,7,6]
dp = [0] * (n+1)

for i in a:
    w,v = b[i],i
    for j in range(n+1):
        if j < w:
            continue
        if j%w == 0 or dp[j-w]:
            dp[j] = max(dp[j], dp[j-w]*10 + v)
    # print(dp)
print(dp[-1])

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    n,m = map(int, input().split())
    a = list(map(int, input().split()))
    #使う本数の種類
    b = set()
    matti = [2,5,5,4,5,6,3,7,6]
    for i in a:
        b.add(matti[i-1])

    dp = [-1]*(n+1)
    dp[0] = 0
    for i in range(n+1):
        for j in b:
            if i >= j:
                dp[i] = max(dp[i-j]+1, dp[i])

    keta = dp[-1]
    res = []
    a.sort(reverse=True)
    cnt = n
    while cnt>0:
        for i in a:
            if cnt >= matti[i-1]:
                if dp[cnt]-dp[cnt-matti[i-1]]==1:
                    res.append(str(i))
                    cnt -= matti[i-1]
                    break
    print(''.join(res))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 4)
from fractions import gcd

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

def main():
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    dp = [[""]*(n+1) for _ in range(len(a))]
    dp[0][num[a[0]]] = str(a[0])
    for i in range(num[a[0]], n+1):
        if len(dp[0][i-num[a[0]]]) > 0:
            dp[0][i] = dp[0][i-num[a[0]]] + str(a[0])
    for i in range(1, len(a)):
        for j in range(n+1):
            if j < num[a[i]]:
                dp[i][j] = dp[i-1][j]
            else:
                if j == num[a[i]] or dp[i][j-num[a[i]]] != "":
                    buf = dp[i][j-num[a[i]]] + str(a[i])
                    if len(buf) < len(dp[i-1][j]):
                        dp[i][j] = dp[i-1][j]
                    else:
                        dp[i][j] = buf
                else:
                    dp[i][j] = dp[i-1][j]
    ans = list(dp[len(a)-1][n])
    ans.sort(reverse=True)
    print("".join(ans))

if __name__ == "__main__":
    main()

Submission status: Accepted

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

INF = "-"

def chmax(a:str,b:str):
    if a == INF: return b
    elif len(a) < len(b): return b
    elif len(a) == len(a):
        if a < b: return b
    return a

# 数字 : 必要なマッチの本数
cnt = dict(zip(range(1,10), [2,5,5,4,5,6,3,7,6]))

# dp[i]: マッチをi本使って作れる数値の最大値
dp = [INF] * (10 ** 5)

# 初期条件
dp[0] = ""

# 配るDP
for i in range(N):
    if dp[i] == INF: continue
    for a in A:
        dp[i + cnt[a]] = chmax(dp[i + cnt[a]], dp[i] + chr(ord("0") + a))

print(dp[N])

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
sz=[0,2,5,5,4,5,6,3,7,6]
l=[]
dp=[0]*(n+1)
l=list(map(int,input().split()))
l.sort(reverse=True)
dp[0]=1
for i in range(1,n+1):
    for j in l:
        if i-sz[j]>=0 and dp[i-sz[j]]>0:
            dp[i]=max(dp[i],1+dp[i-sz[j]])
#print(dp)
ans=[]
#using the dp table construct the number 
cur=n
while cur>0:#cur denotes count of available match sticks
 #   print(cur)
    for j in l:
        if cur-sz[j]>=0:
            if dp[cur]==1+dp[cur-sz[j]] and dp[cur-sz[j]]>0:
                ans.append(j)
                cur-=sz[j]
                break
ans.sort(reverse=True)
print(''.join(map(str,ans)))

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
num = {1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}
a = list(map(int,input().split()))
a.sort(reverse = True)
dp = [0]+[-1]*(n+1)
for i in range(n):
    for j in a:
        if i+num[j] <=n:
            dp[i+num[j]] = max(dp[i+num[j]],dp[i]+1)
ans = []
match = n
while match > 0:
    for i in a:
        if match-num[i] >= 0 and dp[match-num[i]] == dp[match]-1:
            match -= num[i]
            ans.append(str(i))
            break
print("".join(ans))

Submission status: Accepted

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

dp = [(-1, -1)]*(n+1)
dp[0] = (0, -1)
for k in range(1, n+1):
    max_value = -1
    max_d = -1
    for num in A:
        if k >= digit[num]:
            suf, d = dp[k - digit[num]]
            if suf >= 0:
                value = num * (10 ** (d + 1)) + suf
                if value > max_value:
                    max_value = value
                    max_d = d + 1

    dp[k] = (max_value, max_d)
print(dp[n][0])

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
    N, M = map(int, input().split())
    A = set(map(int, input().split()))


    cost = [-1, 2, 5, 5, 4, 5, 6, 3, 7, 6]
    B = []
    for i in range(1, 10):
        if i in A:
            B.append((cost[i], i))

    B = B[::-1]
    dp = [[-1, -1] for i in range(N+1)]
    dp[0][0] = 0
    for i in range(1, N+1):
        for x, y in B:
            if i >= x and dp[i-x][0] >= 0:
                if dp[i][0] < dp[i-x][0] + 1:
                    dp[i][0] = dp[i-x][0] + 1
                    dp[i][1] = y
    id = N
    ans = []
    # print(dp)
    while(id > 0):
        ans.append(dp[id][1])
        id -= cost[dp[id][1]]
    ans.sort(reverse=True)
    print("".join(map(str, ans)))
main()

Submission status: Accepted

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

match = [10**18, 2, 5, 5, 4, 5, 6, 3, 7, 6]

# 作れる数字の個数
dp = [-10**18] * (N + 1)
dp[0] = 1

for i in range(N):
    for a in A:
        m = match[a]
        if i + m <= N and dp[i + m] < dp[i] + 1:
            dp[i + m] = dp[i] + 1

ans = []
while N > 0:
    for a in A:
        m = match[a]
        if N - m >= 0 and dp[N - m] + 1 == dp[N]:
            ans.append(a)
            N -= m
            break

ans.sort(reverse=True)

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

Submission status: Accepted

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

N, M = map(int, input().split())
A = list(map(int, input().split()))
cnt = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [0] * (N+1) # the max number using i matches
for i in range(N):
    if i > 0 and dp[i] == 0:
        continue
    for a in A:
        if i + cnt[a] > N:
            continue
        dp[i+cnt[a]] = max(dp[i+cnt[a]], dp[i]*10 + a)
print(dp[N])

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() 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)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    W,n = LI()
    a = LI()
    for i in range(n):
        a[i] -= 1
    a.sort(reverse = True)
    b = [2,5,5,4,5,6,3,7,6]
    dp = [-float("inf")]*(W+1)
    dp[0] = 0
    for i in range(n):
        v = a[i]+1
        w = b[a[i]]
        for j in range(W):
            nj = j+w
            if nj > W:
                continue
            nd = dp[j]*10+v
            if dp[nj] < nd:
                dp[nj] = nd
    print(dp[W])
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))
count = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [[0] * 10 for _ in range(N+1)]
for i in range(N+1):
    if i > 0 and all(dp[i][j] == 0 for j in range(10)):
        continue
    for a in A:
        if i + count[a] <= N:
            ndp = list(dp[i])
            ndp[a] += 1
            ca = sum(ndp)
            cb = sum(dp[i+count[a]])
            if ca > cb:
                dp[i+count[a]] = ndp
            if ca == cb:
                for j in range(10)[::-1]:
                    if dp[i+count[a]][j] > ndp[j]:
                        break
                    if dp[i+count[a]][j] < ndp[j]:
                        dp[i+count[a]] = ndp
                        break
ans = ''
for i in range(10)[::-1]:
    ans += str(i) * dp[N][i]
print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
A = list(map(int,input().split()))
L = [2,5,5,4,5,6,3,7,6]
dp = [-float('inf')]*(n+1)
dp[0] = 0
for i in range(1,n+1):
    for j in range(m):
        if i-L[A[j]-1] < 0:
            None
        else:
            dp[i] = max(dp[i-L[A[j]-1]]+1, dp[i])
A.sort()
A.reverse()
cur = n
ans = ''
while cur != 0:
    for i in range(m):
        temp = A[i]
        if cur-L[temp-1] >= 0:
            if dp[cur-L[temp-1]] == dp[cur]-1:
                ans = ans+str(temp)
                cur -= L[temp-1]
                break
print(ans)

Submission status: Accepted

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


COST = {
    1: 2,
    2: 5,
    3: 5,
    4: 4,
    5: 5,
    6: 6,
    7: 3,
    8: 7,
    9: 6,
}
A = sorted(A, reverse=True)

best = [None for _ in range(N + 1)]
best[0] = tuple([0] * len(A))
for n in range(N + 1):
    for ai, a in enumerate(A):
        before = n - COST[a]
        if before < 0 or best[before] is None:
            continue
        val = tuple(x + (1 if i == ai else 0) for i, x in enumerate(best[before]))
        if (
            best[n] is None
            or sum(best[n]) < sum(val)
            or (sum(best[n]) == sum(val) and best[n] < val)
        ):
            best[n] = val
print(''.join(sorted(''.join(str(d) * n for d, n in zip(A, best[N])), reverse=True)))

Submission status: Accepted

Solution code:
n, m = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]

dp = [(0, 0)] * (n+1)
ma = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]

for i in range(n):
    if i!=0 and dp[i] == (0, 0):
        continue
    for j in a:
        t = dp[i]
        k = i + ma[j]
        if k <= n:
            dp[k] = max(dp[k], (t[0] + j * 10 ** t[1], t[1] + 1))
            dp[k] = max(dp[k], (t[0]*10 + j, t[1] + 1))

print(dp[-1][0])

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]
li=[-100]*(N+1)
li[0]=0
for i in range(N+1):
  for a in A:
    if weight[a]+i<=N:
      li[weight[a]+i]=max(li[weight[a]+i],a+10*li[i])
print(li[N])

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
A=[2,5,5,4,5,6,3,7,6]
B=list(map(int,input().split()))
B=sorted(B,reverse=True)
C=[]
for i in range(m):
  C.append(A[B[i]-1])
C=set(C)
C=sorted(list(C))
dp=[-10**10]*(n+10)
dp[0]=0
for i in range(1,n+1):
  for j in range(len(C)):
    if dp[i]<dp[i-C[j]]+1:
      dp[i]=dp[i-C[j]]+1
S=[]
for i in range(dp[n]):
  for j in range(len(B)):
    if dp[n-A[B[j]-1]]==dp[n]-1:
      n=n-A[B[j]-1]
      S.append(B[j])
      break
for i in range(len(S)):
  print(S[i],end="")
print()

Submission status: Accepted

Solution code:
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)


n,m = inm()
a = inl()
a.sort()
cs = [0,2,5,5,4,5,6,3,7,6]
dp = [-1]*(n+9)
dp[0] = 0
for i in range(n):
    if dp[i]>=0:
        for x in a:
            c = cs[x]
            dp[i+c] = max(dp[i+c], dp[i]+1)
ans = []
t = n
k = dp[n]
for j in range(k,0,-1):
    for i in range(m-1,-1,-1):
        x = a[i]
        c = cs[x]
        if t>=c and dp[t-c]==j-1:
            ans.append(str(x))
            t -= c
            break
print(''.join(ans))

Submission status: Accepted

Solution code:
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

DEPMAX = 5

def foo(n,dep):
    if dep>DEPMAX or n<0:
        ret = "-1"
    elif n==0:
        ret = ""
    elif n%mn==0:
        ret = str(mni)*(n//mn)
    else:
        mxs = "-1"
        for x in a:
            v = foo(n-cs[x],dep+1)
            if v=="-1":
                continue
            vv = v+str(x)
            if int(vv)>int(mxs):
                mxs = vv
            vv = str(x)+v
            if int(vv)>int(mxs):
                mxs = vv
        ret = mxs
    #ddprint(f"foo n {n} k {k} ret {ret}")
    return ret

n,m = inm()
a = inl()
a.sort()
cs = [0,2,5,5,4,5,6,3,7,6]
mn = min([cs[x] for x in a])
for i in range(m-1,-1,-1):
    if cs[a[i]]==mn:
        mni = a[i]
        break
#k = (n+mn-1)//mn
#k = (n)//mn
#ddprint(f"mn {mn} mni {mni}")
#ddprint(a)
print(foo(n,0))

Submission status: Accepted

Solution code:
#import decimal
#decimal.getcontext().prec==500 Floatの桁数を500まで増やす
#Decimal(c).sqrt() それで平方根を求める
#Decimal(1) / Decimal(7) 1/7

from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
import math
from fractions import gcd
import sys
#input = sys.stdin.readline

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

data=[]
for i,a in enumerate([2,5,5,4,5,6,3,7,6]):
    if i+1 in A:
        data.append([a,i+1])

dic={}
for a,i in reversed(data):
    dic[i]=0
dp=[copy.copy(dic) for i in range(N+1)]

def main(dic1,dic2):
    dic1=sorted([[str(i),dic1[i]] for i in dic],key=lambda x:x[0],reverse=True)
    dic2=sorted([[str(i),dic2[i]] for i in dic],key=lambda x:x[0],reverse=True)
    for a,b in zip(dic1,dic2):
        if a[1]>b[1]:
            return(0)
        if a[1]<b[1]:
            return(1)
    return(0)

def _sum(dic):
    count=0
    for i in dic:
        count+=dic[i]
    return(count)


for a,n in data:
    tempdic=copy.copy(dic)
    tempdic[n]+=1
    if len(dp)-1>=a:
        flag=main(dp[a],tempdic)
        if flag:
            dp[a]=tempdic
    for i in range(len(dp)):
        if i>=a and _sum(dp[i-a]):
            if _sum(dp[i])<_sum(dp[i-a])+1:

                tempdic=copy.copy(dp[i-a])
                tempdic[n]+=1
                dp[i]=tempdic
            elif _sum(dp[i])==_sum(dp[i-a])+1:
                dp[i-a][n]+=1
                flag=main(dp[i],dp[i-a])
                dp[i-a][n]-=1
                if flag:
                    tempdic=copy.copy(dp[i-a])
                    tempdic[n]+=1
                    dp[i]=tempdic
dic=dp[N]
a=""
dic=sorted([[str(i),dic[i]] for i in dic],key=lambda x:x[0],reverse=True)
for i,z in dic:
    for m in range(z):
        a+=i
print(a)

Submission status: Accepted

Solution code:
from collections import defaultdict
n,m=map(int,input().split())
A=list(map(int,input().split()))
hon2=[1]
hon5=[2,3,5]
hon4=[4]
hon3=[7]
hon6=[6,9]
hon7=[8]
usenum=[]
usematch=defaultdict(int)
for a in A:
    if a in hon2:
        usenum.append(2)
        usematch[2]=max(a, usematch[2])
    if a in hon5:
        usenum.append(5)
        usematch[5]=max(a, usematch[5])
    if a in hon4:
        usenum.append(4)
        usematch[4]=max(a, usematch[4])
    if a in hon3:
        usenum.append(3)
        usematch[3]=max(a, usematch[3])
    if a in hon6:
        usenum.append(6)
        usematch[6]=max(a, usematch[6])
    if a in hon7:
        usenum.append(7)
        usematch[7]=max(a, usematch[7])
usenum=list(set(usenum))
usenum.sort()
dp=[-1]*(n+11)
dp[0]=0
for i in range(n+1):
    if dp[i]==-1:
        continue
    for num in usenum:
        dp[i+num]=max(10*dp[i]+usematch[num], dp[i+num])
print(dp[n])

Submission status: Accepted

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

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

N=[0,2,5,5,4,5,6,3,7,6]
X=[]
dp=[0]+[-1]*n*9

for i in range(n):
    for j in A:
        if dp[i]>=0:
            dp[i+N[j]]=max(dp[i+N[j]],dp[i]*10+j)

print(dp[n])