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: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
a = list(map(int, input().split()))
use = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [[0] * 10 for i in range(n+1)]

def makenum(x,y):
    res = 0
    for i in range(y):
        res = res* 10 + x
    return res
    
for i in range(1,n+1):
    kouho = []
    for j in a:
        if i - use[j] >= 0:
            if dp[i-use[j]] == [0] * 10 and i - use[j] != 0: # マッチの数が合わない場合
                continue #何もしない
            else:
                copy = dp[i-use[j]][:]
                copy[j] += 1
                kouho.append(copy)
    if kouho == []: #空の場合
        continue #何もしない
    else:
        usearray = []
        usenum = 0
        for array in kouho:
            tmpnum = 0
            for k in range(9,0,-1):
                tmpnum = tmpnum * (10**array[k]) + makenum(k,array[k])
            if tmpnum > usenum:
                usearray = array
                usenum = tmpnum
        dp[i] = usearray
ans = ""
for i in range(9,0,-1):
    ans += (str(i) * dp[n][i])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
A = [int(x) - 1 for x in input().split()]
match = [2, 5, 5, 4, 5, 6, 3, 7, 6]
for a in range(9):
  if a not in A:
    match[a] = N + 1
match.reverse()
L = []
for m in range(7, 1, -1):
  if m in match:
    L.append([m, 9 - match.index(m)])
DP = [[0, []] for i in range(N + 1)]
def insert(S, m):
  l, r = 0, len(S)
  if m >= S[0]:
    return 0
  if S[-1] > m:
    return r
  while r - l > 1:
    mid = (l + r) // 2
    if S[mid] > m:
      l = mid
    else:
      r = mid
  return r
for i in range(1, N + 1):
  for m, l in L:
    if i == m and DP[i][0] == 0:
        DP[i] = [l, [str(l)]]
    elif i > m and DP[i - m][0]:
      r = insert(DP[i - m][1], str(l))
      a = DP[i - m][1][:r] + [str(l)] + DP[i - m][1][r:]
      b = int(''.join(a))
      if b > DP[i][0]:
        DP[i] = [b, a]
print(DP[-1][0])

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
A=list(map(int,input().split()))
num=[0,2,5,5,4,5,6,3,7,6]
dp=[0]
keta=[0]
tmp=0
tmp1=0
tmp_keta=-1
tmp1_keta=-1
for i in range(1,N+1):
    tmp=-1
    tmp_keta=-1
    for j in A:
        tmp1=-1
        tmp1_keta=-1
        if(i-num[j]>=0):
            if(dp[i-num[j]]>0):
                tmp1=dp[i-num[j]]+j*(10**keta[i-num[j]])
                tmp1_keta=keta[i-num[j]]+1
            elif(dp[i-num[j]]==0):
                tmp1=j
                tmp1_keta=1
            if(tmp1>tmp):
                tmp=tmp1
                tmp_keta=tmp1_keta
    dp.append(tmp)
    keta.append(tmp_keta)
ans=dp[N]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

N,M=map(int,input().split())
A=list(map(int,input().split()))
A.sort(reverse=True)
num=[0,2,5,5,4,5,6,3,7,6]
dp=[0]
keta=[0]
tmp=0
tmp1=0
tmp_keta=-1
tmp1_keta=-1
for i in range(1,N+1):
    tmp=-1
    tmp_keta=-1
    for j in A:
        tmp1=-1
        tmp1_keta=-1
        if(i-num[j]>=0):
            if(dp[i-num[j]]>0):
                tmp1=dp[i-num[j]]+j*(10**keta[i-num[j]])
                tmp1_keta=keta[i-num[j]]+1
            elif(dp[i-num[j]]==0):
                tmp1=j
                tmp1_keta=1
            if(tmp1>tmp):
                tmp=tmp1
                tmp_keta=tmp1_keta
    dp.append(tmp)
    keta.append(tmp_keta)
ans=dp[N]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
A = [int(x) - 1 for x in input().split()]
match = [2, 5, 5, 4, 5, 6, 3, 7, 6]
for a in range(9):
  if a not in A:
    match[a] = N + 1
match.reverse()
L = [[m, 9 - i] for i, m in enumerate(match) if m <= N]
DP = [[0, []] for i in range(N + 1)]
def insert(S, m):
  l, r = 0, len(S)
  if m >= S[0]:
    return 0
  if S[-1] > m:
    return r
  while r - l > 1:
    mid = (l + r) // 2
    if S[mid] > m:
      l = mid
    else:
      r = mid
  return r
for i in range(1, N + 1):
  for m, l in L:
    if i == m and DP[i][0] == 0:
        DP[i] = [l, [str(l)]]
    elif i > m and DP[i - m][0]:
      r = insert(DP[i - m][1], str(l))
      a = DP[i - m][1][:r] + [str(l)] + DP[i - m][1][r:]
      b = int(''.join(a))
      if b > DP[i][0]:
        DP[i] = [b, a]
print(DP[-1][0])

Submission status: Time Limit Exceeded

Solution code:
#!/mnt/c/Users/moiki/bash/env/bin/python
from itertools import permutations
N,M = map(int, input().split())
cost = [0,2,5,5,4,5,6,3,7,6]
A = list(map(int, input().split()))

p = []
for a in A:
    p.append( (cost[a], a) )
costp = sorted(p)


costX = [ z[0] for z in costp]
A = [ z[1] for z in costp]

dp = [""] * (N+1)

for c,a in zip(costX,A):
    i = N 
    if i-c >= 0:
        dp[i-c] = str(a)



for i in range(N-1, 1, -1):
    if len(dp[i]) == 0:
        continue
    
    for c,a in zip(costX,A):
        for p in permutations( [dp[i], str(a)]):
            if i-c >= 0:
                if dp[i-c] == "":
                    dp[i-c] = str(int( "".join(p)))
                else:
                    dp[i-c] = str(max(int(dp[i-c]), int( "".join(p))))
    
print(dp[0])

Submission status: Time Limit Exceeded

Solution code:
def sol(inp=input):
    n,_=map(int,inp().split())
    adms=[c for c in inp() if c!=' ']
    matchnums={'{}'.format(i+1):[2,5,5,4,5,6,3,7,6][i] for i in range(9)}

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

    for i in range(n):
        for a in adms:
            if i+matchnums[a]>=len(dp) or (i>0 and dp[i]==''):
                continue
            dp[i+matchnums[a]]=str(max(int(x) for x in (dp[i+matchnums[a]],a+dp[i],dp[i]+a) if x!=''))
    return dp[-1]
print(sol())

Submission status: Time Limit Exceeded

Solution code:
# coding=utf-8

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


def remove_chou(number_l, match_l):
    if len(match_l) == len(set(match_l)):
        return number_l, match_l
    for i in range(len(match_l)):
        for j in range(i+1, len(match_l)):
            if match_l[i] == match_l[j]:
                if number_l[i] > number_l[j]:
                    number_l.pop(j)
                    match_l.pop(j)
                else:
                    number_l.pop(i)
                    match_l.pop(i)
                return remove_chou(number_l, match_l)


def join_max_number(list_list):
    if len(list_list) == 1:
        return list_list[0]
    list_list2 = [sorted(_list, reverse=True) for _list in list_list]
    #print(list_list2)
    list_list3 = [int("".join(map(str, _list))) for _list in list_list2]
    #print(list_list3)
    max_number = max(list_list3)
    #print(list_list[list_list3.index(max_number)])
    return list_list[list_list3.index(max_number)]


if __name__ == '__main__':
    N, M = map(int, input().split())
    usable_numbers = list(map(int, input().split()))
    usable_numbers.sort()
    usable_matches = [match_list[num-1] for num in usable_numbers]
    #print(usable_numbers, usable_matches)

    usable_numbers2, usable_matches2 = remove_chou(usable_numbers, usable_matches)

    #print(usable_numbers2, usable_matches2)

    min_match = min(usable_matches2)

    matches = [0, -1]
    for i in range(2, N+1):
        if i - min_match < 0:
            matches.append(-1)
        else:
            candidate = []
            for _number in usable_matches2:
                if i - _number < 0:
                    pass
                elif i - _number == 0:
                    candidate.append([usable_numbers2[usable_matches2.index(_number)]])
                else:
                    if matches[i-_number] == -1:
                        pass
                    else:
                        cand = matches[i-_number][:]
                        cand.append(usable_numbers2[usable_matches2.index(_number)])
                        candidate.append(cand)
            #print(i, candidate)
            if candidate == []:
                matches.append(-1)
            else:
                winner = join_max_number(candidate)
                matches.append(winner)
    #print()
    #print(matches[-1])
    print("".join(map(str, matches[-1])))

"""
    remove_index = []
    for i in range(len(usable_matches)):
        for j in range(i+1, len(usable_matches)-i):
            if usable_matches[i] == usable_matches[j]:
                if usable_numbers[i] > usable_numbers[j]:
                    remove_index.append(j)
                else:
                    remove_index.append(i)
    print(remove_index)
    for _index in remove_index:
"""

Submission status: Time Limit Exceeded

Solution code:
#!/mnt/c/Users/moiki/bash/env/bin/python
from itertools import permutations
N,M = map(int, input().split())
cost = [0,2,5,5,4,5,6,3,7,6]
A = list(map(int, input().split()))

p = []
for a in A:
    p.append( (cost[a], a) )
costp = sorted(p)


costX = [ z[0] for z in costp]
A = [ z[1] for z in costp]

dp = [""] * (N+1)

for c,a in zip(costX,A):
    i = N 
    if i-c >= 0:
        dp[i-c] = str(a)

for i in range(N-1, 1, -1):
    if len(dp[i]) == 0:
        continue
    
    for c,a in zip(costX,A):
        for p in permutations( [dp[i], str(a)]):

            if i-c >= 0:
                if dp[i-c] == "":
                    dp[i-c] = str(int( "".join(p)))
                else:
                    dp[i-c] = str(max(int(dp[i-c]), int( "".join(p))))
    
print(dp[0])

Submission status: Time Limit Exceeded

Solution code:
s = list(map(int, input().split()))
t = list(map(int, input().split()))


num=[2,5,5,4,5,6,3,7,6]
aru=[0,0,0,0,0,0,0,0,0,0]
n=s[0]


lista=[]
minm=[8,7]
minflag=0;
for i in range(len(t)):
    if(t[i]==1):
        lista.append([1,2])
        aru[1]=1
        if(minflag==0):
            minm=[1,2]
            minflag=1
for i in range(len(t)):
    if(t[i]==7):
        lista.append([7,3])
        aru[7]=1
        if(minflag==0):
            minm=[7,3]
            minflag=1
        
for i in range(len(t)):
    if(t[i]==4):
        lista.append([4,4])
        aru[4]=1
        if(minflag==0):
            minm=[4,4]
            minflag=1
        
flag=[0,0,0]
for i in range(len(t)):
    if(t[i]==5):
        flag[0]=1
        aru[5]=1
    if(t[i]==3):
        flag[1]=1
        aru[3]=1
    if(t[i]==2):
        flag[2]=1
        aru[2]=1
if(flag[0]==1):
    lista.append([5,5])
    if(minflag==0):
        minm=[5,5]
        minflag=1
elif(flag[1]==1):
    lista.append([3,5])
    if(minflag==0):
        minm=[3,5]
        minflag=1
elif(flag[1]==1):
    lista.append([2,5])
    if(minflag==0):
        minm=[2,5]
        minflag=1

flag=[0,0]
for i in range(len(t)):
    if(t[i]==9):
        flag[0]=1
        aru[9]=1
    if(t[i]==6):
        flag[1]=1
        aru[6]=1
if(flag[0]==1):
    lista.append([9,6])
    if(minflag==0):
        minm=[9,6]
        minflag=1
elif(flag[1]==1):
    lista.append([6,6])
    if(minflag==0):
        minm=[6,6]
        minflag=1

for i in range(len(t)):
    if(t[i]==8):
        aru[8]=1
        lista.append([8,7])
        
      

nn=n
d=0

while(nn>=minm[1]):
    nn-=minm[1]
    d+=1

sch=minm[1]
saigo=minm[0]
if(nn==0):
    ans=""
    for i in range(d):
        ans+=str(minm[0])
    print(ans)
else:
    saigo=0
    while(True):
        flag=0
        if(nn==3 and aru[7]==1):
            saigo=7
            flag=1
        elif(nn==4 and aru[4]==1):
            saigo=4
            flag=1
        elif(nn==5):
            if(aru[5]==1):
                saigo=5
                flag=1
            elif(aru[3]==1):
                saigo=3
                flag=1
            elif(aru[2]==1):
                saigo=2
                flag=1
        elif(nn==6):
            if(aru[9]==1):
                saigo=9
                flag=1
            elif(aru[6]==1):
                saigo=6
                flag=1
        elif(nn==7 and aru[7]==1):
            saigo=7
            flag=1
        if(flag==1):
            break
        nn+=minm[1]
        d-=1
    
    ans=""
    if(minm[0]>saigo):
        for i in range(d):
            ans+=str(minm[0])
        ans+=str(saigo)
    else:
        ans+=str(saigo)
        for i in range(d):
            ans+=str(minm[0])
    print(ans)



##a

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
a = list(map(int, input().split()))
use = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [[0] * 10 for i in range(n+1)]
for i in range(1,n+1):
    kouho = []
    for j in a:
        if i - use[j] >= 0:
            if dp[i-use[j]] == [0] * 10 and i - use[j] != 0: # マッチの数が合わない場合
                continue #何もしない
            else:
                copy = dp[i-use[j]][:]
                copy[j] += 1
                kouho.append(copy)
    if kouho == []: #空の場合
        continue #何もしない
    else:
        usearray = []
        accnum = "0"
        for array in kouho:
            tmpnum = ""
            for k in range(9,0,-1):
                tmpnum += (str(k) * array[k])
            if int(tmpnum) > int(accnum):
                usearray = array
                accnum = tmpnum
        dp[i] = usearray
ans = ""
for i in range(9,0,-1):
    ans += (str(i) * dp[n][i])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
a.reverse() # aを大きい順にソート
use = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [[0] * 10 for i in range(n+1)]
for i in range(1,n+1):
    kouho = []
    for j in a:
        if i - use[j] >= 0:
            if dp[i-use[j]] == [0] * 10 and i - use[j] != 0: # マッチの数が合わない場合
                continue #何もしない
            else:
                copy = dp[i-use[j]][:]
                copy[j] += 1
                kouho.append(copy)
    if kouho == []: #空の場合
        continue #何もしない
    else:
        usearray = []
        accnum = "0"
        for array in kouho:
            tmpnum = ""
            for k in range(9,0,-1):
                tmpnum += (str(k) * array[k])
            if int(tmpnum) > int(accnum):
                usearray = array
                accnum = tmpnum
        dp[i] = usearray
ans = ""
for i in range(9,0,-1):
    ans += (str(i) * dp[n][i])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
A=list(map(int,input().split()))
num=[0,2,5,5,4,5,6,3,7,6]
dp=[[1,0,0,0,0,0,0,0,0,0]]
tmp=0
tmp1=0
tmp2=0
for i in range(0,N+1):
    dp.append([0,0,0,0,0,0,0,0,0,0])
    tmp=0
    for j in A:
        if(i-num[j]>=0):
            tmp1=dp[i-num[j]].copy()
            #存在しないなら不可
            if(tmp1[0]==0):
                continue
            tmp1[j]+=1
            tmp2=int("9"*tmp1[9]+"8"*tmp1[8]+"7"*tmp1[7]+"6"*tmp1[6]+"5"*tmp1[5]+"4"*tmp1[4]+"3"*tmp1[3]+"2"*tmp1[2]+"1"*tmp1[1])
            if(tmp2>tmp):
                tmp=tmp2
                dp[i]=tmp1
ans=0
for k in range(1,10):
    if(dp[N][10-k]!=0):
        ans*=10**dp[N][10-k]
        ans+=(10-k)*int("1"*dp[N][10-k])
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
import itertools
import numpy as np

(n, _) = map(int, input().split())
a = sorted(list(map(int, input().split())))
match = [2,5,5,4,5,6,3,7,6]
l = [j for i, j in zip(range(1, 10), match) if i in a]
mm = {j: i for i, j in zip(a, l)}
sorted(mm.items(), key=lambda x: x[1], reverse=True)
b = [i for i in itertools.combinations_with_replacement(l+[0], n//min(a)) if sum(i) == n]
m = max([np.count_nonzero(i) for i in b])
c = [i for i in b if np.count_nonzero(i) == m]
d = [sorted([mm[j] for j in i if j != 0], reverse=True) for i in c]
print(max([int("".join(map(str, i))) for i in d]))

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
A=list(map(int,input().split()))
num=[0,2,5,5,4,5,6,3,7,6]
dp=[[1,0,0,0,0,0,0,0,0,0]]
tmp=0
tmp1=0
tmp2=0
for i in range(0,N+1):
    dp.append([0,0,0,0,0,0,0,0,0,0])
    tmp=0
    for j in A:
        if(i-num[j]>=0):
            tmp1=dp[i-num[j]].copy()
            #存在しないなら不可
            if(tmp1[0]==0):
                continue
            tmp1[j]+=1
            tmp2=0
            tmp2=int("9"*tmp1[9]+"8"*tmp1[8]+"7"*tmp1[7]+"6"*tmp1[6]+"5"*tmp1[5]+"4"*tmp1[4]+"3"*tmp1[3]+"2"*tmp1[2]+"1"*tmp1[1])
            if(tmp2>tmp):
                tmp=tmp2
                dp[i]=tmp1
ans=0
for k in range(1,10):
    if(dp[N][10-k]!=0):
        ans*=10**dp[N][10-k]
        ans+=(10-k)*int("1"*dp[N][10-k])
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
A=list(map(int,input().split()))
num=[0,2,5,5,4,5,6,3,7,6]
dp=[[1,0,0,0,0,0,0,0,0,0]]
tmp=0
tmp1=0
tmp2=0
for i in range(0,N+1):
    dp.append([0,0,0,0,0,0,0,0,0,0])
    tmp=0
    for j in A:
        if(i-num[j]>=0):
            tmp1=dp[i-num[j]].copy()
            #存在しないなら不可
            if(tmp1[0]==0):
                continue
            tmp1[j]+=1
            tmp2=0
            for k in range(1,10):
                if(tmp1[10-k]!=0):
                    tmp2*=(10**tmp1[10-k])
                    tmp2+=(10-k)*int("1"*tmp1[10-k])
            tmp2=int("9"*tmp1[9]+"8"*tmp1[8]+"7"*tmp1[7]+"6"*tmp1[6]+"5"*tmp1[5]+"4"*tmp1[4]+"3"*tmp1[3]+"2"*tmp1[2]+"1"*tmp1[1])
            if(tmp2>tmp):
                tmp=tmp2
                dp[i]=tmp1
ans=0
for k in range(1,10):
    if(dp[N][10-k]!=0):
        ans*=10**dp[N][10-k]
        ans+=(10-k)*int("1"*dp[N][10-k])
print(int(ans))

Submission status: Time Limit Exceeded

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

items = {
    1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6
}
dp = [0] * (N + 1)

b_list = []
for a in a_list:
    need = items[a]
    if need <= N:
        dp[need] = a
        b_list.append(a)

M = len(b_list)
b_list.sort()
for i in range(N + 1):
    for b in b_list:
        if i - items[b] >= 0:
            if dp[i - items[b]] != 0:
                if int(str(dp[i - items[b]])[0]) < b:
                    cnt = 0
                    num = dp[i - items[b]]
                    while num != 0:
                        cnt += 1
                        num //= 10
                    tmp = max(b * (10 ** cnt) + dp[i - items[b]], dp[i - items[b]] * 10 + b)
                    dp[i] = max(tmp, dp[i])
                else:
                    dp[i] = max(dp[i], dp[i - items[b]] * 10 + b)


print(dp[N])

Submission status: Time Limit Exceeded

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

count_table = [None, 2,5,5,4,5,6,3,7,6]

dp = [None for _ in range(n + 1)]
dp[0] = {0: 0}

for i in range(m):
    my_value = values[i]
    for j in range(n):
        dic = dp[j]
        if dic is not None and len(dic) > 0:
            my_count = 1
            while j + count_table[my_value] * my_count <= n:
                already = dp[j + count_table[my_value] * my_count] or {}
                new_dic = {k: v for k, v in dic.items()}
                new_dic[my_value] = my_count

                s = ''
                for value, cnt in reversed(sorted(already.items())):
                    s += str(value) * cnt
                s_already = s
                s = ''
                for value, cnt in reversed(sorted(new_dic.items())):
                    s += str(value) * cnt

                if s_already == '':
                    dp[j + count_table[my_value] * my_count] = new_dic
                elif s == '':
                    pass
                elif int(s_already) < int(s):
                    dp[j + count_table[my_value] * my_count] = new_dic

                my_count += 1

pin_dic = dp[n]

s = ''
for value, cnt in reversed(sorted(pin_dic.items())):
    s += str(value) * cnt
print(s)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
A = [int(x) - 1 for x in input().split()]
match = [2, 5, 5, 4, 5, 6, 3, 7, 6]
for a in range(9):
  if a not in A:
    match[a] = N + 1
match.reverse()
L = [[m, 9 - i] for i, m in enumerate(match)]
DP = [[0, []] for i in range(N + 1)]
for i in range(1, N + 1):
  for m, l in L:
    if i == m:
      if DP[i][0] == 0:
        DP[i] = [l, [str(l)]]
    if i > m and DP[i - m][0]:
      a = DP[i - m][1] + [str(l)]
      b = int(''.join(sorted(a, reverse=True)))
      if b > DP[i][0]:
        DP[i] = [b, a]
print(DP[-1][0])

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
A=list(map(int,input().split()))
num=[0,2,5,5,4,5,6,3,7,6]
dp=[[1,0,0,0,0,0,0,0,0,0]]
tmp=0
tmp1=0
tmp2=0
for i in range(0,N+1):
    dp.append([0,0,0,0,0,0,0,0,0,0])
    tmp=0
    for j in A:
        if(i-num[j]>=0):
            tmp1=dp[i-num[j]].copy()
            #存在しないなら不可
            if(tmp1[0]==0):
                continue
            tmp1[j]+=1
            tmp2=0
            for k in range(1,10):
                if(tmp1[10-k]!=0):
                    tmp2*=(10**tmp1[10-k])
                    tmp2+=(10-k)*int("1"*tmp1[10-k])
            if(tmp2>tmp):
                tmp=tmp2
                dp[i]=tmp1
ans=0
for k in range(1,10):
    if(dp[N][10-k]!=0):
        ans*=10**dp[N][10-k]
        ans+=(10-k)*int("1"*dp[N][10-k])
print(int(ans))

Submission status: Time Limit Exceeded

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

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

C = []
A = sorted(A)
for a in A:
  C.append(cost_define[a-1])

#まず最小コストで桁を決定
min_cost = 7
min_cost_index = 0
for i in range(len(C)):
  #あと勝ち
  if (C[i] <= min_cost):
    min_cost_index = i
    min_cost = C[i]
min_cost_number = A[min_cost_index]
keta = N // min_cost
amari = (N - (keta*min_cost))
#print(min_cost, min_cost_number, keta, amari)

#余ったら最大桁から増やしていく
res = 0
while (0 < keta):
  if (0 < amari):
    found = False
    for (c,a) in zip(reversed(C),reversed(A)):
      #print(c,a,amari)
      c -= min_cost
      if (c <= amari):
        amari -= c
        res += (a * 10**(keta-1))
        found = True
        break
    if not found:
      res += (min_cost_number * 10**(keta-1))
  else:
    res += (min_cost_number * 10**(keta-1))
  keta -= 1
  #print(keta, res)

#まだ余っていたら最下位から数を減らしてでも本数を使い切る
while (0 < amari):
  tmp_c = 0
  tmp_a = 0
  for (c,a) in zip(C,A):
    c -= min_cost
    if (c <= amari):
      #あと勝ち
      if (tmp_c <= c):
      	tmp_c = c
      	tmp_a = a
  amari -= tmp_c
  #print(amari,tmp_c)
  #print(res, res[-(keta+1)], str(tmp_a))
  #res[-(keta+1)] = str(a)[0]
  res -= (min_cost_number * 10**(keta))
  res += (tmp_a * 10**(keta))
  keta += 1

print(str(res))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
def  inpl(): return list(map(int, input().split()))
N, M = inpl()
A = sorted(inpl())
cost = [1e9, 2, 5, 5, 4, 5, 6, 3, 7, 6]
mincost = min([cost[a] for a in A])
maxcost = max([cost[a] for a in A])

DP = [0]*N
for a in A:
    if N - cost[a] >= 0:
        DP[N-cost[a]] = a

ans = DP[0]
for j in range(N//2 + 1):
    DP2 = [0]*N
    ok = False
    for i in range(max(0, N-maxcost*(j+1)), N-mincost*j):
        v = DP[i]
        if v == 0:
            continue
        for a in A:
            nk = i - cost[a]
            if nk >= 0:
                ok = True
                DP2[nk] = max(DP2[nk], 10*v + a)
    ans = max(ans, DP2[0])
    DP = DP2
    if ok == False:
        break

print(ans)

Submission status: Time Limit Exceeded

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

items = {
    1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6
}
dp = [0] * (N + 1)

b_list = []
for a in a_list:
    need = items[a]
    if need <= N:
        dp[need] = a
        b_list.append(a)

M = len(b_list)
b_list.sort()
for i in range(N + 1):
    for b in b_list:
        if i - items[b] >= 0:
            if dp[i - items[b]] != 0:
                cnt = 0
                num = dp[i - items[b]]
                while num != 0:
                    cnt += 1
                    num //= 10
                tmp = max(b * (10 ** cnt) + dp[i - items[b]], dp[i - items[b]] * 10 + b)
                dp[i] = max(tmp, dp[i])
print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
A=list(map(int,input().split()))
num=[0,2,5,5,4,5,6,3,7,6]
dp=[[1,0,0,0,0,0,0,0,0,0]]
tmp=0
tmp1=0
tmp2=0
for i in range(0,N+1):
    dp.append([0,0,0,0,0,0,0,0,0,0])
    tmp=0
    for j in A:
        if(i-num[j]>=0):
            tmp1=dp[i-num[j]].copy()
            #存在しないなら不可
            if(tmp1[0]==0):
                continue
            tmp1[j]+=1
            tmp2=0
            for k in range(1,10):
                if(tmp1[10-k]!=0):
                    tmp2*=(10**tmp1[10-k])
                    tmp2+=(10-k)*int("1"*tmp1[10-k])
            if(tmp2>tmp):
                tmp=tmp2
                dp[i]=tmp1
ans=0
for k in range(1,10):
    if(dp[N][10-k]!=0):
        ans*=10**dp[N][10-k]
        ans+=(10-k)*int("1"*dp[N][10-k])
print(int(ans))

Submission status: Time Limit Exceeded

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

items = {
    1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6
}
dp = [0] * (N + 1)

b_list = []
for a in a_list:
    need = items[a]
    if need <= N:
        dp[need] = a
        b_list.append(a)

M = len(b_list)
b_list.sort()
for i in range(N + 1):
    for b in b_list:
        if i - items[b] >= 0:
            if dp[i - items[b]] != 0:
                cnt = 0
                num = dp[i - items[b]]
                while num >= 1:
                    cnt += 1
                    num //= 10
                tmp = max(b * (10 ** cnt) + dp[i - items[b]], dp[i - items[b]] * 10 + b)
                dp[i] = max(tmp, dp[i])
print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
n, m = list(map(int, input().split()))
li = list(map(int, input().split()))
di = {}
for i, d in enumerate([2,5,5,4,5,6,3,7,6], 1):
    di[i] = d

# honsuu list
ns = set()
# honsuu-> disit list
n2d = {}
for a in li:
    hon = di[a]
    ns.add(hon)
    if (hon not in n2d) or (n2d[hon] < a):
        n2d[hon] = a
ns = list(ns)
ns.sort(reverse=True)

from collections import Counter, deque
cnt = Counter()
Q = deque()
for hon in ns:
    if n - hon >= 0:
        Q.append(((hon,), n - hon))
ma = 0
mali = []
while len(Q) > 0:
    lis, remain = Q.pop()
    if remain == 0 and len(lis) > ma:
        ma = len(lis)
        mali = lis
    for hon in ns:
        if remain - hon >= 0:
            Q.append((lis + (hon,), remain - hon))

digits = [n2d[n] for n in mali]
digits.sort(reverse=True)

print(*digits, sep='')

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
def  inpl(): return list(map(int, input().split()))
N, M = inpl()
A = sorted(inpl())
cost = [1e9, 2, 5, 5, 4, 5, 6, 3, 7, 6]
mincost = min([cost[a] for a in A])
maxcost = max([cost[a] for a in A])

DP = [0]*N
for a in A:
    if N - cost[a] >= 0:
        DP[N-cost[a]] = a

ans = DP[0]
for j in range(N//2 + 1):
    DP2 = [0]*N
    for i in range(max(0, N-maxcost*(j+1)), N-mincost*j):
        v = DP[i]
        if v == 0:
            continue
        for a in A:
            nk = i - cost[a]
            if nk >= 0:
                DP2[nk] = max(DP2[nk], 10*v + a)
    ans = max(ans, DP2[0])
    DP = DP2

print(ans)

Submission status: Time Limit Exceeded

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

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

C = []
A = sorted(A)
for a in A:
  C.append(cost_define[a-1])

#まず最小コストで桁を決定
min_cost = 7
min_cost_index = 0
for i in range(len(C)):
  #あと勝ち
  if (C[i] <= min_cost):
    min_cost_index = i
    min_cost = C[i]
min_cost_number = A[min_cost_index]
keta = N // min_cost
amari = (N - (keta*min_cost))
#print(min_cost, min_cost_number, keta, amari)

#余ったら最大桁から増やしていく
res = ""
while (0 < keta):
  if (0 < amari):
    found = False
    for (c,a) in zip(reversed(C),reversed(A)):
      #print(c,a,amari)
      c -= min_cost
      if (c <= amari):
        amari -= c
        res += str(a)
        found = True
        break
    if not found:
      res += str(min_cost_number)
  else:
    res += str(min_cost_number)
  keta -= 1
  #print(keta, res)

#まだ余っていたら最下位から数を減らしてでも本数を使い切る
while (0 < amari):
  tmp_c = 0
  tmp_a = 0
  for (c,a) in zip(C,A):
    c -= min_cost
    if (c <= amari):
      #あと勝ち
      if (tmp_c <= c):
      	tmp_c = c
      	tmp_a = a
  amari -= tmp_c
  #print(amari,tmp_c)
  #print(res, res[-(keta+1)], str(tmp_a))
  #res[-(keta+1)] = str(a)[0]
  new_res = res[:-(keta+1)] + str(tmp_a)
  if (0 < keta):
    new_res += res[-(keta):]
  res = new_res
  keta += 1

print(res)

Submission status: Time Limit Exceeded

Solution code:
N , M = map(int,input().split())
L = sorted(list(map(int,input().split())))
table =  [0,2,5,5,4,5,6,3,7,6]
L_val =sorted( list(map(lambda x:(table[x],x),L)))
number = ["0" for i in range(10**4+10)]

def comp(x,y):
    if len(x) >len(y):
        return 0
    elif len(x) < len(y):
        return 1
    else:
        for i in range(len(x)):
            if x[i] == y[i]:
                i+=1
            elif int(x[i]) < int(y[i]):
                return 1
            elif int(x[i]) > int(y[i]):
                return 0
        return 0



for x in L_val:
    number[x[0]] = str(x[1])

for i in range(10**4):
    tmp = number[i]
    if tmp=="0":
        continue
    for x in L_val:
        if  comp(number[i+x[0]],tmp + str(x[1])):
            number[i+x[0]] = tmp + str(x[1])

print(number[N])