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







def nCast(number):
    if type(number)==str:
        return int(number)
    for idx in range(0,len(number)):
        if type(number[idx])==str:

            number[idx]=int(number[idx])
        else:
            nCast(number[idx])
    return number
    
def inputArr(w):
    l=list()
    for idx in range(0,w):
        l.append(input())
    return l
def inputArr1(w):
    l=list()
    for idx in range(0,w):
        l.append(input().split())
    return l

n=nCast(input().split())
m=nCast(input().split())

def cmp(l1,l2):

    if len(l1)!=len(l2):
        return len(l1)-len(l2)
    for idx in range(0,len(l1)):
        if l1[idx]!=l2[idx]:
            return l1[idx]-l2[idx]
    return 0
def func():
    l=list()
    nn=[1,2,3,4,5,6,7,8,9]
    s=set(m)
    mm=[2,5,5,4,5,6,3,7,6]
    d=dict()
    for idx in nn:
        if idx in s:
            if idx==2 and 5 in s:
                continue
            if idx==3 and 5 in s:
                continue
            if idx==2 and 3 in s:
                continue
            if idx==6 and 9 in s:
                continue
            d[nn[idx-1]]=mm[idx-1]
    for idx in range(0,n[0]+1):
        l.append(list())
    for idx in range(1,n[0]+1):
        for idy in d:
            if idx-d[idy]>0:
                tmp=l[idx-d[idy]][:]
                if len(tmp)==0:
                    continue
                tmp.append(idy)
                #tmp.sort(reverse=True)
                if cmp(tmp,l[idx])>0:
                    l[idx]=tmp
            elif idx-d[idy]==0:
                max=0
                for dd in d:
                    if d[dd]==idx and dd>max:
                        max=dd
                if cmp([max],l[idx])>0:
                    l[idx]=[max]

    result=""
    l[-1].sort(reverse=True)
    for idx in range(0,len(l[-1])):
        result=result+str(l[-1][idx])
    return result



print(func())

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]

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(N):
        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_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:
                tmp = max(b * (10 ** len(str(dp[i - items[b]]))) + 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:
M = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]

max_vs = [''] * 10001
n, m = [int(v) for v in input().split()]
a = [int(v) for v in input().split()]
for i in range(1, n + 1):
        for v in a:
                if M[v] > i:
                        continue
                elif M[v] == i:
                        if max_vs[i] == '' or int(max_vs[i]) < v:
                                max_vs[i] = str(v)
                else:
                        if max_vs[i - M[v]] != '':
                                if max_vs[i] == '' or int(max_vs[i]) < int(str(v) + max_vs[i - M[v]]):
                                        max_vs[i] = str(v) + max_vs[i - M[v]]
print(max_vs[n])

Submission status: Time Limit Exceeded

Solution code:
import math
import copy
import bisect







def nCast(number):
    if type(number)==str:
        return int(number)
    for idx in range(0,len(number)):
        if type(number[idx])==str:

            number[idx]=int(number[idx])
        else:
            nCast(number[idx])
    return number
    
def inputArr(w):
    l=list()
    for idx in range(0,w):
        l.append(input())
    return l
def inputArr1(w):
    l=list()
    for idx in range(0,w):
        l.append(input().split())
    return l

n=nCast(input().split())
m=nCast(input().split())

def cmp(l1,l2):

    if len(l1)!=len(l2):
        return len(l1)-len(l2)
    for idx in range(0,len(l1)):
        if l1[idx]!=l2[idx]:
            return l1[idx]-l2[idx]
    return 0
def func():
    l=list()
    nn=[1,2,3,4,5,6,7,8,9]
    s=set(m)
    mm=[2,5,5,4,5,6,3,7,6]
    d=dict()
    for idx in nn:
        if idx in s:
            if idx==2 and 5 in s:
                continue
            if idx==3 and 5 in s:
                continue
            if idx==2 and 3 in s:
                continue
            if idx==6 and 9 in s:
                continue
            d[nn[idx-1]]=mm[idx-1]
    for idx in range(0,n[0]+1):
        l.append(list())
    for idx in range(1,n[0]+1):
        for idy in d:
            if idx-d[idy]==0:
                max=0
                for dd in d:
                    if d[dd]==idx and dd>max:
                        max=dd
                if cmp([max],l[idx])>0:
                    l[idx]=[max]
            if idx-d[idy]>0:
                tmp=l[idx-d[idy]][:]
                if len(tmp)==0:
                    continue
                tmp.append(idy)
                #tmp.sort(reverse=True)
                if cmp(tmp,l[idx])>0:
                    l[idx]=tmp

    result=""
    l[-1].sort(reverse=True)
    for idx in range(0,len(l[-1])):
        result=result+str(l[-1][idx])
    return result



print(func())

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)))
#print(L_val)
number = ["0" for i in range(10**4+10)]
for x in L_val:
    number[x[0]] = str(x[1])

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

print(number[N])

Submission status: Time Limit Exceeded

Solution code:
#coding:utf-8
N,M  = map(int,input().split())
A = list(map(int,input().split()))
b = 0
c = [0,2,5,5,4,5,6,3,7,6]
bagS = [[] for i in range(N+1)]
def check(A,B):#A:prev,B:temp
    As = list(map(str,sorted(A,reverse=True)))
    p = int("".join(As)) if len(A) else 0

    B.sort(reverse=True)
    Bs = list(map(str,B))
    
    t = int("".join(Bs)) if len(B) else 0
    if t > p:
        return B
    else :
        return A
def check2(A,B):
    p = 0
    t = 0
    for a in A:
        p = p*10+a
    for b in B:
        t = t*10+b
    if t > p:
        return B

    else:
        return A

while b != N:

    for a in A:
        if b+ c[a] <= N:
  
            bagS[b+c[a]] = check2(bagS[b+c[a]],bagS[b]+[a])

    for i in range(b+1,N+1):
        if bagS[i]:
            b = i
            break
print("".join(list(map(str,bagS[N]))))

Submission status: Time Limit Exceeded

Solution code:
M = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]

max_vs = [0] * 10001
n, m = [int(v) for v in input().split()]
a = [int(v) for v in input().split()]
for i in range(1, n + 1):
        for v in a:
                if M[v] > i:
                        continue
                elif M[v] == i:
                        max_vs[i] = max(max_vs[i], v)
                else:
                        if max_vs[i - M[v]] > 0:
                                max_vs[i] = max(max_vs[i], int(str(v) + str(max_vs[i - M[v]])))
print(max_vs[n])

Submission status: Time Limit Exceeded

Solution code:
import math
import copy
import bisect







def nCast(number):
    if type(number)==str:
        return int(number)
    for idx in range(0,len(number)):
        if type(number[idx])==str:

            number[idx]=int(number[idx])
        else:
            nCast(number[idx])
    return number
    
def inputArr(w):
    l=list()
    for idx in range(0,w):
        l.append(input())
    return l
def inputArr1(w):
    l=list()
    for idx in range(0,w):
        l.append(input().split())
    return l

n=nCast(input().split())
m=nCast(input().split())

def cmp(l1,l2):

    if len(l1)!=len(l2):
        return len(l1)-len(l2)
    for idx in range(0,len(l1)):
        if l1[idx]!=l2[idx]:
            return l1[idx]-l2[idx]
    return 0
def func():
    l=list()
    nn=[1,2,3,4,5,6,7,8,9]
    s=set(m)
    mm=[2,5,5,4,5,6,3,7,6]
    d=dict()
    for idx in nn:
        if idx in s:
            d[nn[idx-1]]=mm[idx-1]
    for idx in range(0,n[0]+1):
        l.append(list())


    for idx in range(1,n[0]+1):
        for idy in d:
            if idx-d[idy]==0:
                max=0
                for dd in d:
                    if d[dd]==idx and dd>max:
                        max=dd
                if cmp([max],l[idx])>0:
                    l[idx]=[max]
                        
       
            if idx-d[idy]>0:

                tmp=l[idx-d[idy]][:]
            
                if len(tmp)==0:
                    continue
                
                tmp.append(idy)
                #tmp.sort(reverse=True)
                
                if cmp(tmp,l[idx])>0:
                    l[idx]=tmp

    result=""

    for idx in range(0,len(l[-1])):
        result=result+str(l[-1][idx])
    return result

a=7771111111111111111111111111111111111111111111111
b=71111111111111111111111111111111111111111111111111

print(func())

Submission status: Time Limit Exceeded

Solution code:
import math
import copy
import bisect







def nCast(number):
    if type(number)==str:
        return int(number)
    for idx in range(0,len(number)):
        if type(number[idx])==str:

            number[idx]=int(number[idx])
        else:
            nCast(number[idx])
    return number
    
def inputArr(w):
    l=list()
    for idx in range(0,w):
        l.append(input())
    return l
def inputArr1(w):
    l=list()
    for idx in range(0,w):
        l.append(input().split())
    return l

n=nCast(input().split())
m=nCast(input().split())

def cmp(l1,l2):

    if len(l1)!=len(l2):
        return len(l1)-len(l2)
    for idx in range(0,len(l1)):
        if l1[idx]!=l2[idx]:
            return l1[idx]-l2[idx]
    return 0
def func():
    l=list()
    nn=[1,2,3,4,5,6,7,8,9]
    s=set(m)
    mm=[2,5,5,4,5,6,3,7,6]
    d=dict()
    for idx in nn:
        if idx in s:
            d[nn[idx-1]]=mm[idx-1]
    for idx in range(0,n[0]+1):
        l.append(list())


    for idx in range(1,n[0]+1):
        for idy in d:
            if idx-d[idy]==0:
                max=0
                for dd in d:
                    if d[dd]==idx and dd>max:
                        max=dd
                if cmp([max],l[idx])>0:
                    l[idx]=[max]
                        
       
            if idx-d[idy]>0:

                tmp=l[idx-d[idy]][:]
            
                if len(tmp)==0:
                    continue
                tmp.append(idy)
                tmp.sort(reverse=True)
                
                if cmp(tmp,l[idx])>0:
                    l[idx]=tmp

    result=""

    for idx in range(0,len(l[-1])):
        result=result+str(l[-1][idx])
    return result

a=7771111111111111111111111111111111111111111111111
b=71111111111111111111111111111111111111111111111111

print(func())

Submission status: Time Limit Exceeded

Solution code:
#coding:utf-8
N,M  = map(int,input().split())
A = list(map(int,input().split()))
b = 0
c = [0,2,5,5,4,5,6,3,7,6]
bagS = [[] for i in range(N+1)]
def check(A,B):#A:prev,B:temp




    As = list(map(str,sorted(A,reverse=True)))
    p = int("".join(As)) if len(A) else 0

    B.sort(reverse=True)
    Bs = list(map(str,B))
    
    t = int("".join(Bs)) if len(B) else 0
    if t > p:
        return B
    else :
        return A

while b != N:

    for a in A:
        if b+ c[a] <= N:
  
            bagS[b+c[a]] = check(bagS[b+c[a]],bagS[b]+[a])

    for i in range(b+1,N+1):
        if bagS[i]:
            b = i
            break
print("".join(list(map(str,bagS[N]))))

Submission status: Time Limit Exceeded

Solution code:
match_num = [0,2,5,5,4,5,6,3,7,6]

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

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

for i in range(n+1):
    c = []
    for m in match:
        k = match_num[m]
        if i-k >= 0 and dp[i-k] != -1:
            c.append(max(int(str(dp[i-k]) + str(m)), int(str(m) + str(dp[i-k]))))
        if i == k:
            c.append(m)
    if len(c)>0:
        dp[i] = max(c)

print(dp[n])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from collections import defaultdict
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]

DP = defaultdict(int)
DP[N] = 0

ans = 0
for _ in range(N+1):
    DP2 = defaultdict(int)
    for k, v in DP.items():
        for a in A:
            nk = k - cost[a]
            if nk >= 0:
                DP2[nk] = max(DP2[nk], 10*v + a)
    if len(DP2) == 0:
        break
    ans = max(ans, DP2[0])
    DP = DP2

print(ans)

Submission status: Time Limit Exceeded

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

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

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

#dpの初期化
for i in range(m):
    if cost[a[i]] <= n:
        dp[cost[a[i]]]= [a[i]]


for i in range(0,n+1):
    for k in range(m):
        if i > cost[a[k]]:
            #print(cost[a[k]])
            tmp = copy.copy(dp[i-cost[a[k]]])
            tmp.append(a[k])
            tmp.sort(reverse = True)
            #print(i,tmp)
            if len(tmp) > len(dp[i]) and len(tmp) != 1:
                dp[i] = tmp
            elif len(tmp) == len(dp[i]) and len(tmp) != 1:

                num1 = ""
                for cha in dp[i]:
                    num1 = num1 + str(cha)

                num2 = ""
                for cha in tmp:
                    num2 = num2 + str(cha)

                if num2 > num1:
                    dp[i] = tmp
            #print(dp)

ans = ""
for cha in dp[n]:
    ans = ans + str(cha)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def intlog10(n):
    if n <= 0:
        return -1
    i = 0
    while 10**i <= n:
        i += 1
    return i-1

N, M = map(int, input().split())
A = [int(a) for a in input().split()]
L = [2, 5, 5, 4, 5, 6, 3, 7, 6]
B = [[A[i], L[A[i]-1]] for i in range(M)]

best = sorted(B, key = lambda x: x[1]*10-x[0])[0]

# print(best)
X = [0] + [-10**9] * N
bpre = -1
ll = 1
for i in range(1, N+1):
    if i > 50 and i < N-50:
        X[i] = X[i-best[1]]*10 + best[0]
    else:
        for b in B:
            if b[1] <= i:
                if X[i-b[1]] == 0:
                    if b[0] > X[i]:
                        X[i] = b[0]
                        bpre = b
                        ll = 0
                else:
                    if X[i-b[1]]*10 + b[0] < X[i-b[1]] + b[0] * (10**intlog10(X[i-b[1]])):
                        lll = 1

                    if max(X[i-b[1]]*10 + b[0], X[i-b[1]] + b[0] * (10**intlog10(X[i-b[1]]))) > X[i]:
                        X[i] = max(X[i-b[1]]*10 + b[0], X[i-b[1]] + b[0] * (10**intlog10(X[i-b[1]])))
                        ll = lll
                        bpre = b
                
    
print(X[N])

Submission status: Time Limit Exceeded

Solution code:
numbers = {'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(input().split())
cands = [(a, numbers[a]) for a in A]

dp = {i: None for i in range(1, N+1)}
for c in cands:
    dp[c[1]] = int(c[0])
for i in range(2, N+1):
    for c in cands:
        j = i - c[1]
        if j >= 1 and dp[j] is not None:
            if dp[i] is None:
                dp[i] = int(''.join(sorted(str(dp[j]) + c[0], reverse=True)))
            else:
                dp[i] = max(dp[i], int(''.join(sorted(str(dp[j]) + c[0], reverse=True))))
print(dp[N])

Submission status: Time Limit Exceeded

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

MAX_N = int(1e4)
dp = [[-1 for i in range(10)] for i in range(MAX_N + 10)]
for j in range(1, 9 + 1):
    dp[0][j] = 0

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

for i in range(N + 1):
    for j in range(1, 9 + 1):
        if j not in A:
            continue

        if i < mc[j - 1]:
            continue

        for k in range(1, j + 1):
            tmp = dp[i - mc[j - 1]][k]
            if tmp == -1:
                continue
            if tmp == 0:
                tmp = ""
            tmp = str(tmp)
            dp[i][j] = max(dp[i][j], int(tmp + str(j)), int(str(j) + tmp))


ans = 0
for j in range(1, 9 + 1):
    ans = max(ans, dp[N][j])
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=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(map(int, input().split()))
use = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
usecase = [use[i] for i in a]

dp = [""] * (n+1)
for i in range(1,n+1):
    kouho = []
    for j in a:
        if i - use[j] >= 0:
            if dp[i-use[j]] == "" and i - use[j] != 0: # マッチの数が合わない場合
                continue #何もしない
            else:
                for k in range(len(dp[i-use[j]])+1):
                    kouho.append(dp[i-use[j]][:k]+str(j)+dp[i-use[j]][k:])
    if kouho == []: #空の場合
        continue #何もしない
    else:
        dp[i] = str(max(map(int,kouho)))
print(dp[n])

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!

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

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


bar = list(set([table[i] for i in a]))
bar.sort()
minbar=min(bar)

maxnum = [0]*10
for i in bar:
    mbmax = max([j for j in a if table[j] == i])
    maxnum[i]=str(mbmax)
#print(maxnum,bar)
ans = ['0']*(n+10)
for i in range(8):
    if i in bar:
        ans[i]=maxnum[i]
#print(ans)
for i in range(n+1):
    if ans[i] == '0':
        continue
    for j in bar:
        if maxnum[j] > ans[i][0]:
            tmp = maxnum[j]+ans[i]
        else:
            tmp = ans[i]+maxnum[j]
            ans[i+j] = str(max(int(ans[i+j]),int(tmp)))
#    print(ans)

print(ans[n])

Submission status: Time Limit Exceeded

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

dp = ["" for i in range(N+10)]

A = sorted(A, reverse=True)

for num in A:
    c = cost[num]
    if dp[c] == "":
        dp[c] = str(num)
    else:
        dp[c] = str(max(int(dp[c]), num))

for i in range(N+1):
    for num in A:
        c = cost[num]
        prev = dp[i]
        if prev != "":
            if int(prev[0]) > num:
                nxt = prev + str(num)
                nxt_i = int(nxt)
            else:
                nxt = str(num) + prev
                nxt_i = int(nxt)
            if dp[i + c] == "":
                dp[i + c] = nxt
            else:
                dp[i + c] = str(max(int(dp[i + c]), nxt_i))

print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!

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

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


bar = list(set([table[i] for i in a]))
bar.sort()
minbar=min(bar)

maxnum = [0]*10
for i in bar:
    mbmax = max([j for j in a if table[j] == i])
    maxnum[i]=str(mbmax)
#print(maxnum,bar)
ans = ['0']*(n+10)
for i in range(8):
    if i in bar:
        ans[i]=maxnum[i]
#print(ans)
for i in range(n+1):
    if ans[i] == '0':
        continue
    for j in bar:
        if maxnum[j] > ans[i][0]:
            tmp = maxnum[j]+ans[i]
        else:
            tmp = ans[i]+maxnum[j]
            ans[i+j] = str(max(int(ans[i+j]),int(tmp)))
#    print(ans)

print(ans[n])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
n,m=map(int,input().split())
a=sorted(map(int,input().split()),key=lambda x:-x)
qq=[1,2,3,4,5,6,7,8,9]
rr=[2,5,5,4,5,6,3,7,6]
q=[]
r=[]
for i in range(m):
    q.append(qq[a[i]-1])
    r.append(rr[a[i]-1])

memo={}
def ff(n,m):
    if (n,m) in memo:
        return memo[(n,m)]
    global q,r
    if n==0:
        return ''
    s=0
    f=0
    for i in range(m):
        if (n-r[i])>=0:
            tmp=ff(n-r[i],m)
            if tmp!=None:
                s=max(s,int(str(q[i])+tmp))
            else:
                f+=1
        else:
            f+=1
    if f==m:
        return None
    memo[(n,m)]=str(s)
    return memo[(n,m)]
print(ff(n,m))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
n,m=map(int,input().split())
a=sorted(map(int,input().split()),key=lambda x:-x)
qq=[1,2,3,4,5,6,7,8,9]
rr=[2,5,5,4,5,6,3,7,6]
q=[]
r=[]
for i in range(m):
    q.append(qq[a[i]-1])
    r.append(rr[a[i]-1])

memo={}
def ff(n,m):
    if (n,m) in memo:
        return memo[(n,m)]
    global q,r
    if n==0:
        return ''
    s=0
    f=0
    for i in range(m):
        if (n-r[i])>=0:
            tmp=ff(n-r[i],m)
            if tmp!=None:
                s=max(s,int(str(q[i])+tmp))
            else:
                f+=1
        else:
            f+=1
    if f==m:
        return None
    memo[(n,m)]=str(s)
    return str(s)
print(ff(n,m))

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
A = [int(x) for x in input().split()]
mp = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
dp = [''] * (N+1)
for i in range(1, N+1):
    cand = []
    for x in A:
        if i - mp[x] < 0:
            continue
        if dp[i-mp[x]] == '' and mp[x] != i:
            continue
        cand.append(max(int(str(dp[i - mp[x]]) + str(x)), int(str(x) + str(dp[i - mp[x]]))))
    if cand:
        dp[i] = max(cand)
    else:
        dp[i] = ''
print(dp[N])

Submission status: Time Limit Exceeded

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

dp = ["x"] * (n + 1)
dp[0] = ""
for i in range(1, n + 1):
    for a in aa:
        if i - NUM[a] >= 0 and dp[i - NUM[a]] != "x":
            tmp = dp[i - NUM[a]] + str(a)
            tmp = "".join(sorted(tmp, reverse=True))
            if int(tmp) > (0 if dp[i] == "x" else int(dp[i])):
                dp[i] = tmp
print(dp[n])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**5)
readline = sys.stdin.readline
writelines = sys.stdout.writelines
write = sys.stdout.write

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

A.sort(reverse=1)
CS = [0,2,5,5,4,5,6,3,7,6]

INV = (None, 0)
EMP = ([], 0)

memo = [[-1]*(N+1) for i in range(M+1)]
mM = memo[M]
mM[0] = EMP
for i in range(1, N+1):
    mM[i] = INV
def dfs(rest, i):
    mi = memo[i]
    if mi[rest] != -1:
        return mi[rest]
    v = A[i]; cost = CS[v]
    r = None
    cnt = 0
    k = 0
    kc = 0
    for k in range((rest // cost) + 1):
        r0, c0 = dfs(rest-k*cost, i+1)
        if r0 is not None:
            cnt0 = k + c0
            if r is None or cnt <= cnt0:
                r = r0
                cnt = cnt0
                kc = k
    if r is None:
        mi[rest] = INV
        return INV
    mi[rest] = res = [kc] + r, cnt
    return res
res, _ = dfs(N, 0)
ans = []
for i in range(M):
    ans.append(str(A[i]) * res[i])
writelines(ans)
write("\n")

Submission status: Time Limit Exceeded

Solution code:
def inpl(): return list(map(int, input().split()))

N, M = inpl()
A = inpl()
A.sort(reverse = True)
matnum = set([(2, 5, 5, 4, 5, 6, 3, 7, 6)[a-1] for a in A])
maxdig = 1
Dig = [{0}]
for i in range(1,1+N//min(matnum)):
    k = set()
    for v in Dig[-1]:
        for a in matnum:
            k.add(a+v)
    if N in k:
        maxdig = i
    Dig.append(k)
N1 = N
ansli = [0]*maxdig
for i in range(maxdig, 0, -1):
    for a in A:
        if N1-(2, 5, 5, 4, 5, 6, 3, 7, 6)[a-1] in Dig[i-1]:
            ansli[maxdig-i] = a
            N1 -= (2, 5, 5, 4, 5, 6, 3, 7, 6)[a-1]
            break
        
print(''.join(map(str, ansli)))

Submission status: Time Limit Exceeded

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]
ab = {}
for i in a:
    ab[i] = b[i]
dp = [0]*(n+10)
dp[0] = ""
for i in range(n+1):
    if dp[i] == 0:
        continue
    for j in ab.keys():
        if dp[i] == "":
            dp[i+ab[j]] = str(max(int(dp[i+ab[j]]),j))
        else:
            if dp[i][0]> str(j):
                next0 = dp[i]+str(j)
            else:
                next0 = str(j)+dp[i]
            if dp[i+ab[j]] == 0:
                dp[i+ab[j]] = next0
                continue
            if len(next0) > len(dp[i+ab[j]]):
                dp[i+ab[j]] = next0
            elif len(next0) < len(dp[i+ab[j]]):
                continue
            else:
                for k in range(len(next0)):
                    if next0[k]> dp[i+ab[j]][k]:
                        dp[i+ab[j]] = next0
                        break
                    elif next0[k]< dp[i+ab[j]][k]:
                        break
                else:
                    dp[i+ab[j]] = next0

print(dp[n])

Submission status: Time Limit Exceeded

Solution code:
def inpl(): return list(map(int, input().split()))

def match(x):
    return (2, 5, 5, 4, 5, 6, 3, 7, 6)[x-1]
N, M = inpl()
A = inpl()
A.sort(reverse = True)
matnum = set([match(a) for a in A])
maxdig = 1
Dig = [{0}]
for i in range(1,1+N//min(matnum)):
    k = set()
    for v in Dig[-1]:
        for a in matnum:
            k.add(a+v)
    if N in k:
        maxdig = i
    Dig.append(k)
N1 = N
anstr = ''
for i in range(maxdig, 0, -1):
    for a in A:
        if N1-match(a) in Dig[i-1]:
            anstr += str(a)
            N1 -= match(a)
            break
        
print(anstr)

Submission status: Time Limit Exceeded

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

import functools

DIGIT = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
n, m = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]

memo = {}

for count in range(n + 1):
    answer = -1

    for a in A:
        if count > DIGIT[a]:
            rest = memo[count - DIGIT[a]]
            if rest >= 0:
                s = str(rest)
                answer = max(answer, rest * 10 + a if int(s[0]) > a else int(str(a) + s))
        elif count == DIGIT[a]:
            answer = max(answer, a)

    memo[count] = answer

print(memo[n])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**5)

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

A.sort(reverse=1)
CS = [None,2,5,5,4,5,6,3,7,6]

INV = (None, 0)
EMP = ([], 0)

memo = [[-1]*(N+1) for i in range(M)]
def dfs(rest, i):
    if i == M:
        return EMP if rest == 0 else INV
    mi = memo[i]
    if mi[rest] != -1:
        return mi[rest]
    v = A[i]; cost = CS[v]
    r = None
    cnt = 0
    k = 0
    kc = 0
    for k in range((rest // cost) + 1):
        r0, c0 = dfs(rest-k*cost, i+1)
        if r0 is not None:
            cnt0 = k + c0
            if r is None or cnt <= cnt0:
                r = r0
                cnt = cnt0
                kc = k
    if r is None:
        mi[rest] = INV
        return INV
    mi[rest] = res = [kc] + r, cnt
    return res
res, _ = dfs(N, 0)
ans = []
for i in range(M):
    ans.append(str(A[i]) * res[i])
print(*ans, sep='')

Submission status: Time Limit Exceeded

Solution code:
def intlog10(n):
    if n <= 0:
        return -1
    i = 0
    while 10**i <= n:
        i += 1
    return i-1

N, M = map(int, input().split())
A = [int(a) for a in input().split()]
L = [2, 5, 5, 4, 5, 6, 3, 7, 6]
B = [[A[i], L[A[i]-1]] for i in range(M)]

X = [0] + [-10**9] * N

for i in range(1, N+1):
    for b in B:
        if b[1] <= i:
            if X[i-b[1]] == 0:
                X[i] = max(X[i], b[0])
            else:
                X[i] = max(X[i], X[i-b[1]]*10 + b[0], X[i-b[1]] + b[0] * (10**intlog10(X[i-b[1]])))
    
print(X[N])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**5)

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

A.sort(reverse=1)
CS = [None,2,5,5,4,5,6,3,7,6]

memo = [{} for i in range(M+1)]
def dfs(rest, i):
    if i == M:
        return ([] if rest == 0 else None), 0
    mi = memo[i]
    if rest in mi:
        return mi[rest]
    v = A[i]; cost = CS[v]
    r = None
    cnt = 0
    k = 0
    kc = 0
    for k in range((rest // cost) + 1):
        r0, c0 = dfs(rest-k*cost, i+1)
        if r0 is not None:
            cnt0 = k + c0
            if r is None or cnt <= cnt0:
                r = r0
                cnt = cnt0
                kc = k
        k += 1
    if r is None:
        mi[rest] = r = None, 0
    else:
        mi[rest] = r = [kc] + r, cnt
    return r
res, _ = dfs(N, 0)
ans = []
for i in range(M):
    ans.append(str(A[i]) * res[i])
print(*ans, sep='')

Submission status: Time Limit Exceeded

Solution code:
def intlog10(n):
    if n <= 0:
        return -1
    i = 0
    while 10**i <= n:
        i += 1
    return i-1

N, M = map(int, input().split())
A = [int(a) for a in input().split()]
L = [2, 5, 5, 4, 5, 6, 3, 7, 6]
B = [[A[i], L[A[i]-1]] for i in range(M)]

X = [0] + [-10**9] * N

for i in range(1, N+1):
    for b in B:
        if b[1] <= i:
            if X[i-b[1]] == 0:
                X[i] = max(X[i], b[0])
            else:
                X[i] = max(X[i], X[i-b[1]]*10 + b[0], X[i-b[1]] + b[0] * (10**intlog10(X[i-b[1]])))
    
print(X[N])