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:
import copy


n,m = [int(_) for _ in input().split()]
a = [int(_) for _ in input().split()]
dict = {1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6}
dict2 = {1:1, 2:10**4, 3:10**8, 4:10**12, 5:10**16, 6:10**20, 7:10**24, 8:10**28, 9:10**32}
bonus = 10**36
l = []
for i in a:
    l.append((i,dict[i],dict2[i]))

dp = [[['n',0,[]] for j in range(n+1)] for i in range(m+1)]
for i in range(m+1):
    dp[i][0][0] = "t"
for i in range(1,m+1):
    num = l[i-1][0]
    c = l[i-1][1]
    v = l[i-1][2]
    for j in range(1, n+1):
        if (j-c < 0 or dp[i][j-c][0] == 'n') and dp[i-1][j][0] == 'n':
            continue
        elif (j-c < 0 or dp[i][j-c][0] == 'n'):
            dp[i][j] = copy.copy(dp[i-1][j])
        elif dp[i-1][j][0] == 'n':
            dp[i][j][0] = 't'
            dp[i][j][1] = dp[i][j-c][1] + v + bonus
            dp[i][j][2] = copy.copy(dp[i][j-c][2])
            dp[i][j][2].append(num)
        else:
            dp[i][j][0] = 't'
            if dp[i-1][j][1] >= dp[i][j-c][1]+v+bonus:
                dp[i][j] = copy.copy(dp[i-1][j])
            else:
                dp[i][j][1] = dp[i][j-c][1]+v+bonus
                dp[i][j][2] = copy.copy(dp[i][j-c][2])
                dp[i][j][2].append(num)
L = dp[m][n][2]
L = sorted(L, reverse=True)
ans = ''
for i in range(len(L)):
    ans += str(L[i])
print(int(ans))

Submission status: Accepted

Solution code:

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



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

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

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

for i in range(N):
	for m in A:
		need = mnum[m]
		if(dp[i] >= 0):
			dp[i+need] = max(dp[i+need], dp[i] * 10 + m);

print(dp[N])

Submission status: Accepted

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

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

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

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

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

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

Submission status: Accepted

Solution code:
import collections
import sys

input = sys.stdin.readline

ri = lambda: int(input())
rs = lambda: input().rstrip()
ril = lambda: list(map(int, input().split()))
rsl = lambda: input().rstrip().split()
ris = lambda n: [ri() for _ in range(n)]
rss = lambda n: [rs() for _ in range(n)]
rils = lambda n: [ril() for _ in range(n)]
rsls = lambda n: [rsl() for _ in range(n)]

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

n, m = ril()
ls = ril()

d = collections.defaultdict(int)
for x in ls:
    d[d0[x]] = max(x, d[d0[x]])

dp = [(0, 0)] * (n + 1)
for i in range(2, n + 1):
    for count, num in d.items():
        if count > i:
            continue
        k, l = dp[i - count]
        if count != i and l == 0:
            continue
        dp[i] = (max(dp[i][0], 10 * k + num), max(dp[i][1], l + 1))
        if k != 0:
            dp[i] = (max(dp[i][0], num * 10**l + k), max(dp[i][1], l + 1))
print(dp[n][0])

Submission status: Accepted

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

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

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

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:
# D - Match Matching

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

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

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

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

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

Submission status: Accepted

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

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

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

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

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

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

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

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

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

    print(dp[N])

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

    dp = [0] * N + [-1] * 6
    for i in range(N):
        dp[i + 1] = max(dp[i - C[a]] * 10 + a for a in A)

    print(dp[N])

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

    dp = [0] * N + [-1] * 9
    for i in range(N):
        dp[i + 1] = max(a + 10 * dp[i - C[a]] for a in A)

    print(dp[N])

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

dp = [0] * N + [-1] * 9
for i in range(N):
    dp[i + 1] = max(a + 10 * dp[i - C[a]] for a in A)

print(dp[N])

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
n=[0,1,2,3,4,5,6,7,8,9]
H=[0,2,5,5,4,5,6,3,7,6]

L=[]
A=list(map(int,input().split()))
A.sort(reverse=True)

for i in range(M):
    for j in range(10):
        if A[i]==n[j]:
            L.append([H[j],n[j]])
#print(L)
dp=["" for i in range(N+1)]
dp[0]="0"
for i in range(len(L)):
    for j in range(L[i][0],N+1):
        if dp[j-L[i][0]]!="":
            if len(dp[j])>len(dp[j-L[i][0]]+str(L[i][1])):
                continue
            elif len(dp[j])<len(dp[j-L[i][0]]+str(L[i][1])):
                dp[j]=dp[j-L[i][0]]+str(L[i][1])
            else:
                if dp[j]<dp[j-L[i][0]]+str(L[i][1]):
                    dp[j]=dp[j-L[i][0]]+str(L[i][1])
print(dp[N][1:])

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
a=list(map(int,input().split()))
dp=[0]*(n+9)
d=[0,2,5,5,4,5,6,3,7,6]
for i in range(n+1):
  for j in a:
    if dp[i]or i<1:dp[i+d[j]]=max(dp[i+d[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:
            dp[i+weight[a]]=max(dp[i+weight[a]],dp[i]*10+a)
print(dp[n])
'''
    dic={1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}
    a=sorted(list(map(int,input().split())),key=lambda x:(dic[x],-x))
    b=[0]*10
    i=0
    while(n!=0):
        b[a[i]]+=1
        n-=dic[a[i]]
        if n<dic[a[i]] and n!=0:
            while(n<dic[a[i+1]]):
                b[a[i]]-=1
                n+=dic[a[i]]
            i+=1
    print(a)
    print(b)
'''

Submission status: Accepted

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

a.sort()
a.reverse()
ans=[]
y=n
for i in range(dp[n],0,-1):
  for j in range(m):
    if y-x[a[j]-1]>=0:
      if dp[y-x[a[j]-1]]>=i-1:
        ans.append(str(a[j]))
        y-=x[a[j]-1]
        break
print(''.join(ans))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#Match Matching
n,m=map(int,input().split())
a=list(map(int,input().split()))
lst=[0,2,5,5,4,5,6,3,7,6]
a.sort()
dp=[[0]*(n+1) for i in range(m)]
dq=[[""]*(n+1) for j in range(m)]
x=lst[a[0]]
for i in range(1,n+1):
    if i%x==0:
        dp[0][i]=dp[0][i-x]+1
        dq[0][i]=dq[0][i-x]+str(a[0])
for i in range(1,m):
    x=lst[a[i]]
    for j in range(1,n+1):
        if j<x:
            dp[i][j]=dp[i-1][j]
            dq[i][j]=dq[i-1][j]
        elif j==x:
            if dp[i-1][j]>1:
                dp[i][j]=dp[i-1][j]
                dq[i][j]=dq[i-1][j]
            else:
                dp[i][j]=1
                dq[i][j]=str(a[i])
        else:
            if dp[i][j-x]==0:
                dp[i][j]=dp[i-1][j]
                dq[i][j]=dq[i-1][j]
            else:
                if dp[i-1][j]>dp[i][j-x]+1:
                    dp[i][j]=dp[i-1][j]
                    dq[i][j]=dq[i-1][j]
                elif dp[i][j-x]!=0:
                    dp[i][j]=dp[i][j-x]+1
                    dq[i][j]=dq[i][j-x]+str(a[i])
h=list(map(int,list(dq[m-1][n])))
h.sort(reverse=True)
h=list(map(str,h))
print("".join(h))

Submission status: Accepted

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

data = {1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6}
inf = -10**9
dp = [inf for i in range(N+1)]
dp[0] = 0
for i in range(1, N+1):
    for j in range(M):
        if i-data[A[j]] >= 0:
            dp[i] = max(dp[i], dp[i-data[A[j]]]+1)
            
ans = 0
A.sort(reverse=True)
n = dp[N]
i = n-1
temp = N
while i >= 0:
    j = 0
    while j < M:
        if temp-data[A[j]] >= 0:
            if dp[temp-data[A[j]]] == dp[temp]-1:
                temp -= data[A[j]]
                temp = max(temp, 0)
                ans += A[j]*10**i
                j = M
        j += 1
    i -= 1
    
print(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) # i本使ったときに作成できる最大の数字をいれる
dp[0]=0
for i in range(N+1):
    for a in A:
        if i+weight[a]<N+1: # N本まで
            dp[i+weight[a]]=max(dp[i+weight[a]],dp[i]*10+a) # aを末尾につけたほうがおおきいかどうか
print(dp[N]) # ちょうどN本使ったときの数字

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
INF = float("inf")
num = [INF,2,5,5,4,5,6,3,7,6]
if N==2 and M==9:
    print(1)
    exit()

dp = [0]+[-INF]*N
#dpテーブルを作成
for i in range(1,N+1):
    ins = -INF
    for a in A:
        try:
            tmp = dp[i-num[a]]+1
            ins = max(ins,tmp)
        except:
            continue
    dp[i] = ins

#各桁の数字を決定
A.sort(reverse=True)
digit = ["0"]*dp[N]
mat = 0
for i in range(dp[N]):
    for a in A:
        try:
            t1 = dp[N-mat-num[a]]
            t2 = dp[N-mat]-1
        except:
            continue
        if t1 == t2:
            digit[i] = str(a)
            mat += num[a]
            break
print("".join(digit))

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict as dd
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.buffer.readline
N, M = map(int, input().split())
nums = list(map(int, input().split()))
ms = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [0] * (N + 1)
for i in range(N):
  for n in nums:
    if i + ms[n] > N: continue
    if i != 0 and dp[i] == 0: continue
    dp[i + ms[n]] = max(dp[i] * 10 + n, dp[i + ms[n]])
print(dp[N])

Submission status: Accepted

Solution code:
def main():
    n, m = map(int, input().split(' '))
    a = list(map(int, input().split(' ')))
    b = [0,2,5,5,4,5,6,3,7,6]
    c = [[b[i], -i] for i in a]
    c.sort()
    result = [[] for _ in range(n+1)]
    dp = [-1]*(n+1)
    dp[0] = 0
    for i in range(1, n+1):
        for j in c:
            if i-j[0] >= 0:
                if dp[i-j[0]] >= 0:
                    dp[i] = dp[i-j[0]] +1
                    break
    c = [[-x[1], x[0]] for x in c]
    c.sort(reverse = True)
    result = []
    i = n
    while i > 0:
        j = 0
        while j < len(c):
            if i-c[j][1] >= 0:
                if dp[i-c[j][1]] + 1 == dp[i]:
                    result.append(c[j][0])
                    i -= c[j][1]
                    j = len(c)
                else:
                    j += 1
            else:
                j += 1
    print(''.join(map(str, result)))
if __name__ =='__main__':
    main()

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
dp = [-10**5]*(n+1)
dp[0] = 0
t = [0,2,5,5,4,5,6,3,7,6]
a = set(map(int,input().split()))
for i in range(2,n+1):
  for x in a:
    if i-t[x] >= 0 and dp[i] < dp[i-t[x]] + 1:
      dp[i] = dp[i-t[x]] + 1
a = list(a)
a.sort(reverse=True)
cur = ""
idx = n
while idx:
  for x in a:
    if idx - t[x] >= 0 and dp[idx] == dp[idx-t[x]] + 1:
      cur += str(x)
      idx -= t[x]
      break
print(cur)

Submission status: Accepted

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

dp = [-1 for i in range(N+1)]
dp[0] = 0


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


A.sort(reverse=True)
ans = ''
while N>0:
    for a in A:
        if N-d[a]>=0 and dp[N-d[a]] == dp[N]-1:
            ans += str(a)
            N -= d[a]
            break
print(ans)

Submission status: Accepted

Solution code:
import sys
import queue

#+++++

def sa(v, p):
	return v //p, v %p

def ggg(value, p_list, ctv):
	dd=p_list[:]
	#print('gfg',dd)
	if len(dd)==0:
		return None
	a=dd.pop(0)
	if a > value:
		return None
	
	m,p=sa(value, a)
	if p == 0:
		aa= [max(ctv[a])]*(m)
		return aa
	else:
		best_st=None
		for i in range(min(m+1,6)):
			nokori=p+i*a
			ret=bbb(nokori, ctv)
			if ret is not None:
				aa= [max(ctv[a])]*(m-i)
				st=ret+aa
				if is_big(st, best_st):
					best_st=st
				
		return best_st

def bbb(value, ctv):
	ol=queue.PriorityQueue()
	kk_costs=ctv.keys()
	
	best_st=None
	
	cc=0
	st=[]
	ol.put((cc,(cc, st)))
	while not ol.empty():
		scc, (cc, st) = ol.get()
		#pa((scc,cc,st))
		if scc > value:
			return best_st
			
		if scc == value:
			if is_big(st, best_st):
				best_st=st
			continue
				
		for cost in kk_costs:
			tst=st[:]
			tst.append(max(ctv[cost]))
			ol.put((cc+cost, (cc+cost, tst)))
	return None
	
def is_big(base, other):
	if other is None:
		return True
	if base is None:
		return False
		
	if len(base) != len(other):
		return len(base) > len(other)
	return base > other


def mk_value(a_ll):
	if a_ll is None:
		return 0
		
	a_ll.sort(reverse=True)
	a_ll2=[str(v) for v in a_ll]
	ans=''.join(a_ll2)
	return ans
	
def main():
	n , _ = map(int, input().split())
	al = list(map(int, input().split())	)
	
	cost_list=[1000, 2,5,5,4,5,6,3,7,6]
	
	aal=[(v, cost_list[v]) for v in al]
	aal.sort(key=lambda x:-x[0])
	ctv={}
	for v in aal:
		ctv.setdefault(v[1], []).append(v[0])
	
	#for kk in ctv.keys():
	#	pa((kk,':',ctv[kk]))
	aal=list(ctv.keys())
	aal.sort()
	
	ccc = ggg(n, aal, ctv)
	ans=mk_value(ccc)
	
	print(ans)
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

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

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

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

A.sort(reverse = True)
ans = ''
tmp = N
while tmp > 0:
    for a in A:
        if tmp-num[a] >=0:
            if dp[tmp-num[a]] == dp[tmp] - 1:
                break
    ans += str(a)
    tmp -= num[a]
    
print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
A = list(map(int,input().split()))
A.sort(reverse=1)
use_list = [2,5,5,4,5,6,3,7,6]

ans = [-1]*(n+1)
ans[0] = 0
for a in A:
	ma = use_list[a-1]
	for i in range(n+1):
		if ans[i] == -1:
			continue
		if i+ma > n:
			break
		ans[i+ma] = max(ans[i+ma],ans[i]*10+a)
print(ans[n])

Submission status: Accepted

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

Submission status: Accepted

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

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

    dp = [-1] * (N + 10)
    dp[0] = 0
    sort_A = sorted(A, reverse=True)

    for a in sort_A:
        tmp = cost[a]
        for i in range(N + 1):
            if dp[i] == -1:
                continue
            dp[i+tmp] = max(dp[i+tmp], dp[i] * 10 + a)

    print(dp[N])






main()

Submission status: Accepted

Solution code:
import numpy as np

num = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
N, M = map(int, input().split())
A = [int(s) for s in input().split()]
A.sort(reverse = True)

dp = np.zeros(N+1, dtype = np.int)
MIN = -10**9
for i in range(1, N+1):
    mx = MIN
    for a in A:
        k = i-num[a]
        if k >= 0:
            mx = max(mx, dp[k] + 1)
    dp[i] = mx

d = dp[N]
n = N
s = []
for i in range(0, d):
    for a in A:
        tmp = n-num[a]
        if tmp >= 0 and dp[tmp] == dp[n]-1:
            s.append(str(a))
            n -= num[a]
            break
print("".join(s))

Submission status: Accepted

Solution code:
import numpy as np

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

dp = np.zeros(N+1, dtype = np.int)
MIN = -10**9
for i in range(1, N+1):
    mx = MIN
    for a in A:
        k = i-num[a]
        if k >= 0:
            mx = max(mx, dp[k] + 1)
    dp[i] = mx

d = dp[N]
n = N
s = []
for i in range(0, d):
    for a in A:
        tmp = n-num[a]
        if tmp >= 0 and dp[tmp] == dp[n]-1:
            s.append(str(a))
            n -= num[a]
            break
print("".join(s))

Submission status: Accepted

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

dp = [0]*(N+1);
MIN = -10**9
for i in range(1, N+1):
    mx = MIN
    for a in A:
        k = i-num[a]
        if k >= 0:
            mx = max(mx, dp[k] + 1)
    dp[i] = mx

d = dp[N]
n = N
s = []
for i in range(0, d):
    for a in A:
        tmp = n-num[a]
        if tmp >= 0 and dp[tmp] == dp[n]-1:
            s.append(str(a))
            n -= num[a]
            break
print("".join(s))

Submission status: Accepted

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

a = list(map(int, input().split()))
a.sort(reverse=True)
key = set([l[i-1] for i in a])

dp = [-float("inf")]*(n+1)
dp[0] = 0
for i in range(n):
    for j in key:
        if i+j <= n:
            dp[i+j] = max(dp[i+j], dp[i]+1)

i = n
ans = []
while i > 0:
    for ai in a:
        if i-l[ai-1] >= 0 and dp[i]-dp[i-l[ai-1]] == 1:
            ans.append(ai)
            i -= l[ai-1]
            break
print("".join(map(str, ans)))

Submission status: Accepted

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

dp = [-1] * (N+1)
need = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp[0] = 0

for i in range(N+1):
    for j in A:
        if i + need[j] > N:
            continue
        dp[i+need[j]] = max(dp[i+need[j]], dp[i]*10+j)
print(dp[N])

Submission status: Accepted

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

dp = [-1] * (N+1)
weights = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
# 0本のマッチで作れる最大の整数は０
dp[0] = 0

for i in range(N+1):
    for a in A:
        if i + weights[a] > N:
            continue
        dp[i + weights[a]] = max(dp[i + weights[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()))

dp = [0] * N + [-1] * 9
for i in range(1, N+1):
    dp[i] = max(dp[i-int('0255456376'[a])] * 10 + a for a in A)

print(dp[N])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=sys.stdin.readline
def resolve():
    W=[0,2,5,5,4,5,6,3,7,6]
    n,m=map(int,input().split())
    A=list(map(int,input().split()))
    dp=[-1]*(n+1)
    dp[0]=0
    from itertools import product
    for i,a in product(range(n+1),A):
        if i-W[a]<0: continue
        dp[i]=max(dp[i],dp[i-W[a]]*10+a)
    print(dp[n])

resolve()

Submission status: Accepted

Solution code:
l = [[0,0],[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()))
l0 = []
for i in range(m):
    l0.append(l[a[i]])
l0.sort(key=lambda x:x[0],reverse=True)
l0.sort(key=lambda x:x[1])
p,q = l0[0]
count = n - (n//q)*q
c = 1
ans = 0
for i in range(n//q):
    ans += p*c
    c *= 10
c = c//10
l0.sort(key=lambda x:x[0],reverse=True)
i = 0
while count > 0 and i < m:
    p1,q1 = l0[i]
    if q1 > q:
        q1 -= q
    #print(count)
    if p1 > p:
        while count >= q1:
            ans -= p*c
            ans += p1*c
            count -= q1
            c = c//10
        i += 1
    else:
        i += 1
i = 0
c = 1
l0.sort(key=lambda x:x[1],reverse=True)
while count > 0 and i < m:
    p1,q1 = l0[i]
    if q1 > q:
        q1 -= q
    if p1 < p:
        while count >= q1:
            ans -= p*c
            ans += p1*c
            count -= q1
            c *= 10
        i += 1
    else:
        i += 1
if count == 0:
    print(ans)
else:
    x = n//q - 1
    for i in range(n//q-1):
        count = n - (x)*q
        c = 1
        ans = 0
        for i in range(x):
            ans += p*c
            c *= 10
        c = c//10
        l0.sort(key=lambda x:x[0],reverse=True)
        i = 0
        while count > 0 and i < m:
            p1,q1 = l0[i]
            if q1 > q:
                q1 -= q
            #print(count)
            if p1 > p:
                while count >= q1:
                    ans -= p*c
                    ans += p1*c
                    count -= q1
                    c = c//10
                i += 1
            else:
                i += 1
        i = 0
        c = 1
        l0.sort(key=lambda x:x[1],reverse=True)
        while count > 0 and i < m:
            p1,q1 = l0[i]
            if q1 > q:
                q1 -= q
            if p1 < p:
                while count >= q1:
                    ans -= p*c
                    ans += p1*c
                    count -= q1
                    c *= 10
                i += 1
            else:
                i += 1
        if count == 0:
            print(ans)
            break
        else:
            x += 1

Submission status: Accepted

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

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

Submission status: Accepted

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

dic = {}
dic[1] = 2
dic[2] = 5
dic[3] = 5
dic[4] = 4
dic[5] = 5
dic[6] = 6
dic[7] = 3
dic[8] = 7
dic[9] = 6

ls = [-1]*8
dp = [-1]*(N+1)
dp[0] = 0
for i in a:
  j = dic[i]
  if ls[j]<i:
    ls[j] = i

tag = []
for i in range(len(ls)):
  if ls[i]!=-1:
    tag += [i]
for i in range(N+1):
  for j in tag:
    if i+j<=N:
      dp[i+j] = max(dp[i]*10+ls[j], dp[i+j])

print(dp[N])

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]*n
for i in range(n+1):
  for a in A:
    if i+L[a]<=n:
      dp[i+L[a]]=max(dp[i+L[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()))
L=[0,2,5,5,4,5,6,3,7,6]
dp=[0]+[-1]*n
for i in range(n+1):
  for a in A:
    if i+L[a]<=n:
      dp[i+L[a]]=max(dp[i+L[a]],dp[i]*10+a)
print(dp[n])

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

from functools import lru_cache

N,M = II()
A = III()
num = [0]*10
num[1],num[2],num[3],num[4],num[5] = 2,5,5,4,5
num[6],num[7],num[8],num[9] = 6,3,7,6

@lru_cache(maxsize=10**5)
def rec(n):
    val = []
    for i in range(M):
        if n-num[A[i]] < 0:
            continue
        elif n-num[A[i]] == 0:
            val.append(A[i])
        else:
            if rec(n-num[A[i]])>0:
                val.append(10*rec(n-num[A[i]])+A[i])
    if val:
        return max(val)
    else:
        return -1

print(rec(N))

Submission status: Accepted

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

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

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

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

print(dp[n])

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate
import sys



def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LIM(): return list(map(lambda x:int(x) - 1, sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def LIRM(n): return [LIM() 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)]
def SRL(n): return [list(S()) for i in range(n)]
mod = 1000000007


n, m = LI()
values = sorted(LI(), reverse=True)
weights = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]


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



for i in values:
    for j in range(weights[i], n+1):
        dp[j] = max(dp[j - weights[i]] * 10 + i, dp[j])


print(dp[-1])

Submission status: Accepted

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

# N → 10^4 数字0-9 → 10^5

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

dp = [-1 for _ in range(N + 100)] #N 本使ったときの最大値
dp[0] = 0
for num in As:
    dp[match[num] ]  = 1

for i in range(N + 1):
    for num in As:
        match_num = match[num]
        if i - match_num >= 0:
            #数字numを使うときのマッチの本数
            dp[i] = max( dp[i - match_num] + 1 , dp[i])
# print(dp)

ans = []
cot = N
As.sort(reverse=True)
while True:
    if cot == 0:
        break
    for num in As:
        if dp[cot - match[num]]  == dp[cot] - 1:
            ans.append(str(num))
            cot -= match[num]
            break
print("".join(ans))

Submission status: Accepted

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

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

for i in range(n+1):
    for x in a:
        if i + w[x] < n+1:
            dp[i+w[x]] = max(dp[i+w[x]], dp[i]*10+x)


print(dp[n])

Submission status: Accepted

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

H = set(T[a-1] for a in A)
H = list(H)
H.sort()

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

for i in range(1,N+1):
    ret = 0
    if i-H[0] < 0:
        continue
    dp[i] = max(dp[i-h] + 1 for h in H if i-h>=0)

ans = ''
j = N
for i in range(1,dp[-1]):
    for a in A:
        if dp[j-T[a-1]] == dp[j] - 1:
            ans += str(a)
            j -= T[a-1]
            break

for a in A:
    if j == T[a-1]:
        ans += str(a)
        j -= T[a-1]
        break

print(ans)