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()))
da=[9,8,7,6,5,4,3,2,1]
db=[6,7,3,6,5,4,5,5,2]
ka=set(())
d={}
for i in range(9):
  if  da[i] in a and db[i] not in ka:
    d[da[i]]=db[i]
    ka.add(db[i])
dr={v:k for k,v in d.items()}
a=[d.keys()]
a.sort(reverse=True)

dp=[0]*(n+1)
dp[0]=''
import sys
sys.setrecursionlimit(10**7)
def maxret(d1,d2):
  if len(d1)>len(d2):return d1
  if len(d1)<len(d2):return d2
  if d1>d2:return d1
  if d1<d2:return d2
def func(k):
  if k==0:return ''
  if dp[k]!=0:return dp[k]
  ret=''
  for x in d:
    if k-d[x]<0:continue
    tmp=func(k-d[x])
    tmp+=str(x)
    if tmp[0]=='-':continue
    t=maxret(ret,tmp)
    ret=t
  if ret=='':
    dp[k]='-'
  else:
    dp[k]=ret
  return dp[k]
ddd=func(n)
print(ddd)

Submission status: Accepted

Solution code:
import sys
N,M = map(int,sys.stdin.readline().rstrip().split())
A = list(map(int,sys.stdin.readline().rstrip().split()))

from collections import defaultdict

d = defaultdict(int)  # d[i] = (Aの中でi本用いて表せる最大の数)
for i in range(M):
    if A[i] == 1:
        d[2] = 1
    elif A[i] == 7:
        d[3] = 7
    elif A[i] == 4:
        d[4] = 4
    elif A[i] in [2,3,5]:
        d[5] = max(d[5],A[i])
    elif A[i] in [6,9]:
        d[6] = max(d[6],A[i])
    else:
        d[7] = 8

B = list(d.keys())
B.sort()

a = B[0]
B[0] = 0

if N % a == 0:
    print(''.join([str(d[a])]*(N//a)))
    exit()

from itertools import combinations_with_replacement

C = []

for i in range(N//a,max(-1,N//a-7),-1):  # aをi回用いる
    x = N-a*i
    for u in list(combinations_with_replacement(B,5)):
        if sum(u) == x:
            s = []
            for j in range(5):
                if u[j] != 0:
                    s.append(u[j])
            C.append((i,s))

D = []
for i,j in C:
    if i + len(j) == C[0][0] + len(C[0][1]):
        D.append((i,j))

m = min(D[i][0] for i in range(len(D)))

q,r,s = 0,0,0
for i,j in D:
    X = [d[a]]*(i-m) + [d[k] for k in j]
    X.sort(reverse=True)
    M = ''
    for k in X:
        M += str(k)
    M = int(M)
    if q < M:
        q,r,s = M,i,j

E = [d[a]]*r + [d[i] for i in s]
E.sort(reverse=True)

ans = ''
for i in E:
    ans += str(i)
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
D = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
A = list(map(int, input().split()))
C = [(a, D[a]) for a in A]
C.sort(reverse=True)
dp = [-1]*(n+1)
dp[0] = 0
for i in range(1, n+1):
  for a, c in C:
    if i >= c and dp[i-c] >= 0:
      dp[i] = max(dp[i-c]+1, dp[i])
now = n
ans = ""
while now:
  for a, c in C:
    if now-c >= 0 and dp[now] == dp[now-c]+1:
      ans += str(a)
      now -= c
      break
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)
req = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]

t = [-1]*(N+1)
t[0] = 0
for a in A:
    q = req[a]
    for i in range(q, N+1):
        t[i] = max(t[i], t[i-q] * 10 + a)
print(t[-1])

Submission status: Accepted

Solution code:
import heapq
N, M = map(int, input().split())
A = list(map(int, input().split()))
B = [6,2,5,5,4,5,6,3,7,6] # B[i]がiを作るのに必要なマッチ棒の数

# dp[i]: i本マッチ使って作れるMAX桁数。。
dp = [-1 for _ in range(N+10)]
dp[0] = 0
A.sort()
visited = [False for _ in range(N+10)]
h = []
heapq.heappush(h, (0,0))

while h:
  now_n, keta = heapq.heappop(h)
  if visited[now_n]:
    continue
  visited[now_n] = True
  for a in A:
    nxt_n = now_n + B[a]
    if nxt_n >= N + 10:
      continue
    dp[nxt_n] = max(dp[nxt_n], dp[now_n] + 1)
    heapq.heappush(h, (nxt_n, dp[now_n] + 1))
    
#print(dp)

A.sort(reverse=True)
# 上の桁から決めていく。dp[N]
ANS = []
zan = N
for i in range(dp[N],0,-1):
  bugf = True
  # sorted(a) 大きい方から試す
  for a in A:
    if dp[zan-B[a]] == dp[zan] - 1:
      ANS.append(str(a))
      zan = zan - B[a]
      bugf = False
      break
  if bugf:
    # Aが構成できない、と言うことなのでここは通らないはず
    print("bug...")
  
print("".join(ANS))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)
INF = float('inf')
dp = [-INF]*(N + 5)
needs = [2, 5, 5, 4, 5, 6, 3, 7, 6]
can_use = {k: needs[k-1] for k in A}
dp[0] = 0
for i in range(2, N+1):
    for v in can_use.values():
        if i - v < 0:
            continue
        dp[i] = max(dp[i], dp[i-v]+1)
ans = ''
i = N
while i != 0:
    for k, v in can_use.items():
        if i - v < 0:
            continue
        while dp[i] == dp[i-v] + 1:
            ans += str(k)
            i -= v
print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
A=list(map(int,input().split()))
d={2:0,3:0,4:0,5:0,6:0,7:0}
for i in A:
    if i==1:
        d[2]=1
    elif i==7:
        d[3]=7
    elif i==8:
        d[7]=8
    elif i==4:
        d[4]=4
    elif i==6 or i==9:
        if d[6]<i:
            d[6]=i
    else:
        if d[5]<i:
            d[5]=i
l=[]
for i in d.keys():
    if d[i]:
        l.append(i)
l.sort()
a=[]
m=0
if len(l)>=4:
    for i in range(4):
        for j in range(4):
            for k in range(4):
                t=N-i*l[1]-j*l[2]-k*l[3]
                if t%l[0] or t<0:
                    continue
                ke=i+j+k+t//l[0]
                if ke<m:
                    continue
                else:
                    s=[d[l[1]]]*i+[d[l[2]]]*j+[d[l[3]]]*k+[d[l[0]]]*(t//l[0])
                    s.sort(reverse=1)
                    if ke==m:
                        a.append(s)
                    else:
                        a=[s]
                        m=ke
    print(*max(a),sep="")
elif len(l)==3:
    for i in range(5):
        for j in range(5):
            t=(N-i*l[1]-j*l[2])
            if t%l[0] or t<0:
                continue
            ke=i+j+t//l[0]
            if ke<m:
                continue
            else:
                s=[d[l[1]]]*i+[d[l[2]]]*j+[d[l[0]]]*(t//l[0])
                s.sort(reverse=1)
                if ke==m:
                    a.append(s)
                else:
                    a=[s]
                    m=ke
    print(*max(a),sep="")
elif len(l)==2:
    for i in range(6):
        if (N-l[1]*i)%l[0]==0:
            a=[d[l[1]]]*i+[d[l[0]]]*((N-i*l[1])//l[0])
            a.sort(reverse=1)
            print(*a,sep="")
            break
else:
    a=[d[l[0]]]*(N//l[0])
    print(*a,sep="")

Submission status: Accepted

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

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


all_weights = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
weights = [all_weights[i] for i in a]

# print(weights)

dp = [-1 for _ in range(n+1)]
dp[0] = 0

for i in range(1, n+1):
    # print(dp)
    for j in range(len(weights)):
        if i-weights[j] >= 0:
            dp[i] = max(dp[i-weights[j]]*10 + a[j], dp[i])

print(dp[-1])

Submission status: Accepted

Solution code:
def main():  
  N,M=map(int,input().split())
  A=list(map(int,input().split()))
  dp=[2,5,5,4,5,6,3,7,6]
  p=[]
  q=[]
  for i in range(M):
    p.append(dp[A[i]-1])
    q.append(A[i])
  bp=[[0,0]for i in range(N+1)]
  for i in range(N-1):
    for j in range(len(p)):
      if i+p[j]>N:
        continue
      if bp[i][0]==0:
          if i!=0:
              continue
      bp[i+p[j]][0]=max(bp[i+p[j]][0],bp[i][0]+(10**bp[i][1])*q[j])
      bp[i+p[j]][1]=bp[i][1]+1
  print(bp[N][0])
if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, M = mapint()
As = list(mapint())
num_lis = [2, 5, 5, 4, 5, 6, 3, 7, 6]
need_m = [num_lis[a-1] for a in As]
dp = [-1]*(N+1)
dp[0] = 0

for i in range(1, N+1):
    for a, need in zip(As, need_m):
        if need>i:
            continue
        elif dp[i-need]==-1:
            continue
        elif dp[i-need]==0:
            dp[i] = max(dp[i], a)
        else:
            dp[i] = max(dp[i], dp[i-need]*10+a)

print(dp[-1])

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


def main():
    N, M = [int(x) for x in input().split()]
    A = [int(x) for x in input().split()]

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

    dp = [0] * (N + 1)

    for i in range(1, N + 1):
        for a in A:
            if match[a] <= i:
                if match[a] == i or dp[i - match[a]] != 0:
                    dp[i] = max(dp[i], dp[i - match[a]] * 10 + a)

    print(dp[-1])



if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

# ある本数で作れる数
candi = [[],[],[1],[7],[4],[2,3,5],[6,9],[8]]

# たとえば2と3を両方作れるときに、2を作るメリットはない。
if 2 in A and 3 in A:
  A.remove(2)
if 2 in A and 5 in A:
  A.remove(2)
if 3 in A and 5 in A:
  A.remove(3)
if 6 in A and 9 in A:
  A.remove(6)

for i in range(len(candi)):
  for j in range(len(candi[i])-1,-1,-1):
    if candi[i][j] not in A:
      del candi[i][j]

# マッチをある本数使って作れる桁数の最大値をdp
# そのときの使用文字も記録
# 最大値が同じときは、大小比較
dp = [-1] * (N + 1)
ans = [""] * (N + 1)
dp[0] = 0
def to_num(x):
  return int("".join(sorted(x, reverse = True)))
for i in range(len(candi)):
  if not candi[i]:
    continue
  num = str(candi[i][0]) # i文字使って作る文字
  # i文字使って作る
  for j in range(len(dp)):
    if dp[j] == -1:
      continue
    #print("j",j)
    if j + i > N:
      continue
    if dp[j + i] < dp[j] + 1:
      dp[j + i] = dp[j] + 1
      ans[j + i] = ans[j] + num
    elif dp[j + i] == dp[j] + 1:
      if to_num(ans[j + i]) < to_num(ans[j] + num):
        ans[j + i] = ans[j] + num
    #print(dp)
    #print(ans)

print(to_num(ans[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]
dp=[]
dp.append([0,0,0,0,0,0,0,0,0,0])
for i in range(n):
  dp.append([-1,-1,-1,-1,-1,-1,-1,-1,-1,-1])
allowed=[]
for i in a:
  allowed.append([i,D[i-1]])
for i in range(n):
  for j in allowed:
    temp=i+j[1]
    if temp<n+1 and dp[i][0]!=-1:
      if dp[temp][9]<dp[i][9]+1:
        for k in range(10):
          dp[temp][k]=dp[i][k]
        dp[temp][9]+=1
        dp[temp][j[0]-1]+=1
      elif dp[temp][9]==dp[i][9]+1:
        change=0
        for k in range(8,-1,-1):
          if k!=j[0]-1:
            breakflag=0
            if dp[temp][k]>dp[i][k]:
              change=-1
              breakflag=1
            if dp[temp][k]<dp[i][k]:
              change=1
              breakflag=1
          else:
            breakflag=0
            if dp[temp][k]>dp[i][k]+1:
              change=-1
              breakflag=1
            if dp[temp][k]<dp[i][k]+1:
              change=1
              breakflag=1
          if breakflag==1:
            break
        if change==1:
          for k in range(10):
            dp[temp][k]=dp[i][k]
          dp[temp][9]+=1
          dp[temp][j[0]-1]+=1
ans=[]
for i in range(8,-1,-1):
  for j in range(dp[n][i]):
    ans.append(str(i+1))
print(''.join(ans))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

from copy import deepcopy
def compare(A,B):
    tot_a = sum(A)
    tot_b = sum(B)
    if tot_a > tot_b:
        return A
    if tot_b > tot_a:
        return B
    for i in range(9,0,-1):
        if A[i] > B[i]:
            return A
        elif A[i] < B[i]:
            return B

def main():
    N,M = map(int,input().split())
    A = list(map(int,input().split()))
    match = (-1,2,5,5,4,5,6,3,7,6)

    dp = [[0]*10 for _ in range(1 + N)]
    changed = [0] * (N + 1)
    changed[0] = 1
    for i in range(N):
        for j in A:
            if i + 1 - match[j] >= 0 and changed[i + 1 - match[j]]:
                B = deepcopy(dp[i + 1 - match[j]])
                B[j] += 1
                if compare(dp[i + 1],B) == B:
                    dp[i + 1] = B
                    changed[i + 1] = 1
    ans = ''
    for i in range(9,0,-1):
        ans += str(i) * dp[-1][i] 
    print(ans)    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
a = [int(i) for i in input().split()]
match = [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 - match[j] < 0: continue
        if dp[i-match[j]] == -1: continue
        dp[i] = max(dp[i], dp[i-match[j]]*10+j)
# print(dp)
print(dp[n])

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
a = list(map(int, input().split()))
d = [10**5, 2,5,5,4,5,6,3,7,6]
dp = [(0, 0)] * (n + 1)
for i in range(n):
    if i > 0 and dp[i][0] == 0:
        continue
    k, _ = dp[i]
    for ai in a:
        if i + d[ai] <= n:
            dp[i+d[ai]] = max(dp[i+d[ai]], (k+1, ai))
ans = []
i = n
for _ in range(dp[n][0]):
    ans.append(str(dp[i][1]))
    i -= d[dp[i][1]]
print(''.join(ans))

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:
            dp[i+weight[a]] = max(dp[i+weight[a]],dp[i]*10+a)
print(dp[N])

Submission status: Accepted

Solution code:
N, M = list(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):  # dpで0~N本のマッチを探索
    for a in A:  # Aに入ってるもの（作れる数字）を探索
        if i + weight[a] < N + 1:  # i+(今回作る数字に必要なマッチ)本のマッチがN以下だったらOk
            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()))
a.sort()
p=[2,5,5,4,5,6,3,7,6]
num=[]
for x in a:
	num.append(p[x-1])
inf=10**8
dp=[-inf]*(n+1)
dp[0]=0
for i in range(n):
	for j in range(m):
		if i+num[j]<=n and dp[i]!=-inf:
			dp[i+num[j]]=max(dp[i+num[j]],dp[i]+1)
ans=""
now=n
for i in range(dp[n]):
	for j in range(m-1,-1,-1):
		if now-num[j]<0:
			continue
		if dp[now-num[j]]==dp[now]-1:
			now-=num[j]
			ans+=str(a[j])
			break
print(ans)

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, input().split())
A = list(map(int, input().split()))

w = (2,5,5,4,5,6,3,7,6)
dp = [-1] * (N+100)
dp[0] = 0
for i in range(N+1):
    if dp[i] < 0: continue
    for a in A:
        dp[i + w[a-1]] = max(dp[i + w[a-1]], dp[i]*10+a)

print(dp[N])

Submission status: Accepted

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

num_to_hon = [0, 2,5,5,4,5,6,3,7,6]
hon_to_num_dic = {}
for a in al:
    hon = num_to_hon[a]
    hon_to_num_dic.setdefault(hon,0)
    hon_to_num_dic[hon] = max(a, hon_to_num_dic[hon])


dp = [{'keta':0, 'num_cnts':[0]*10} for _ in range(n+10)]
for hon, num in hon_to_num_dic.items():
    dp[hon]['keta'] = 1
    dp[hon]['num_cnts'][num] += 1


for i in range(n):
    i_keta = dp[i]['keta']
    if i_keta == 0: continue
    for hon, num in hon_to_num_dic.items():
        i_num_cnts = dp[i]['num_cnts'][:]
        i_keta = dp[i]['keta']
        i_num_cnts[num] += 1
        next_dp = {'keta': i_keta+1, 'num_cnts':i_num_cnts[:]}
        # if i_keta == 0 and dp[i+hon]['keta'] > 0:
        #     continue
        if next_dp['keta'] > dp[i+hon]['keta']:
            dp[i+hon] = next_dp
            # print()
        elif next_dp['keta'] == dp[i+hon]['keta']:
            for comp_num in range(9,0,-1):
                if i_num_cnts[comp_num] > dp[i+hon]['num_cnts'][comp_num]:
                    dp[i+hon] = next_dp
                    break
                elif  i_num_cnts[comp_num] < dp[i+hon]['num_cnts'][comp_num]:
                    break


ans = []
for num in range(9,0,-1):
    ans.extend([str(num)]*dp[n]['num_cnts'][num])

print(''.join(ans))

Submission status: Accepted

Solution code:
def resolve():
    N, M = list(map(int, input().split()))
    A = list(map(int, input().split()))
    required = [None]+[2,5,5,4,5,6,3,7,6]
    dp = [0 for _ in range(max(10, N+1))]
    candidates = {}
    for a in A:
        req = required[a]
        if dp[req] < a:
            dp[req] = a
            candidates[req] = a
    #print(dp)
    #print(candidates)
    for i in range(N+1):
        for n_match, num in candidates.items():
            if i - n_match >= 0 and dp[i-n_match] != 0:
                dp[i] = max(dp[i], dp[i-n_match]*10+num)
    #print(dp)
    print(dp[N])

if '__main__' == __name__:
    resolve()

Submission status: Accepted

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

dp=[0]*(N+1)
cost=[0,2,5,5,4,5,6,3,7,6]
for i in range(1,N+1):
    for a in A:
        if i-cost[a]>=0:
            if dp[i-cost[a]]==0 and i-cost[a]>0:
                continue
            dp[i]=max(dp[i],dp[i-cost[a]]*10+a)
print(dp[-1])

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
a=list(map(int,input().split()))
temp=[0,2,5,5,4,5,6,3,7,6]
dp=[-1]*(n+1)
dp[0]=0
for i in range(n+1):
  for j in a:
    if i+temp[j]<n+1:
      dp[i+temp[j]]=max(dp[i+temp[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()))
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 = list(map(int, input().split()))
A = list(map(int, input().split()))

dp = [0] * (N+1)

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

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

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n, m = map(int, readline().split())
a = list(map(int, readline().split()))
memo = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [''] * (n + 1)
for aa in a:
    if memo[aa] <= n:
        dp[memo[aa]] = max(dp[memo[aa]], str(aa))
for i in range(n):
    if dp[i] == '':
        continue
    for aa in a:
        if i + memo[aa] <= n:
            v = str(aa) + dp[i]
            if len(dp[i + memo[aa]]) < len(v):
                dp[i + memo[aa]] = v
            else:
                dp[i + memo[aa]] = max(dp[i + memo[aa]], v)
print(dp[-1])

Submission status: Accepted

Solution code:
def main():
    n, m, *a = map(int, open(0).read().split())
    t = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
    a.sort(reverse=True)
    b = {}
    for i in a:
        x = t[i]
        if b.get(x) is not None:
            a.remove(i)
        else:
            b[x] = 0

    b = [t[i] for i in a]
    dp = [-float('Inf')] * (n + 10)
    dp[0] = 0
    for i in range(2, n + 1):
        dp[i] = max(dp[i - j] + 1 for j in b)

    nums = []
    for i in range(dp[n], 0, -1):
        for x in a:
            if dp[n - t[x]] == i - 1:
                nums.append(x)
                n -= t[x]
                break

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    n, m, *a = map(int, open(0).read().split())
    t = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
    a.sort(reverse=True)
    b = [t[i] for i in a]
    dp = [-float('Inf')] * (n + 10)
    dp[0] = 0
    for i in range(2, n + 1):
        dp[i] = max(dp[i - j] + 1 for j in b)

    nums = []
    for i in range(dp[n], 0, -1):
        for x in a:
            if dp[n - t[x]] == i - 1:
                nums.append(x)
                n -= t[x]
                break

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    n, m, *a = map(int, open(0).read().split())
    t = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
    a.sort(reverse=True)

    dp = [-float('Inf')] * (n + 10)
    dp[0] = 0
    for i in range(2, n + 1):
        for j in a:
            dp[i] = max(dp[i], dp[i - t[j]] + 1)

    nums = []
    for i in range(dp[n], 0, -1):
        for x in a:
            if dp[n - t[x]] == i - 1:
                nums.append(x)
                n -= t[x]
                break

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    n, m, *a = map(int, open(0).read().split())
    t = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
    a.sort(reverse=True)

    dp = [-float('Inf')] * (n + 10)
    dp[0] = 0
    for i in range(2, n + 1):
        for j in a:
            dp[i] = max(dp[i], dp[i - t[j]] + 1)

    nums = []
    k = dp[n]
    while n:
        for x in a:
            if dp[n - t[x]] == k - 1:
                nums.append(x)
                n -= t[x]
                break
        k -= 1

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10000000)
import os
import math
import bisect
import collections
import itertools
import heapq
import re
import queue

# import fractions

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)
# lcm = lambda x, y: (x * y) // fractions.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, M = il()
    A = il()
    matches = [2, 5, 5, 4, 5, 6, 3, 7, 6]
    dict = {i + 1: matches[i] for i in range(9)}
    dp = [-1] * (N + 1)
    dp[0] = 0

    for n in range(N + 1):
        for a in A:
            if n + dict[a] <= N:
                dp[n + dict[a]] = max(dp[n + dict[a]], dp[n] * 10 + a)
    print(dp[N])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10000000)
import os
import math
import bisect
import collections
import itertools
import heapq
import re
import queue

# import fractions

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)
# lcm = lambda x, y: (x * y) // fractions.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, M = il()
    A = sorted(il())
    matches = [2, 5, 5, 4, 5, 6, 3, 7, 6]
    dict = {i + 1: matches[i] for i in range(9)}
    dp = [-1] * (N + 1)
    dp[0] = 0

    for n in range(N + 1):
        for a in A:
            if n + dict[a] <= N:
                dp[n + dict[a]] = max(dp[n + dict[a]], dp[n] * 10 + a)
    print(dp[N])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def create_integer_string(counts):
    res = ""

    for i in range(9, 0, -1):
        count = counts[i]
        res += str(i) * count

    return res


def main():
    from copy import copy

    n, m = list(map(int, readline().split()))
    a = list(map(int, readline().split()))
    a.sort()
    pat = [-1, 2, 5, 5, 4, 5, 6, 3, 7, 6]
    match_nums = dict()

    for x in a:
        match_num = pat[x]
        match_nums[match_num] = x

    dp = [0] * (n + 1)
    dp_c = [[0] * 10 for _ in range(n + 1)]

    for i in range(n + 1):
        for match_num, val in match_nums.items():
            if i + match_num > n:
                continue
            if i > 0 and dp[i] == 0:
                continue
            if dp[i + match_num] < dp[i] + 1:
                dp[i + match_num] = dp[i] + 1
                dp_c[i + match_num] = copy(dp_c[i])
                dp_c[i + match_num][val] += 1
            elif dp[i + match_num] == dp[i] + 1:
                counts_cur = copy(dp_c[i + match_num])
                cur = create_integer_string(counts_cur)
                counts_new = copy(dp_c[i])
                counts_new[val] += 1
                new = create_integer_string(counts_new)
                if new > cur:
                    dp[i + match_num] = dp[i] + 1
                    dp_c[i + match_num] = copy(dp_c[i])
                    dp_c[i + match_num][val] += 1

    counts = dp_c[n]

    print(create_integer_string(counts))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
a = set(map(int,input().split()))
dp = [0]+[-float('inf')]*n
f = [0,2,5,5,4,5,6,3,7,6]
for i in range(n+1):
  for j in a:
    F = f[j]
    if F <= i:
      dp[i] = max(dp[i-F]*10+j,dp[i])
print(dp[n])

Submission status: Accepted

Solution code:
def main():  
  import sys
  read = sys.stdin.buffer.read
  readline = sys.stdin.buffer.readline
  readlines = sys.stdin.buffer.readlines

  n,m = map(int,readline().split())
  a = list(map(int,readline().split()))
  d5 = False
  d9 = False

  if 5 in a:
    d5 = True
  if 9 in a:
    d9 = True
  chk = set()
  for i in a:
    if d5 and (i == 2 or i == 3):
      continue
    if d9 and i == 6:
      continue
    chk.add(i)

  dp = [-float('inf')]*(n+1)
  dp[0] = 0
  f = [0,2,5,5,4,5,6,3,7,6]

  for i in range(2,n+1):
    for j in chk:
      F = f[j]
      if F <= i:
        dp[i] = max(dp[i-F]*10+j,dp[i])

  print(dp[n])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    n,m = LI()
    a = LI()
    match = [0,2,5,5,4,5,6,3,7,6]
    dp = [-1] * (n+1)
    dp[0] = 0
    for i in range(1,n+1):
        for x in a:
            if i < match[x]: continue
            if dp[i-match[x]] < 0: continue
            dp[i] = max(dp[i],dp[i-match[x]]*10+x)
    print(dp[-1])

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

kazu = [a[List[i]] for i in range(M)]

def dddd(kazu,X):
  dp = [ [ -float('inf') for j in range(X+1)]  for i in range(M)]
  for i in range(M):
    dp[i][0] = 0

  for i in range(M):
    for j in range(X+1):
      if kazu[i] <= j:
        dp[i][j] = max(dp[i][j-kazu[i]] + 1,dp[i-1][j])
      else:
        dp[i][j] = dp[i-1][j]
  return dp[-1]
   
keta_arr = dddd(kazu,N)
keta = keta_arr[-1]
List.sort(reverse=True)
ans = []

while keta>0:
  for aa in List:
    k = a[aa]
    if N-k < 0:
      continue
    if N-k >= 0:
      if keta_arr[N-k] == keta-1:       
        ans.append(aa)
        N = N-k
        keta -= 1
        break
ans.sort(reverse=True)
print(int(''.join(map(str,ans))))

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]

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

for i in range(N):
    for j in A:
        if i+B[j] <= N:
            DP[i+B[j]] = max(DP[i]*10+j, DP[i+B[j]])

print(DP[N])

Submission status: Accepted

Solution code:
"""
- minでの桁数
- その後の余りでgreedy
- 
"""

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

N, M = list(map(int, input().split()))
t_dic = {}
A = list(map(int, input().split()))
A = sorted(A)[::-1]
for a in A:
    t_dic[a] = num_dic[a]
min_v = min(t_dic.values())

dp = [0] * (N+8)
for i in range(N):
    for a in A:
        num = t_dic[a]
        if i !=0 and dp[i] == 0:
            continue
        dp[i+num] = max(10 * dp[i]+ a, dp[i+num])

print(dp[N])

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
a = list(map(int , input().split()))
t = [2,5,5,4,5,6,3,7,6]
cost = {ai: t[ai-1] for ai in a}

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

for i in range(1, n+1):
    dpi = -1
    for ai, ci in cost.items():
        if i - ci >= 0 and dp[i-ci] >= 0:
            dpi = max(dp[i-ci] * 10 + ai, dpi)
    dp[i] = dpi
print(dp[n])

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
a = list(map(int , input().split()))
t = [2,5,5,4,5,6,3,7,6]
cost = {ai: t[ai-1] for ai in a}

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

for i in range(n+1):
    tmp = []
    for ai, ci in cost.items():
        if i - ci >= 0 and dp[i-ci] >= 0:
            tmp.append(dp[i-ci] * 10 + ai)
    if len(tmp) > 0:
        dp[i] = max(tmp)
print(dp[n])