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: Runtime Error

Solution code:
import sys
from bisect import bisect_left
INF = 1 << 30

def main():
    N,M = map(int,input().split())
    A = set(map(str,input().split()))
    number = '174532968'
    necesary_match = (1,3,4,5,5,5,6,6,7)
    match = {i:j for i,j in zip(number,necesary_match)}

    if '1' in A:
        if N%2 == 0:
            ans = ['1'] * (N//2)
        else:
            for num in '7532':
                if num in A:
                    ans = ['1'] * ((N - match[num])//2) + [num]
                    break
    elif '7' in A:
        if N%3 == 0:
            ans = ['7'] * (N//3)
        elif N%3 == 1:
            flag = False
            for num in '496':
                if num in A:
                    flag = True
                    ans = ['7'] * ((N - match[num])//3) + [num]
                    break
            if not flag:
                for num in '5328':
                    if num in A:
                        ans = ['7'] * ((N - 2*match[num])//3) + [num] * 2
        else:
            flag = False
            for num in '5328':
                if num in A:
                    flag = True
                    ans = ['7'] * ((N - match[num])//3) + [num]
                    break
            if not flag:
                for num in '496':
                    if num in A:
                        ans = ['7'] * ((N - 2*match[num])//3) + [num] * 2
    elif '4' in A:
        if N%4 == 0:
            ans = ['4'] * (N//4)
        elif N%4 == 1:
            flag = False
            for num in '532':
                if num in A:
                    flag = True
                    ans = ['4'] * ((N - match[num])//4) + [num]
                    break
            if not flag:
                for num in '96':
                    if num in A:
                        flag = True
                        ans = ['4'] * ((N - match[num] - match['8'])//4) + [num,'8']
                        break
            if not flag:
                ans = ['4'] * ((N - match['8']*3)//4) + ['8'] * 3
        elif N%4 == 2:
            flag = False
            for num in '96':
                if num in A:
                    ans = ['4'] * ((N - match[num])//4) + [num]
                    flag = True
                    break
            if not flag:
                for num in '532':
                    if num in A:
                        ans = ['4'] * ((N - 2*match[num])//4) + [num] * 2
                        flag = True
                        break
            if not flag:
                ans = ['4'] * ((N - 2*match['8'])//4) + ['8'] * 2
        else:
            flag = False
            if '8' in A:
                flag = True
                ans = ['4'] * ((N - match['8'])//4) + ['8']
            if not flag:
                x = ''
                for num in '96':
                    if num in A:
                        x = num
                        break
                y = ''
                for num in '532':
                    if num in A:
                        y = num
                        break
                if x:
                    ans = ['4'] * ((N - match[x] - match[y])//4) + [x,y]
                else:
                    ans = ['4'] * ((N - 3*match[y])//4) + [y] *3
    else:
        x = ''
        for num in '532':
            if num in A:
                x = num
                break
        if x:
            if N%5 == 0:
                ans = [x] * (N//5)
            elif N&5 == 1:
                flag = False
                for num in '96':
                    if num in A:
                        flag = True
                        ans = [x] * ((N - match[num])//5) + [num]
                        break
                if not flag:
                    ans = [x] * ((N - 3*match['8'])//5) + ['8'] * 3
            elif N%5 == 2:
                if '8' in A:
                    ans = [x] * ((N - match['8'])//5) + ['8']
                else:
                    for num in '96':
                        if num in A:
                            ans = [x] * ((N - 2*match[num])//5) + [num] * 2
                            break
            elif N%5 == 3:
                if '8' in A:
                    flag = False
                    for num in '96':
                        if num in A:
                            flag = True
                            ans = [x] * ((N - match[num] - match['8'])//5) + ['8',num]
                            break
                    if not flag:
                        ans = [x] * ((N - 4*match['8'])//5) + ['8'] * 4
            elif N%5 == 4:
                if '8' in A:
                    ans = [x] * ((N - 2*match['8'])//5) + ['8'] * 2
                else:
                    for num in '96':
                        if num in A:
                            ans = [x] * ((N - 4*match[num])//5) + [num] * 4
                            break

        else:
            y = ''
            for num in '96':
                if num in A:
                    y = num
                    break
            if y:
                if N%6 == 0:
                    ans = [y] * (N//6)
                else:
                    k = N%6
                    ans = [y] * ((N - k*match['8'])//6) + ['8'] * k
            else:
                ans = ['8'] * (N//7)
    ans.sort(reverse = True)
    print(''.join(ans))
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
a = list(map(int, input().split()))
matchlist = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
numberlist = []
for i in range(m):
    numberlist.append(matchlist[a[i]])
numberlist = set(numberlist)
#dp[i]:i本でのmax桁
dp = [-10000000]*(n+1)
dp[0] = 0
for i in range(n):
    for j in numberlist:
        if i+j <= n:
            dp[i+j] = max(dp[i+j], dp[i]+1)


ans = []
d = dp[n]
a.sort(reverse = True)
for i in range(d):
    for j in a:
        if dp[n] == dp[n-matchlist[j]] + 1:
            n -= matchlist[j]
            ans.append(j)
            break
print("".join(map(str,ans)))

Submission status: Runtime Error

Solution code:
from collections import defaultdict
N,M,*A = map(int, open('0').read().split())
ls = [0]*10
ls[1] = 2
ls[2] = 5
ls[3] = 5
ls[4] = 4
ls[5] = 5
ls[6] = 6
ls[7] = 3
ls[8] = 7
ls[9] = 6
dic = defaultdict(int)
for a in A:
  k = ls[a]
  dic[k] = max(dic[k],a)
dp = [-1]*(N+1)
for k in dic.keys():
  if k>N:
    continue
  dp[k] = dic[k]
for i in range(N+1):
  for k in dic.keys():
    if i-k>0 and dp[i-k]!=-1:
      s = str(dp[i-k])
      m = int(s+str(dic[k]))
      dp[i] = max(dp[i], m)
print(dp[N])

Submission status: Runtime Error

Solution code:
from collections import defaultdict
N,M,*A = map(int, open(0).read().split())
ls = [0]*10
ls[1] = 2
ls[2] = 5
ls[3] = 5
ls[4] = 4
ls[5] = 5
ls[6] = 6
ls[7] = 3
ls[8] = 7
ls[9] = 6
dic = defaultdict(int)
for a in A:
  k = ls[a]
  dic[k] = max(dic[k],a)
dp = [-1]*(N+1)
for k in dic.keys():
  dp[k] = dic[k]
for i in range(N+1):
  for k in dic.keys():
    if i-k>0 and dp[i-k]!=-1:
      s = str(dp[i-k])
      m = int(str(dic[k])+s)
      dp[i] = max(dp[i], m)
print(dp[N])

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Mon May  4 20:56:12 2020
"""

import sys
import numpy as np
import itertools

sys.setrecursionlimit(10 ** 9)
#def input():
#    return sys.stdin.readline()[:-1]
mod = 10**9+7

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

A1 = np.array(A)
A1.sort()
matchi = np.array([99,2,5,5,4,5,6,3,7,6])

matchi = matchi[A1]
m = np.min(matchi)
m_n = list(A1[matchi == m])

ans = m_n * (N // m)

tmp = N % m
flg = True
matchi2 = matchi[matchi != m]
np.unique(matchi2)
counta = 1
while flg:
    tmp += m
    ans.pop()
#    print(ans,tmp)
    for s in itertools.combinations_with_replacement(matchi2,counta):
#        print(s)
        if tmp == np.sum(s):
            flg = False
            break
    counta += 1

for s1 in s:
    ans.append(A1[matchi == s1][-1])

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

Submission status: Runtime Error

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

d1 = {1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}
d2 = {2:[1],3:[7],4:[4],5:[5,3,2],6:[9,6],7:[8]}

# dp[i]:i本のマッチを使用した場合の最大桁数
dp = [-float('inf') for _ in range(n+1)]
dp[0] = 0
for i in range(1,n+1):
  for ai in a:
    if i-d1[ai] >= 0:
      dp[i] = max(dp[i-d1[ai]]+1,dp[i])

a.sort(reverse = True)
ans = ''
r = n
k = dp[n]
while(r > 0):
  for ai in a:
    if dp[r-d1[ai]] == k-1:
      ans += str(ai)
      r -= d1[ai]
      k -= 1
      break

print(ans)

Submission status: Runtime Error

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

T=[0,2,5,5,4,5,6,3,7,6]
B=[]
for i in A:
    B.append(T[i])
B=sorted(list(set(B)))
dp=[0 for i in range(N+1)]
AB=[[i,T[i]] for i in A]
AB=sorted(AB,reverse=True)

for i in range(1,N+1):
    for j in B:
        if i-j>=0 and dp[i-j]!=-1:
            dp[i]=max(dp[i],dp[i-j]+1)
            #print(i,j,dp[i])
    if dp[i]==0:
        dp[i]=-1
#print(dp)
#print(AB)

c=N
U=[0 for i in range(8)]
while c>0:
    for i in range(len(AB)):
        if dp[c]==dp[c-AB[i][1]]+1:
            U[AB[i][1]]+=1
            c-=AB[i][1]
            break
#print(U)

ans=""
if 9 in A:
    ans+='9'*U[6]
    U[6]=0
if 8 in A:
    ans+='8'*U[7]
if 7 in A:
    ans+='7'*U[3]
if 6 in A:
    ans+='6'*U[6]
if 5 in A:
    ans+='5'*U[5]
    U[5]=0
if 4 in A:
    ans+='4'*U[4]
if 3 in A:
    ans+='3'*U[5]
    U[5]=0
if 2 in A:
    ans+='2'*U[5]
if 1 in A:
    ans+='1'*U[2]

print(ans)

Submission status: Runtime Error

Solution code:
N, M = map(int,input().split())
A = list(map(int,input().split()))
A.sort(reverse = True)
d = [0,2,5,5,4,5,6,3,7,6]
S = set()
for a in A:
    S.add(d[a])

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

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

digit = dp[N]

def dfs(N, digit, ans):
    if digit == 0:
        if N == 0:
            return ans
        else:
            return 0
    for a in A:
        temp = dfs(N - d[a], digit - 1, ans * 10 + a)
        if temp:
            return temp

print(dfs(N, digit, 0))

Submission status: Runtime Error

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

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

def ketadp(N,M,A):
  dp=[0]*(N+1)
  for i in range(N):
    for j in A:
      if (i+1-honsuu[j])==0 or (i+1-honsuu[j]>0 and dp[i+1-honsuu[j]]!=0):
        dp[i+1]=max(dp[i+1],dp[i+1-honsuu[j]]+1)
  return dp
  

ans=""
keta=ketadp(N,M,A)
remain=keta[N]
match=N
#print(keta)

while(match>0):
  for i in A:
    #print(i,match,remain,keta[match-honsuu[i]])
    if(keta[match-honsuu[i]]==remain-1) and not (match-honsuu[i]!=0 and remain==1):
      ans+=str(i)
      remain-=1
      match-=honsuu[i]
      break;
print(ans)

Submission status: Runtime Error

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

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

def ketadp(N,M,A):
  dp=[0]*(N+1)
  for i in range(N):
    for j in A:
      if (i+1-honsuu[j])==0 or (i+1-honsuu[j]>0 and dp[i+1-honsuu[j]]!=0):
        dp[i+1]=max(dp[i+1],dp[i+1-honsuu[j]]+1)
  return dp
  

ans=""
keta=ketadp(N,M,A)
remain=keta[N]
match=N
#print(A)

while(match>0):
  for i in A:
    #print(i,match,remain,keta[match-honsuu[i]])
    if(keta[match-honsuu[i]]==remain-1):
      ans+=str(i)
      remain-=1
      match-=honsuu[i]
      break;
print(ans)

Submission status: Runtime Error

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
import numpy as np
def main():
    n=int(input())
    A=np.array([int(_) for _ in input().split()])
    while A.size>1:
        min_A=np.min(A)
        A=np.fmod(A,min_A)
        A=A[A>0]
        A=np.append(A,min_A)
        print(A)
    print(A[0])
    

if __name__=='__main__':
    main()

Submission status: Runtime Error

Solution code:
解説放送の１つめ
N,M = map(int, input().split())
A = list(map(int, input().split()))
f = [-1, 2,5,5,4,5,6,3,7,6] # 1-indexed
 
# dp[i]: マッチi本数で作れる最大の数(str)
dp = [None]*(N+1)
dp[0] = ""
 
# strの数の大きいほう
def max_str(s1:str, s2:str)->str:
    """return bigger one"""
    l1, l2 = len(s1), len(s2)
    if l1 != l2:
        return s1 if l1>l2 else s2
    if l1 == l2: 
        return s1 if s1>s2 else s2
    
for i in range(2, N+1):
    nxt = ""
    for aj in A:
        # 配列外参照と，i本ちょうどで作れないものはだめ
        if i-f[aj]<0 or dp[i-f[aj]]==None: continue
        nxt = max_str(nxt, 
                      dp[i-f[aj]]+str(aj))
    if nxt!="":
        dp[i] = nxt
    #print(dp)
print(dp[N])

Submission status: Runtime Error

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] + i] = max(d[i + l[ai] + i], k + 1)
print(dp[n])

Submission status: Runtime Error

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 dp[m-numk[i]]==dp[m]-1 and m-numk[i]>=0:
            ans.append(str(i))
            m-=numk[i]
            break
print(''.join(ans))

Submission status: Runtime Error

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 dp[m-numk[i]]+1==dp[m] and m-numk[i]>=0:
            ans.append(str(i))
            m-=numk[i]
            break
print(''.join(ans))

Submission status: Runtime Error

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: Runtime Error

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 dp[m-numk[i]]+1==dp[m] and m-numk[i]>=0:
      ans.append(str(i))
      m-=numk[i]
      break
print(''.join(ans))

Submission status: Runtime Error

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]+[-float('inf')]*(N)
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 dp[m-numk[i]]+1==dp[m] and m-numk[i]>=0:
      ans.append(str(i))
      m-=numk[i]
      break
print(''.join(ans))

Submission status: Runtime Error

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]+[-float('inf')]*(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 range(M):
    if dp[m-numk[A[i]]]+1==dp[m] and m-numk[A[i]]>=0:
      ans.append(str(A[i]))
      m-=numk[A[i]]
      break
print(''.join(ans))

Submission status: Runtime Error

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)
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 range(M):
    if dp[m-numk[A[i]]]+1==dp[m] and m-numk[A[i]]>=0:
      ans.append(str(A[i]))
      m-=numk[A[i]]
      break
print(''.join(ans))

Submission status: Runtime Error

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]+[-float('inf')]*(N)
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 range(M):
    if dp[m-numk[A[i]]]+1==dp[m] and m-numk[A[i]]>=0:
      ans.append(str(A[i]))
      m-=numk[A[i]]
      break
print(''.join(ans))

Submission status: Runtime Error

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]+[-float('inf')]*(N)
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 range(M):
    if dp[m-numk[A[i]]]+1==dp[m] and m-numk[A[i]]>=0:
      ans.append(A[i])
      m-=numk[A[i]]
      break
ans.sort(reverse=True)
for i in range(len(ans)):
  ans[i]=str(ans[i])
a=''.join(ans)
print(a)

Submission status: Runtime Error

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]+[-float('inf')]*(N)
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 range(M):
    if dp[m-numk[A[i]]]+1==dp[m]:
      ans.append(A[i])
      m-=numk[A[i]]
      break
ans.sort(reverse=True)
for i in range(len(ans)):
  ans[i]=str(ans[i])
a=''.join(ans)
print(a)

Submission status: Runtime Error

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]+[-float('inf')]*(N)
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 range(M):
    if dp[m-numk[A[i]]]+1==dp[m]:
      ans.append(A[i])
      m-=numk[A[i]]
ans.sort(reverse=True)
for i in range(len(ans)):
  ans[i]=str(ans[i])
a=''.join(ans)
print(a)

Submission status: Runtime Error

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 dp[X - mapk[k]] == dp[X] - 1:
                ans += str(k)
                X -= mapk[k]
                break
    print(ans)
main()

Submission status: Runtime Error

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 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: Runtime Error

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}


def dfs(k):
    if k == 0:
        return 0, -1
    if k in memo:
        return memo[k]

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

    memo[k] = (max_value, max_d)
    return max_value, max_d


memo = dict()
print(dfs(n)[0])

Submission status: Runtime Error

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 dp[i-w]==-1:
      continue
    dp[i]=max(dp[i],dp[i-w]*10+v)

Submission status: Runtime Error

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 dp[cur-L[temp-1]] == dp[cur]-1:
            ans = ans+str(temp)
            cur -= L[temp-1]
            break
print(ans)

Submission status: Runtime Error

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)

BAD = "z"*10001
def foo(n,k):
    if n<mn*k:
        ret = ""
    elif n==mn*k:
        ret = str(mni)*k
    elif k==1:
        ret = ""
        for i in range(m-1,-1,-1):
            if cs[a[i]]==n:
                ret = str(a[i])
                break
    else:
        mxs = ""
        for x in a:
            v = foo(n-cs[x],k-1)
            if v=="":
                continue
            if x<mn:
                vv = v+str(x)
            else:
                vv = str(x)+v
            mxs = max(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} k {k}")
#ddprint(a)
print(foo(n,k))

Submission status: Runtime Error

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)>=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: Runtime Error

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])

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

def main(dic3,dic4):
    dic1=sorted([[str(i),dic3[i]] for i in dic3],key=lambda x:x[0],reverse=True)
    dic2=sorted([[str(i),dic4[i]] for i in dic4],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(Motodic)
    tempdic[n]+=1
    if i-a>=0 :
        flag=main(dp[a],tempdic)
        if flag:
            dp[a]=tempdic

    for i in range(len(dp)):
        if i-a>=0 and _sum(dp[i-a]):

            if _sum(dp[i])<_sum(dp[i-a])+1:
                try:
                    tempdic=copy.copy(dp[i-a])
                    tempdic[n]+=1
                    dp[i]=tempdic
                except:
                    pass
            elif _sum(dp[i])==_sum(dp[i-a])+1:
                try:
                    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: Runtime Error

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])

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

def main(dic3,dic4):
    dic1=sorted([[str(i),dic3[i]] for i in dic3],key=lambda x:x[0],reverse=True)
    dic2=sorted([[str(i),dic4[i]] for i in dic4],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(Motodic)
    tempdic[n]+=1
    #flag=main(dp[a],tempdic)
    if flag:
        dp[a]=tempdic
    try:
        for i in range(len(dp)):
            if i-a>=0 and _sum(dp[i-a]):

                if _sum(dp[i])<_sum(dp[i-a])+1:
                    try:
                        tempdic=copy.copy(dp[i-a])
                        tempdic[n]+=1
                        dp[i]=tempdic
                    except:
                        pass
                elif _sum(dp[i])==_sum(dp[i-a])+1:
                    try:
                        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
                    except:
                        pass
    except:
        pass

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)