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:
# -*- coding: utf-8 -*-
"""
Created on Sat Feb 16 19:31:10 2019
ABC118D
@author: maezawa
"""
import copy

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

nmatch = [2,5,5,4,5,6,3,7,6]
rmatch = list(reversed(nmatch))
nmdic = dict([(i+1,nmatch[i]) for i in range(9)])
#nums = [[],[],[1],[7],[4],[2,3,5],[6,9],[8]]
nums = [[] for _ in range(10)]
for  i in a:
    nums[nmdic[i]].append(i)
        
#print(nmdic)
#print(nums)

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

for i in range(1, n+1):
    cnds = []
    for j in range(2, 8):
        if nums[j] == []:
            continue
        if dp[i-j][0] == -1:
            continue
        cndo = dp[i-j][0]+1
        cndos = copy.copy(dp[i-j][1])
        cndos.append(max(nums[j]))
        cnds.append([cndo, cndos])
        #print(i, i-j, cnds, cndos)
    if cnds == []:
        continue
    dp[i] = max(cnds, key=lambda x: x[0])

ans = ''.join(map(str, sorted(dp[n][1], reverse=True)))
print(ans)

Submission status: Runtime Error

Solution code:
cost = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
def solve(yoshida, possible, dp):
    if(yoshida == 0):
        dp[0] = 0
    elif(dp[yoshida] == -1):
        for x in possible:
            if(yoshida >= cost[x]):
                idx = yoshida - cost[x]
                solve(idx, possible, dp)
                a = (dp[idx]) * 10 + x
                dp[yoshida] = max(dp[yoshida], a)

if __name__ == '__main__':
    n, m = map(int, input().split())
    lst = list(map(int, input().split(" ")))
    DP = [-1] * (n + 1)
    solve(n, lst, DP)
    '''
    for i in range(n + 1):
        print("{} : {}".format(i, DP[i]))
    '''
    print(DP[n])

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Feb 16 19:31:10 2019
ABC118D
@author: maezawa
"""
import copy

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

nmatch = [2,5,5,4,5,6,3,7,6]
rmatch = list(reversed(nmatch))
nmdic = dict([(i+1,nmatch[i]) for i in range(9)])
#nums = [[],[],[1],[7],[4],[2,3,5],[6,9],[8]]
nums = [[] for _ in range(10)]
for i in range(10):
    if i in a:
        nums[nmdic[i]].append(i)
        
#print(nmdic)
#print(nums)

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

for i in range(1, n+1):
    maxorder = 0
    cnds = []
    for j in range(1, 7):
        if nums[j] == []:
            continue
        if dp[i-j][0] == -1:
            continue
        cndo = dp[i-j][0]+1
        cndos = copy.copy(dp[i-j][1])
        cndos.append(max(nums[j]))
        cnds.append([cndo, cndos])
        #print(i, i-j, cnds, cndos)
    if cnds == []:
        continue
    dp[i] = max(cnds, key=lambda x: x[0])

ans = ''.join(map(str, sorted(dp[n][1], reverse=True)))
print(ans)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
lst = list(map(int, input().split()))
lst = sorted(lst, key = lambda x:-x)
dic = {1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6}

s = set()
for i in lst:
    s.add(dic[i])
s = list(sorted(s))

dp = [0] * (n+1)
for i in range(0, n+1):
    a = 0
    max_a = 0
    for j in s:
        if i-j < 0:
            pass
        elif i == j:
            a = 1
        elif i - j > 0 and dp[i-j] > 0:
            a = dp[i-j] + 1
        if max_a < a:
            max_a = a
    dp[i] = max_a

def out(dp, dic, n, ans, ans_digit, lst):
    if len(ans) == ans_digit-1:
        for i in lst:
            if n == dic[i]:
                return ans + str(i)
    else:
        for i in lst:
            if n - dic[i] >= 0:
                if dp[n] -1 == dp[n-dic[i]]:
                    ans += str(i)
                    next_n = n - dic[i]
                    break
        return out(dp, dic, next_n, ans, ans_digit, lst)
    
print(out(dp, dic, n, '', dp[n], lst))

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
lst = list(map(int, input().split()))
lst = sorted(lst, key = lambda x:-x)
dic = {1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6}

s = set()
for i in lst:
    s.add(dic[i])
s = list(sorted(s))

dp = [0] * (n+1)
for i in range(0, n+1):
    a = 0
    max_a = -1
    for j in s:
        if i-j < 0:
            continue
        if i == j and dp[i-j] == 0:
            a = 1
        elif i - j > 0 and dp[i-j] > 0:
            a = dp[i-j] + 1
        if max_a < a:
            max_a = a
    dp[i] = max_a

def out(dp, dic, n, ans, ans_digit, lst):
    if len(ans) == ans_digit-1:
        for i in lst:
            if n == dic[i]:
                return ans + str(i)
    else:
        for i in lst:
            if n - dic[i] >= 0:
                if dp[n] -1 == dp[n-dic[i]]:
                    ans += str(i)
                    next_n = n - dic[i]
                    break
        return out(dp, dic, next_n, ans, ans_digit, lst)
    
print(out(dp, dic, n, '', dp[n], lst))

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
lst = list(map(int, input().split()))
lst = sorted(lst, key = lambda x:-x)
dic = {1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6}

s = set()
for i in lst:
    s.add(dic[i])
s = list(sorted(s))

dp = [0] * (n+1)
for i in range(0, n+1):
    a = 0
    max_a = 0
    for j in s:
        if i-j < 0:
            continue
        if i == j and dp[i-j] == 0:
            a = 1
        elif i - j > 0 and dp[i-j] > 0:
            a = dp[i-j] + 1
        if max_a < a:
            max_a = a
    dp[i] = max_a

def out(dp, dic, n, ans, ans_digit, lst):
    if len(ans) == ans_digit-1:
        for i in lst:
            if n == dic[i]:
                return ans + str(i)
    else:
        for i in lst:
            if n - dic[i] >= 0:
                if dp[n] -1 == dp[n-dic[i]]:
                    ans += str(i)
                    next_n = n - dic[i]
                    break
        return out(dp, dic, next_n, ans, ans_digit, lst)
    
print(out(dp, dic, n, '', dp[n], lst))

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
lst = list(map(int, input().split()))
lst = sorted(lst, key = lambda x:-x)
dic = {1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6}

s = set()
for i in lst:
    s.add(dic[i])
s = list(sorted(s))

dp = [0] * (n+1)
for i in range(0, n+1):
    a = 0
    max_a = 0
    for j in s:
        if i == j and dp[i-j] == 0:
            a = 1
        elif i - j > 0 and dp[i-j] > 0:
            a = dp[i-j] + 1
        if max_a < a:
            max_a = a
    dp[i] = max_a

def out(dp, dic, n, ans, ans_digit, lst):
    if len(ans) == ans_digit-1:
        for i in lst:
            if n == dic[i]:
                return ans + str(i)
    else:
        for i in lst:
            if n - dic[i] >= 0:
                if dp[n] -1 == dp[n-dic[i]]:
                    ans += str(i)
                    next_n = n - dic[i]
                    break
        return out(dp, dic, next_n, ans, ans_digit, lst)
    
print(out(dp, dic, n, '', dp[n], lst))

Submission status: Runtime Error

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 = [""]*N
for a in A:
    if N - cost[a] >= 0:
        DP[N-cost[a]] = str(a)

ans = ""
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 == "":
            continue
        for a in A:
            nk = i - cost[a]
            if nk >= 0:
                ok = True
                DP2[nk] = max(DP2[nk], v + str(a))
    ans = max(ans, DP2[0])
    DP = DP2
    if ok == False:
        break

print(ans)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
lst = list(map(int, input().split()))
lst = sorted(lst, key = lambda x:-x)
dic = {1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6}

s = set()
for i in lst:
    s.add(dic[i])
s = list(sorted(s))

dp = [0] * (n+1)
for i in range(0, n+1):
    a = 0
    max_a = 0
    for j in s:
        if i == j and dp[i-j] == 0:
            a = 1
        elif i - j >= 0 and dp[i-j] > 0:
            a = dp[i-j] + 1
        if max_a < a:
            max_a = a
    dp[i] = max_a

def out(dp, dic, n, ans, ans_digit, lst):
    if len(ans) == ans_digit-1:
        for i in lst:
            if n == dic[i]:
                return ans + str(i)
    else:
        for i in lst:
            if n - dic[i] >= 0:
                if dp[n] -1 == dp[n-dic[i]]:
                    ans += str(i)
                    next_n = n - dic[i]
                    break
        return out(dp, dic, next_n, ans, ans_digit, lst)
    
print(out(dp, dic, n, '', dp[n], lst))

Submission status: Runtime Error

Solution code:
# Pythonで楽々いけちゃったりしないかな？
cost = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
def solve(yoshida, possible, dp):
    if(yoshida == 0):
        dp[0] = 0
        return 0
    if(dp[yoshida] != -1):
        return dp[yoshida]
    for x in possible:
        if(yoshida >= cost[x]):
            if(solve(yoshida - cost[x], possible, dp) != -2):
                a = dp[yoshida - cost[x]] * 10 + x
                dp[yoshida] = max(dp[yoshida], a)
    if(dp[yoshida] == -1):
        dp[yoshida] = -2
    return dp[yoshida]

if __name__ == '__main__':
    n, m = map(int, input().split())
    lst = list(map(int, input().split()))
    DP = [-1] * (n + 1)
    print(solve(n, lst, DP))
    '''
    for i in range(n + 1):
        print("{} : {}".format(i, solve(i, lst, DP)))
    '''

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
lst = list(map(int, input().split()))
lst = sorted(lst, key = lambda x:-x)
dic = {1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6}

s = set()
for i in lst:
    s.add(dic[i])
s = list(sorted(s))

dp = [0] * (n+1)
for i in range(0, n+1):
    max_a = 0
    for j in s:
        if i == j:
            max_a = 1
        elif i - j >= 0 and dp[i-j] > 0:
            a = dp[i-j] + 1
            if max_a < a:
                max_a = a
    dp[i] = max_a

def out(dp, dic, n, ans, ans_digit, lst):
    if len(ans) == ans_digit-1:
        for i in lst:
            if n == dic[i]:
                return ans + str(i)
    else:
        for i in lst:
            if n - dic[i] >= 0:
                if dp[n] -1 == dp[n-dic[i]]:
                    ans += str(i)
                    next_n = n - dic[i]
                    break
        return out(dp, dic, next_n, ans, ans_digit, lst)
    
print(out(dp, dic, n, '', dp[n], lst))

Submission status: Runtime Error

Solution code:
import numpy as np

#initialization
nmatch = [2,5,5,4,5,6,3,7,6]
f = input()
f = f.split()
N = int(f[0])
M = int(f[1])
dp = [-1]*(N+1) # contains the number of digits it can make
dp[0] = 0
ff = input()
ff = ff.split()
Atemp = [] #contains the number that can be used and the number of matches needed to make the match
for number in ff:
    temp = [int(number),nmatch[int(number)-1]]
    Atemp.append(temp)
Atemp = np.array(Atemp)
index0 = np.argsort(Atemp[:,0])
index1 = np.argsort(Atemp[:,1])
A = Atemp[index1] #sorted by the number of matches: ascending
B = Atemp[index0]
B = B[::-1] #sorted by the number: descending

for i in range(1,N+1):
    #dp(i)を求める
    for k in range(M):
        j = A[k,1]
        i_old = i - j #available matches
        if (i-j) < 0:
            break
        if (i-j) == 0 and dp[i] == -1:
            dp[i] = 1
        if dp[i_old] != -1 and dp[i_old]+1 > dp[i]:
            dp[i] = dp[i_old] + 1
ndigits = dp[N]
j = N
final_number = ''
for l in range(ndigits,0,-1):
    #桁を求めていく
    index = 0
    while True:
        temp_j = j - B[index,1]
        if dp[temp_j] + 1 == dp[j]:
            final_number  += str(B[index,0])
            j = temp_j
            break
        else:
            index += 1
        if index > M:
            print('smth is wrong')
            break
print(int(final_number))

Submission status: Runtime Error

Solution code:
import numpy as np

#initialization
nmatch = [2,5,5,4,5,6,3,7,6]
f = input()
f = f.split()
N = int(f[0])
M = int(f[1])
dp = [-1]*(N+1) # contains the number of digits it can make
dp[0] = 0
ff = input()
ff = ff.split()
Atemp = [] #contains the number that can be used and the number of matches needed to make the match
for number in ff:
    temp = [int(number),nmatch[int(number)-1]]
    Atemp.append(temp)
Atemp = np.array(Atemp)
index0 = np.argsort(Atemp[:,0])
index1 = np.argsort(Atemp[:,1])
A = Atemp[index1] #sorted by the number of matches: ascending
B = Atemp[index0]
B = B[::-1] #sorted by the number: descending

for i in range(1,N+1):
    #dp(i)を求める
    for k in range(M):
        j = A[k,1]
        i_old = i - j #available matches
        if (i-j) < 0:
            break
        if (i-j) == 0 and dp[i] == -1:
            dp[i] = 1
        if dp[i_old] != -1 and dp[i_old]+1 > dp[i]:
            dp[i] = dp[i_old] + 1
ndigits = dp[N]
j = N
final_number = ''
for l in range(ndigits,0,-1):
    #桁を求めていく
    index = 0
    while True:
        temp_j = j - B[index,1]
        if dp[temp_j] + 1 == dp[j]:
            final_number  += str(B[index,0])
            j = temp_j
            break
        else:
            index += 1
        if index > 4:
            print('smth is wrong')
            break
print(int(final_number))

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
lst = list(map(int, input().split()))
lst = sorted(lst, key = lambda x:-x)
dic = {1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6}

s = set()
for i in lst:
    s.add(dic[i])
s = list(sorted(s))

dp = [0] * (n+1)
for i in range(0, n+2):
    max_a = 0
    for j in s:
        if i - j >= 0:
            a = dp[i-j] + 1
            if max_a < a:
                max_a = a
    dp[i] = max_a

def out(dp, dic, n, ans, ans_digit):
    if len(ans) == ans_digit-1:
        for i in lst:
            if n == dic[i]:
                return ans + str(i)
    else:
        for i in lst:
            if n - dic[i] >= 0:
                if dp[n] -1 == dp[n-dic[i]]:
                    ans += str(i)
                    next_n = n - dic[i]
                    break
        return out(dp, dic, next_n, ans, ans_digit)
    
print(out(dp, dic, n, '', dp[n]))

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
lst = list(map(int, input().split()))
lst = sorted(lst, key = lambda x:-x)
dic = {1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6}

s = set()
for i in lst:
    s.add(dic[i])
s = list(sorted(s))

dp = [0] * (n+1)
for i in range(0, n+1):
    max_a = 0
    for j in s:
        if i - j >= 0:
            a = dp[i-j] + 1
            if max_a < a:
                max_a = a
    dp[i] = max_a

def out(dp, dic, n, ans, ans_digit):
    if len(ans) == ans_digit-1:
        for i in lst:
            if n == dic[i]:
                return ans + str(i)
    else:
        for i in lst:
            if n - dic[i] >= 0:
                if dp[n] -1 == dp[n-dic[i]]:
                    ans += str(i)
                    next_n = n - dic[i]
                    break
        return out(dp, dic, next_n, ans, ans_digit)
    
print(out(dp, dic, n, '', dp[n]))

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
lst = list(map(int, input().split()))
lst = sorted(lst, key = lambda x:-x)
dic = {1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6}

s = set()
for i in lst:
    s.add(dic[i])
s = list(sorted(s))

dp = [0] * (n+1)
for i in range(0, n+1):
    max_a = 0
    for j in s:
        if i - j >= 0:
            a = dp[i-j] + 1
            if max_a < a:
                max_a = a
    dp[i] = max_a

def out(dp, dic, n, ans, ans_digit):
    if len(ans) == ans_digit-1:
        for i in lst:
            if n == dic[i]:
                return ans + str(i)
    else:
        for i in lst:
            if n - dic[i] > 0:
                if dp[n] -1 == dp[n-dic[i]]:
                    ans += str(i)
                    next_n = n - dic[i]
                    break
        return out(dp, dic, next_n, ans, ans_digit)
    
print(out(dp, dic, n, '', dp[n]))

Submission status: Runtime Error

Solution code:
n,m,*a=map(int,open(0).read().split())
d=[0]+[-1]*n
for i in range(n):d[i+1]=max(j+d[i-int('0144345265'[j])]*10for j in a)
print(d[n])

Submission status: Runtime Error

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

a.sort()
table = {1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}

dp = ["" for i in range(n + 1)]
for x in a:
    dp[table[x]] = str(x)

def comp(a, b):
    len_a = len(a)
    len_b = len(b)
    if len_a < len_b:
        return b
    if len_a > len_b:
        return a
    #  len_a == len_b
    for i in range(len_a):
        tmp_a = a[i]
        tmp_b = b[i]
        if tmp_a < tmp_b:
            return b
        if tmp_a > tmp_b:
            return a
    # a == b
    return a

for i in range(1, n + 1):
    for x in a:
        tmpstr = str(x)
        tmprest = i - table[x]
        if tmprest < 0:
            tmpstr = ""
        if 0 <= tmprest:
            # load dp
            tmp = dp[tmprest]
            if tmp == "":
                tmpstr = ""
            else:
                tmpstr = tmp + str(x)
        dp[i] = comp(dp[i], tmpstr)

print(dp[-1])

Submission status: Runtime Error

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

a.sort()
table = {1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}

dp = ["" for i in range(n + 1)]
for x in a:
    dp[table[x]] = str(x)

def str_max(maxstrs):
    maxstrlen = max(map(lambda x:len(x), maxstrs))
    maxstr = max(filter(lambda x:len(x) == maxstrlen, maxstrs))
    return maxstr


for i in range(n + 1):
    for x in a:
        tmpstr = str(x)
        tmprest = i - table[x]
        if tmprest < 0:
            tmpstr = ""
        if 0 <= tmprest:
            # load dp
            tmp = dp[tmprest]
            if tmp == "":
                tmpstr = ""
            else:
                tmpstr = tmp + str(x)
        dp[i] = str_max([dp[i], tmpstr])

print(dp[-1])

Submission status: Runtime Error

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

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

dp = ["" for i in range(n + 1)]
for x in a:
    dp[table[x]] = str(x)

def str_max(maxstrs):
    maxstrlen = max(map(lambda x:len(x), maxstrs))
    maxstr = max(filter(lambda x:len(x) == maxstrlen, maxstrs))
    return maxstr


for i in range(n + 1):
    for x in a:
        tmpstr = str(x)
        tmprest = i - table[x]
        if tmprest < 0:
            tmpstr = ""
        if 0 <= tmprest:
            # load dp
            tmp = dp[tmprest]
            if tmp == "":
                tmpstr = ""
            else:
                tmpstr = tmp + str(x)
        dp[i] = str_max([dp[i], tmpstr])

print(dp[-1])

Submission status: Runtime Error

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

# n, m = (20, 4)
# a = [3, 7, 8, 4]

# n,m = (15, 3)
# a = [5, 4, 6]

a.sort()
table = {1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}

dp = ["" for i in range(n + 1)]
for x in a:
    dp[table[x]] = str(x)

def str_max(maxstrs):
    maxstrlen = max(map(lambda x:len(x), maxstrs))
    maxstr = max(filter(lambda x:len(x) == maxstrlen, maxstrs))
    return maxstr


for i in range(n + 1):
    for x in a:
        tmpstr = str(x)
        tmprest = i - table[x]
        if tmprest < 0:
            tmpstr = ""
        if 0 <= tmprest:
            # load dp
            tmp = dp[tmprest]
            if tmp == "":
                tmpstr = ""
            else:
                tmpstr = tmp + str(x)
        # print("{} {} : {} : {}".format(i, x, tmpstr, tmprest))
        # print(dp)
        dp[i] = str_max([dp[i], tmpstr])
        # print(dp)
    # print("")

print(dp[-1])

Submission status: Runtime Error

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

dp=['']*(n+1)
dp[0]=''
for i in range(1,n+1):
    max=''
    for j in range(m):
        if (i-c[int(A[j])]!=0 and dp[i-c[int(A[j])]]!='') or (i-c[int(A[j])]==0):
            if len(dp[i-c[int(A[j])]]+A[j])>len(max):
                max=dp[i-c[int(A[j])]]+A[j]
            elif len(dp[i-c[int(A[j])]]+A[j])==len(max) and dp[i-c[int(A[j])]]+A[j]>max:
                max=dp[i-c[int(A[j])]]+A[j]
    dp[i]=max
    #print(dp)
print(dp[n])

Submission status: Runtime Error

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

num_priority = sorted([(num, matchsticks) for num, matchsticks in num_matchsticks_map.items() if num in A],
                      key=lambda num_matchsticks: num_matchsticks[1] * 10 + (10 - num_matchsticks[0]))

min_sticks = num_priority[0][1]

def num_list_to_max(num_list):
    return int("".join([str(num) for num in sorted(num_list, reverse=True)]))


def gen_max_value(max, num_list, rest_matchsticks):
    # print("gen_max_value: {} {} {}".format(max, num_list, rest_matchsticks))
    if num_list and rest_matchsticks == 0:
        return num_list_to_max(num_list)

    if len(num_list) + int(rest_matchsticks / min_sticks) <= int(max / 10):
        return max

    for num_matchsticks in num_priority:
        if rest_matchsticks - num_matchsticks[1] < 0:
            continue

        current_num_list = list(num_list)
        current_num_list.insert(0, num_matchsticks[0]),
        current_value = gen_max_value(max,
                                      current_num_list,
                                      rest_matchsticks - num_matchsticks[1])

        if current_value > max:
            max = current_value

    return max


max = gen_max_value(0, [], N)
print("{}".format(max))

Submission status: Runtime Error

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

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

num_priority = sorted([(num, matchsticks) for num, matchsticks in num_matchsticks_map.items() if num in A],
                      key=lambda num_matchsticks: num_matchsticks[1] * 10 + (10 - num_matchsticks[0]))

min_sticks = num_priority[0][1]

def num_list_to_max(num_list):
    return int("".join([str(num) for num in sorted(num_list, reverse=True)]))


def gen_max_value(max, num_list, rest_matchsticks):
    if num_list and rest_matchsticks == 0:
        return num_list_to_max(num_list)

    if len(num_list) + int(rest_matchsticks / min_sticks) < int(max / 10):
        return max

    for num_matchsticks in num_priority:
        if rest_matchsticks - num_matchsticks[1] < 0:
            continue

        current_num_list = list(num_list)
        current_num_list.insert(0, num_matchsticks[0]),
        current_value = gen_max_value(max,
                                      current_num_list,
                                      rest_matchsticks - num_matchsticks[1])

        if current_value > max:
            max = current_value

    return max


max = gen_max_value(0, [], N)
print("{}".format(max))

Submission status: Runtime Error

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

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

num_priority = sorted([(num, matchsticks) for num, matchsticks in num_matchsticks_map.items() if num in A],
                      key=lambda num_matchsticks: num_matchsticks[1] * 10 + (10 - num_matchsticks[0]))


def num_list_to_max(num_list):
    return int("".join([str(num) for num in sorted(num_list, reverse=True)]))


def gen_max_value(max, num_list, rest_matchsticks):
    if num_list and rest_matchsticks == 0:
        return num_list_to_max(num_list)

    for num_matchsticks in num_priority:
        if rest_matchsticks - num_matchsticks[1] < 0:
            continue

        current_num_list = list(num_list)
        current_num_list.insert(0, num_matchsticks[0]),
        current_value = gen_max_value(max,
                                      current_num_list,
                                      rest_matchsticks - num_matchsticks[1])

        if current_value > max:
            max = current_value

    return max


max = gen_max_value(0, [], N)
print("{}".format(max))

Submission status: Runtime Error

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

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

num_priority = sorted([(num, matchsticks) for num, matchsticks in num_matchsticks_map.items() if num in A],
                      key=lambda num_matchsticks: num_matchsticks[1] * 10 + (10 - num_matchsticks[0]))


def gen_num_list(num_list, rest_matchsticks):
    if num_list and rest_matchsticks == 0:
        return num_list

    for num_matchsticks in num_priority:
        if rest_matchsticks - num_matchsticks[1] < 0:
            continue

        current_num_list = list(num_list)
        current_num_list.insert(0, num_matchsticks[0]),
        generated_num_list = gen_num_list(current_num_list,
                                          rest_matchsticks - num_matchsticks[1])
        if generated_num_list:
            return generated_num_list


num_list = gen_num_list([], N)
print("{}".format("".join([str(num) for num in sorted(num_list, reverse=True)])))

Submission status: Runtime Error

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

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

num_priority = sorted([(num, matchsticks) for num, matchsticks in num_matchsticks_map.items() if num in A],
                      key=lambda num_matchsticks: num_matchsticks[1] * 10 + (10 - num_matchsticks[0]))


def gen_num_list(num_list, rest_matchsticks):
    if num_list and rest_matchsticks == 0:
        return num_list

    for num_matchsticks in num_priority:
        if rest_matchsticks - num_matchsticks[1] < 0:
            return []

        current_num_list = list(num_list)
        current_num_list.insert(0, num_matchsticks[0]),
        generated_num_list = gen_num_list(current_num_list,
                                          rest_matchsticks - num_matchsticks[1])
        if generated_num_list:
            return generated_num_list


num_list = gen_num_list([], N)
print("{}".format("".join([str(num) for num in sorted(num_list, reverse=True)])))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
import copy
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, M, A):
    c = [
        -1,
        2, # 1 
        5, # 2
        5, # 3
        4, # 4
        5, # 5
        6, # 6
        3, # 7
        7, # 8
        6, # 9
        ]
    
    if (2 in A or 3 in A) and 5 in A:
        A.remove(2)
        A.remove(3)
    if 2 in A and 3 in A:
        A.remove(2)
    if 6 in A and 9 in A:
        A.remove(6)



    dp = [None] * (N+1) 
    dp[N] = (0, Counter())
    for i in range(N, 0, -1):
        if dp[i] is None:
            continue
        
        for a in A:
            if i - c[a] < 0:
                continue
            
            if dp[i-c[a]] is None:
                c_ = copy.copy(dp[i][1])
                c_[a] += 1
                dp[i-c[a]] =  (dp[i][0]+1, c_)
            
            elif dp[i][0]+1 > dp[i-c[a]][0]:
                c_ = copy.copy(dp[i][1])
                c_[a] += 1
                dp[i-c[a]] =  (dp[i][0]+1, c_)
    # print(0, dp[0])

    ans = ""
    for r in  sorted(dp[0][1], reverse=True):
        ans += str(r) * dp[0][1][r]
    return ans


def main():
    # N = read_int()
    N, M = read_int_n()
    A = read_int_n()
    print(slv(N, M, A))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
A=[int(i) for i in input().split()]
Match=[0,2,5,5,4,5,6,3,7,6]
A.sort(reverse=True)
dp=[0]*(N+1)
dp[0]=1
for i in range(1,N+1):
  for a in A:
    if i>=Match[a]:
      dp[i]|=dp[i-Match[a]]<<1

for k in range(N)[::-1]:
  if dp[N]&(1<<k):
    S=k
    break
ans=[]
m=0
for k in range(S):
  if dp[N-Match[A[m]]]&(1<<(S-k-1)) and N-Match[A[m]]>=0:
    ans.append(str(A[m]))
    N-=Match[A[m]]
  else:
    for l in range(m+1,len(A)):
      if dp[N-Match[A[l]]]&(1<<(S-k-1)) and N-Match[A[l]]>=0:
        m=l
        ans.append(str(A[m]))
        N-=Match[A[m]]
        break
print("".join(ans))

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
A=[int(i) for i in input().split()]
Match=[0,2,5,5,4,5,6,3,7,6]
A.sort(reverse=True)
dp=[0]*(N+1)
dp[0]=1
for i in range(1,N+1):
  for a in A:
    if i>=Match[a]:
      dp[i]|=dp[i-Match[a]]<<1

for k in range(N)[::-1]:
  if dp[N]&(1<<k):
    S=k
    break
ans=[]
m=0
for k in range(S):
  if dp[N-Match[A[m]]]&(1<<(S-k-1)):
    ans.append(str(A[m]))
    N-=Match[A[m]]
  else:
    for l in range(m+1,len(A)):
      if dp[N-Match[A[l]]]&(1<<(S-k-1)):
        m=l
        ans.append(str(A[m]))
        N-=Match[A[m]]
        break
print("".join(ans))