Problem:


Score : 400 points

Problem Statement

Find the largest integer that can be formed with exactly N matchsticks, under the following conditions:

Every digit in the integer must be one of the digits A_1, A_2, ..., A_M (1 \leq A_i \leq 9).

The number of matchsticks used to form digits 1, 2, 3, 4, 5, 6, 7, 8, 9 should be 2, 5, 5, 4, 5, 6, 3, 7, 6, respectively.

Constraints

All values in input are integers.

2 \leq N \leq 10^4

1 \leq M \leq 9

1 \leq A_i \leq 9

A_i are all different.

There exists an integer that can be formed by exactly N matchsticks under the conditions.

Input

Input is given from Standard Input in the following format:

N M
A_1 A_2 ... A_M

Output

Print the largest integer that can be formed with exactly N matchsticks under the conditions in the problem statement.

Sample Input 1

20 4
3 7 8 4

Sample Output 1

777773

The integer 777773 can be formed with 3 + 3 + 3 + 3 + 3 + 5 = 20 matchsticks, and this is the largest integer that can be formed by 20 matchsticks under the conditions.

Sample Input 2

101 9
9 8 7 6 5 4 3 2 1

Sample Output 2

71111111111111111111111111111111111111111111111111

The output may not fit into a 64-bit integer type.

Sample Input 3

15 3
5 4 6

Sample Output 3

654



Sample input:
20 4
3 7 8 4


Sample output:
777773

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10 ** 8)
lst = [[1,2], [2, 5], [3, 5], [4, 4], [5, 5], [6, 6], [7, 3], [8, 7], [9, 6]]
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse = True)
# print (A)

def num(k):
    return lst[k-1][1]

# for i in A:
    # print (num(i), end = ', ')
# print ()

INF = 10 ** 9
dp_lst = [-INF] * (N + 1)
dp_lst[0] = 0
def dp(i):
    if dp_lst[i] != -INF:
        return dp_lst[i]
    tmp = -INF
    for j in A:
        if i >= num(j):
            tmp = max(tmp, dp(i - num(j)) + 1)
    dp_lst[i] = tmp
    return dp_lst[i]

a = dp(N)
# print (a)
# print (dp_lst)   
# print ([0] * 10 +[i+1 for i in range(20)])

# print (len(str(71111111111111111111111111111111111111111111111111)))

def check(A):
    if dp_lst[N-num(A)] == dp_lst[N] - 1:
        return True
    else:
        return False

# print (a)
while a > 0:
    for i in A:
        if check(i):
            print (i, end = '')
            N -= num(i)
            a -= 1
            break
        else:
            pass
            # print ('B')
print ()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
lst = [[1,2], [2, 5], [3, 5], [4, 4], [5, 5], [6, 6], [7, 3], [8, 7], [9, 6]]
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse = True)
# print (A)

def num(k):
    return lst[k-1][1]

# for i in A:
    # print (num(i), end = ', ')
# print ()

INF = 10 ** 9
dp_lst = [-INF] * (N + 1)
dp_lst[0] = 0
def dp(i):
    if dp_lst[i] != -INF:
        return dp_lst[i]
    tmp = -INF
    for j in A:
        if i >= num(j):
            tmp = max(tmp, dp(i - num(j)) + 1)
    dp_lst[i] = tmp
    return dp_lst[i]

a = dp(N)
# print (a)
# print (dp_lst)   
# print ([0] * 10 +[i+1 for i in range(20)])

# print (len(str(71111111111111111111111111111111111111111111111111)))

def check(A):
    if dp_lst[N-num(A)] == dp_lst[N] - 1:
        return True
    else:
        return False

# print (a)
while a > 0:
    for i in A:
        if check(i):
            print (i, end = '')
            N -= num(i)
            a -= 1
            break
        else:
            pass
            # print ('B')
print ()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10 ** 10)
lst = [[1,2], [2, 5], [3, 5], [4, 4], [5, 5], [6, 6], [7, 3], [8, 7], [9, 6]]
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse = True)
# print (A)

def num(k):
    return lst[k-1][1]

# for i in A:
    # print (num(i), end = ', ')
# print ()

INF = 10 ** 9
dp_lst = [-INF] * (N + 1)
dp_lst[0] = 0
def dp(i):
    if dp_lst[i] != -INF:
        return dp_lst[i]
    tmp = -INF
    for j in A:
        if i >= num(j):
            tmp = max(tmp, dp(i - num(j)) + 1)
    dp_lst[i] = tmp
    return dp_lst[i]

a = dp(N)
# print (a)
# print (dp_lst)   
# print ([0] * 10 +[i+1 for i in range(20)])

# print (len(str(71111111111111111111111111111111111111111111111111)))

def check(A):
    if dp_lst[N-num(A)] == dp_lst[N] - 1:
        return True
    else:
        return False

# print (a)
while a > 0:
    for i in A:
        if check(i):
            print (i, end = '')
            N -= num(i)
            a -= 1
            break
        else:
            pass
            # print ('B')
print ()

Submission status: Runtime Error

Solution code:
lst = [[1,2], [2, 5], [3, 5], [4, 4], [5, 5], [6, 6], [7, 3], [8, 7], [9, 6]]
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse = True)
# print (A)

def num(k):
    return lst[k-1][1]

# for i in A:
    # print (num(i), end = ', ')
# print ()

INF = 10 ** 9
dp_lst = [-INF] * (N + 1)
dp_lst[0] = 0
def dp(i):
    if dp_lst[i] != -INF:
        return dp_lst[i]
    tmp = -INF
    for j in A:
        if i >= num(j):
            tmp = max(tmp, dp(i - num(j)) + 1)
    dp_lst[i] = tmp
    return dp_lst[i]

a = dp(N)
# print (a)
# print (dp_lst)   
# print ([0] * 10 +[i+1 for i in range(20)])

# print (len(str(71111111111111111111111111111111111111111111111111)))

def check(A):
    if dp_lst[N-num(A)] == dp_lst[N] - 1:
        return True
    else:
        return False

# print (a)
while a > 0:
    for i in A:
        if check(i):
            print (i, end = '')
            N -= num(i)
            a -= 1
            break
        else:
            pass
            # print ('B')
print ()
# print (71111111111111111111111111111111111111111111111111)

Submission status: Runtime Error

Solution code:
from sys import stdin

N, M = [int(x) for x in stdin.readline().rstrip().split()]
S = [2, 5, 5, 4, 5, 6, 3, 7, 6]
A = [int(x) for x in stdin.readline().rstrip().split()]
B = [(x, S[x - 1]) for x in A]
B.sort(key=lambda x: x[1])
print(B)


def solve(match, ans):
    if match == 0:
        return int(ans)
    if match < B[0][1]:
        return -1
    return max([solve(match - B[k][1], ans + str(B[k][0])) for k in range(len(A))])


print(solve(N, ''))

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''
N, M = map(int, input().split())
A = list(map(int, input().split()))

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

for i in range(M):
	available.append((A[i], recipe[A[i] - 1]))
	
available.sort(reverse = True)
dp[0] = 0

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

cost = 0
ans = ''

for i in range(dp[N]):
	for j in range(M):
		if dp[N - cost - available[j][1]] == dp[N - cost] - 1:
			cost += available[j][1]
			ans += str(available[j][0])
			break
	
print(ans)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''
N, M = map(int, input().split())
A = list(map(int, input().split()))

recipe = [2, 5, 5, 4, 5, 6, 3, 7, 6]
strategy = []

for i in A:
	strategy.append((recipe[i - 1], -i))
	
strategy.sort()
l = []

def dfs(cost):
	if cost > N:
		return False
	elif cost == N:
		return True
		
	for j in range(M):
		res = dfs(cost + strategy[j][0])
		if res:
			l.append(-strategy[j][1])
			return True

	return False
	
dfs(0)
l.sort(reverse=True)
c = map(str, l)
print(''.join(c))

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
A=[int(i) for i in input().split()]
if 2 in A and 3 in A:
  A.remove(2)
if 3 in A and 5 in A:
  A.remove(3)
if 2 in A and 5 in A:
  A.remove(2)
if 6 in A and 9 in A:
  A.remove(6)
m=len(A)
D={}
D[1]=2
D[2]=5
D[3]=5
D[4]=4
D[5]=5
D[6]=6
D[7]=3
D[8]=7
D[9]=6
DP=[-float("inf")]*(n+1)
DP[0]=0
for i in range(n):
  for j in range(m):
    if D[A[j]]<=i+1 and DP[i+1-D[A[j]]]!=float("inf") and DP[i+1-D[A[j]]]+1>=DP[i+1]:
      DP[i+1]=DP[i+1-D[A[j]]]+1
A.sort(reverse=True)
k=DP[n]
ans=""
cur=n
for _ in range(k):
  for j in range(m):
    if DP[cur-D[A[j]]]==DP[cur]-1:
      ans+=str(A[j])
      cur-=D[A[j]]
      break
print(ans)

Submission status: Runtime Error

Solution code:
INF = float('inf')
N,M = map(int,input().split())
A = list(map(int,input().split()))
A.sort(reverse=True)
c = [0,2,5,5,4,5,6,3,7,6]

dp = [-INF]*(N+1)
dp[0] = 0
for a in A:
    if c[a] <= N:
        dp[c[a]] = 1

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

ans = ''
n = N
for a in A:
    while dp[n] == dp[n-c[a]]+1:
        n -= c[a]
        ans = ans + str(a)
print(ans)

Submission status: Runtime Error

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

dp[0] = 0
for i in range(1, n + 1):
    for j in a:
        if i < match[j - 1]:
            continue
        else:
            dp[i] = max(dp[i], dp[i - match[j - 1]] + 1)

num = []
k = n
for i in range(dp[n]):
    for j in a:
        if dp[k - match[j - 1]] == dp[k] - 1:
            num.append(j)
            k -= match[j - 1]
            break
print("".join(map(str, num)))

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
A = sorted(list(map(int,input().split())),reverse = 1)
num = [1,2,3,4,5,6,7,8,9]
match = [2,5,5,4,5,6,3,7,6]
use = []
for a in A:
    use.append([a,match[a-1]])
dp = [0]*(N+5)
#dp[i]:マッチ棒をi本使ったときにつくれる最大の桁数
for u in use:
    dp[u[1]] = 1
for i in range(N+3):
    for u in use:
        if i-u[1] >= 0:
            dp[i] = max(dp[i],dp[i-u[1]]+1)
L = dp[N]
use.sort(key = lambda x:x[1],reverse = 1)
res = []
while len(res) != L:
    for u in use:
        if dp[N-u[1]] == dp[N]-1 and N-u[1] >= 0:
            res.append(str(u[0]))
            N -= u[1]
            break
print("".join(sorted(res,reverse = 1)))

Submission status: Runtime Error

Solution code:
## ABC068-D

## 途中だけど保存用

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

#cost = dict([(1,2),(2,5),(3,5),(4,4),(5,5),(6,6),(7,3),(8,7),(9,6)])
cost = [(1,2),(7,3),(4,4),(5,5),(3,5),(2,5),(9,6),(6,6),(8,7)] ## priority order

## 使う可能性のある数字だけを取り出す
## (5,3,2),(9,6) は上位数だけで十分
## 2個の数字で代用できる場合はそちらを用いる: 4 --> 11
B = []
B_cost = []
for i in range(len(cost)):
  if cost[i][1] in B_cost:
    continue
  elif cost[i][1] == 4 and 2 in B_cost:
    continue
  elif cost[i][1] == 6 and (2 in B_cost or 3 in B_cost):
    continue
  else:
    B.append((cost[i]))
    B_cost.append(cost[i][1])
    
solver = []
n_num = 0
upper_n_num = (N + B[0][1]) // B[0][1]
n_lowcost = upper_n_num
while True:

Submission status: Runtime Error

Solution code:
%%timeit
#inputをローカル用に変更した関数
def input():
    return next(input_sample)

#標準入力をトリプルクオーテーションの中に入力
input_sample=iter("""
10000 9
1 2 3 4 5 6 7 8 9
""".split("\n")[1:-1])

#問題を解く
N,M=map(int,input().split())
A=list((map(int,input().split())))
 
m=[[1,2],[2,5],[3,5],[4,4],[5,5],[6,6],[7,3],[8,7],[9,6]]
B=[]
    
for a in A:
    B.append(m[a-1])

if [5,5] in B:
    if [2,5] in B:
        B.remove([2,5])
    if [3,5] in B:    
        B.remove([3,5])

if [3,5] in B and [2,5] in B:
    B.remove([2,5])

if [7,3] in B:
    if [6,6] in B:
        B.remove([6,6])
    if [9,6] in B:
        B.remove([9,6])
    
if [9,6] in B and [6,6] in B:
    B.remove([6,6])

if [1,2] in B and [7,3] in B:
    if [2,5] in B:
        B.remove([2,5])
    if [3,5] in B:
        B.remove([3,5])
    if [5,5] in B:
        B.remove([5,5])
    if [8,7] in B:
        B.remove([8,7])

if [1,2] in B and ([2,5] in B or [3,5] in B or [5,5] in B) and [8,7] in B:
    B.remove([8,7])
    
if [4,4] in B and [7,3] and [8,7] in B:
    B.remove([8,7])
    
if [1,2] in B and [4,4] in B:
    B.remove([4,4])

maxlist=[""]*(N+10)
 
for i in range(N+1):
    if i!=0 and maxlist[i]=="":
        continue
    else:
        for b in B:
            ans=maxlist[i]+str(b[0])
            _max=maxlist[i+b[1]]
            if i+b[1]>N:
                continue
            if len(ans)<len(_max):
                continue
            elif len(ans)>len(_max):
                maxlist[i+b[1]] = ans
            else:
                for j in range(len(ans)):
                    if ans[j]>_max[j]:
                        maxlist[i+b[1]] = ans
 
print(maxlist[N])

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
A=list((map(int,input().split())))
 
m=[[1,2],[2,5],[3,5],[4,4],[5,5],[6,6],[7,3],[8,7],[9,6]]
B=[]
 
for a in A:
    B.append(m[a-1])
    
maxlist=[0]*(N+10)
 
for i in range(N+1):
    if i!=0 and maxlist[i]==0:
        continue
    else:
        for b in B:
            if int(str(maxlist[i])+str(b[0])) > maxlist[i+b[1]]:
                maxlist[i+b[1]] = concat(maxlist[i],b[0])
 
print(maxlist[N])

Submission status: Runtime Error

Solution code:
N, M = map( int, input().split())
A = list( map( int, input().split()))
Needs = [0,2,5,5,4,5,6,3,7,6]
A.sort(reverse = True)
V = [0]*10
Check = []
for a in A:
    if V[Needs[a]] == 0:
        Check.append(Needs[a])
        V[Needs[a]] = a
Check.sort()
dp = [-100000]*(N+1)
dp[0] = 0

for x in Check:
    if x <= N:
        dp[x] = 1
for i in range(1,N):
    t = dp[i]
    for x in Check:
        if x + i <= N:
            if dp[x+i] < t + 1:
                dp[x+i] = t+1
ans = ""
t = N
W = [0]*10
while t > 0:
    for a in A:
        x = Needs[a]
        if dp[t-x]+1 == dp[t]:
            W[V[x]] += 1
            t -= x
            break
for i in range(9,0,-1):
    ans += str(i)*W[i]
print(ans)

Submission status: Runtime Error

Solution code:
N, M = map( int, input().split())
A = list( map( int, input().split()))
Needs = [0,2,5,5,4,5,6,3,7,6]
A.sort(reverse = True)
V = [0]*10
Check = []
for a in A:
    if V[Needs[a]] == 0:
        Check.append(Needs[a])
        V[Needs[a]] = a
Check.sort()
dp = [-100000]*(N+1)
dp[0] = 0

for x in Check:
    dp[x] = 1
for i in range(1,N):
    t = dp[i]
    for x in Check:
        if x + i <= N:
            if dp[x+i] < t + 1:
                dp[x+i] = t+1
ans = ""
t = N
W = [0]*10
while t > 0:
    for a in A:
        x = Needs[a]
        if dp[t-x]+1 == dp[t]:
            W[V[x]] += 1
            t -= x
            break
for i in range(9,0,-1):
    ans += str(i)*W[i]
print(ans)

Submission status: Runtime Error

Solution code:
N, M = map( int, input().split())
A = list( map( int, input().split()))
Needs = [0,2,5,5,4,5,6,3,7,6]
A.sort(reverse = True)
V = [0]*N
Check = []
for a in A:
    if V[Needs[a]] == 0:
        Check.append(Needs[a])
        V[Needs[a]] = a
Check.sort()
dp = [-100000]*(N+1)
dp[0] = 0

for x in Check:
    dp[x] = 1
for i in range(1,N):
    t = dp[i]
    for x in Check:
        if x + i <= N:
            if dp[x+i] < t + 1:
                dp[x+i] = t+1
ans = ""
t = N
W = [0]*10
while t > 0:
    for a in A:
        x = Needs[a]
        if dp[t-x]+1 == dp[t]:
            W[V[x]] += 1
            t -= x
            break
for i in range(9,0,-1):
    ans += str(i)*W[i]
print(ans)

Submission status: Runtime Error

Solution code:
N, M = map( int, input().split())
A = list( map( int, input().split()))
Needs = [0,2,5,5,4,5,6,3,7,6]
A.sort(reverse = True)
V = [0]*N
Check = []
for a in A:
    if V[Needs[a]] == 0:
        Check.append(Needs[a])
        V[Needs[a]] = a
Check.sort()
dp = [-100000]*(N+1)
dp[0] = 0

for x in Check:
    dp[x] = 1
for i in range(1,N):
    t = dp[i]
    for x in Check:
        if x + i <= N:
            if dp[x+i] < t + 1:
                dp[x+i] = t+1
ans = ""
t = N
W = [0]*10
while t > 0:
    for x in Check:
        if dp[t-x]+1 == dp[t]:
            W[V[x]] += 1
            t -= x
            break
for i in range(9,0,-1):
    ans += str(i)*W[i]
print(ans)

Submission status: Runtime Error

Solution code:
N, M = map( int, input().split())
A = list( map( int, input().split()))
Needs = [0,2,5,5,4,5,6,3,7,6]
A.sort(reverse = True)
V = [0]*N
Check = []
for a in A:
    if V[Needs[a]] == 0:
        Check.append(Needs[a])
        V[Needs[a]] = a
Check.sort()
dp = [-100000]*(N+1)
dp[0] = 0

for x in Check:
    dp[x] = 1
for i in range(1,N):
    t = dp[i]
    if x + i <= N:
        if dp[x+i] < t + 1:
            dp[x+i] = t+1
ans = ""
t = N
W = [0]*10
while t > 0:
    for x in Check:
        if dp[t-x]+1 == dp[t]:
            W[V[x]] += 1
            t -= x
            break
for i in range(9,0,-1):
    ans += str(i)*W[i]
print(ans)

Submission status: Runtime Error

Solution code:
N, M = map( int, input().split())
A = list( map( int, input().split()))
Needs = [0,2,5,5,4,5,6,3,7,6]
A.sort(reverse = True)
V = [0]*N
Check = []
for a in A:
    if V[Needs[a]] == 0:
        Check.append(Needs[a])
        V[Needs[a]] = a
Check.sort()
dp = [-100000]*(N+1)
dp[0] = 0

for x in Check:
    dp[x] = 1
for i in range(1,N):
    t = dp[i]
        if x + i <= N:
            if dp[x+i] < t + 1:
                dp[x+i] = t+1
ans = ""
t = N
W = [0]*10
while t > 0:
    for x in Check:
        if dp[t-x]+1 == dp[t]:
            W[V[x]] += 1
            t -= x
            break
for i in range(9,0,-1):
    ans += str(i)*W[i]
print(ans)

Submission status: Runtime Error

Solution code:
N, M = map( int, input().split())
A = list( map( int, input().split()))
Needs = [0,2,5,5,4,5,6,3,7,6]
A.sort(reverse = True)
V = [0]*N
Check = []
for a in A:
    if V[Needs[a]] == 0:
        Check.append(Needs[a])
        V[Needs[a]] = a
Check.sort()
dp = [-100]*(N+1)
dp[0] = 0

for x in Check:
    dp[x] = 1
for i in range(1,N):
    t = dp[i]
        if x + i <= N:
            if dp[x+i] < t + 1:
                dp[x+i] = t+1
ans = ""
t = N
W = [0]*10
while t > 0:
    for x in Check:
        if dp[t-x]+1 == dp[t]:
            W[V[x]] += 1
            t -= x
            break
for i in range(9,0,-1):
    ans += str(i)*W[i]
print(ans)

Submission status: Runtime Error

Solution code:
N, M = map( int, input().split())
A = list( map( int, input().split()))
Needs = [0,2,5,5,4,5,6,3,7,6]
A.sort(reverse = True)
V = [0]*N
Check = []
for a in A:
    if V[Needs[a]] == 0:
        Check.append(Needs[a])
        V[Needs[a]] = a
Check.sort()
dp = [-100]*(N+1)
dp[0] = 0

for x in Check:
    dp[x] = 1
for i in range(1,N):
    t = dp[i]
    if t == -100:
        continue
    for x in Check:
        if x + i <= N:
            if dp[x+i] < t + 1:
                dp[x+i] = t+1
ans = ""
t = N
W = [0]*10
while t > 0:
    for x in Check:
        if dp[t-x]+1 == dp[t]:
            W[V[x]] += 1
            t -= x
            break
for i in range(9,0,-1):
    ans += str(i)*W[i]
print(ans)

Submission status: Runtime Error

Solution code:
N, M = map( int, input().split())
A = list( map( int, input().split()))
Needs = [0,2,5,5,4,5,6,3,7,6]
A.sort(reverse = True)
V = [0]*N
Check = []
for a in A:
    if V[Needs[a]] == 0:
        Check.append(Needs[a])
        V[Needs[a]] = a
Check.sort()
dp = [-100]*(N+1)
dp[0] = 0

for x in Check:
    dp[x] = 1
for i in range(1,N):
    t = dp[i]
    if t == 0:
        continue
    for x in Check:
        if x + i <= N:
            if dp[x+i] < t + 1:
                dp[x+i] = t+1
ans = ""
t = N
W = [0]*10
while t > 0:
    for x in Check:
        if dp[t-x]+1 == dp[t]:
            W[V[x]] += 1
            t -= x
            break
for i in range(9,0,-1):
    ans += str(i)*W[i]
print(ans)

Submission status: Runtime Error

Solution code:
N, M = map( int, input().split())
A = list( map( int, input().split()))
Needs = [0,2,5,5,4,5,6,3,7,6]
A.sort(reverse = True)
V = [0]*N
Check = []
for a in A:
    if V[Needs[a]] == 0:
        Check.append(Needs[a])
        V[Needs[a]] = a
Check.sort()
dp = [0]*(N+1)
for x in Check:
    dp[x] = 1
for i in range(1,N):
    t = dp[i]
    if t == 0:
        continue
    for x in Check:
        if x + i <= N:
            if dp[x+i] < t + 1:
                dp[x+i] = t+1
now = dp[N]
ans = ""
t = N
W = [0]*10
while t > 0:
    # k += 1
    # if k >= 100:
    #     print(dp,t)
    #     print([i for i in range(N)])
    #     break
    for x in Check:
        if dp[t-x] == 0 and t-x >0:
            continue
        if dp[t-x]+1 == dp[t]:
            W[V[x]] += 1
            t -= x
            break
for i in range(9,0,-1):
    ans += str(i)*W[i]
print(ans)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))
dict = dict(zip([i for i in range(1, 10)], [2,5,5,4,5,6,3,7,6]))
INF = 10 ** (N // 2 + 1)
dp = [-INF for i in range(N + 1)]
for a in A:
    dp[dict[a]] = max(dp[dict[a]] , a)
for i in range(N + 1):
    for j in range(1, 10):
        dp[i] = max(dp[i], dp[i - j] * 10 + dp[j], dp[j] * 10 +dp[i - j])
print(dp[N])

Submission status: Runtime Error

Solution code:
N, M = map(int,input().split())
L = list(map(int,input().split()))
K = [0,2,5,5,4,5,6,3,7,6]
A = sorted([[L[k],K[L[k]]] for k in range(M)])[::-1]
dp = [0 for k in range(N+1)]

for k in range(1,N+1):
    t = -float("inf")
    for j in range(M):
        if k-A[j][1]>=0:
            t = max(t, dp[k-A[j][1]]+1)
    dp[k] = t

ans = ""
keta = dp[N]
match = N
while keta > 0:
    for k in range(M):
        if dp[match-A[k][1]] == keta-1:
            ans += str(A[k][0])
            match -= A[k][1]
            keta -= 1
            break
print(ans)

Submission status: Runtime Error

Solution code:
N, M = map(int,input().split())
L = list(map(int,input().split()))
K = [0,2,5,5,4,5,6,3,7,6]
A = sorted([[L[k],K[L[k]]] for k in range(M)])[::-1]
dp = [0 for k in range(N+1)]

for k in range(1,N+1):
    t = -float("inf")
    for j in range(M):
        if k-A[j][1]>=0:
            t = max(t, dp[k-A[j][1]]+1)
    dp[k] = t

ans = ""
keta = dp[N]
match = N
while keta > 0:
    for k in range(M):
        if dp[match-A[k][1]] == keta-1:
            ans += str(A[k][0])
            match -= A[k][1]
            keta -= 1
            break
print(ans)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)
b = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [0 for _ in range(n + 1)]
INF = 10 ** 9
for i in range(1, n + 1):
    c = [dp[i - b[aj]] for aj in a if i >= b[aj]]
    if len(c) > 0:
        dp[i] = max(c) + 1
    else:
        dp[i] = -INF

x = n
i = 0
ans = ''
while(True):
    for aj in a:
        if dp[x - b[aj]] == dp[n] - i - 1:
            i += 1
            x -= b[aj]
            ans += str(aj)
            break
    if i == dp[n]:
        break
print(ans)

Submission status: Runtime Error

Solution code:
# N = int(input())
# A = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]
# MOD = 10 ** 9 + 7
# メモ化再起
from functools import lru_cache
import sys

sys.setrecursionlimit(10000)

N, M = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
match = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]



@lru_cache(maxsize=1000000)
def f(n):
    maxval = -float('inf')
    for a in A:
        tmp = n - match[a]
        if tmp == 0:
            maxval = max(maxval, a)
        elif tmp > 0:
            maxval = max(maxval, f2(f(n - match[a]) * 10 + a))
    return maxval

@lru_cache(maxsize=1000000)
def f2(n):
    if n < 0:
        return 0
    n = list(str(n))
    n.sort(reverse=True)
    return int("".join(n))

ans = f(N)
print(ans)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import sys

input = sys.stdin.readline

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

def main():
    N, M = [int(e) for e in input().split()]
    A = [int(e) for e in input().split()]

    # N 本で作れる桁の数
    dp = [-1 for _ in range(N+1)]
    dp[0] = 0
    dp[1] = 0
    for i in range(N+1):
        for a in A:
            if i-MATCH_NUM[a] < 0:
                continue
            dp[i] = max(dp[i], dp[i-MATCH_NUM[a]] + 1)

    max_digit_num = dp[N]

    A.sort(reverse=True)

    min_cost = 10
    for a in A:
        if MATCH_NUM[a] < min_cost:
            min_cost = MATCH_NUM[a]

    res = ''
    for _ in range(max_digit_num):
        for a in A:
            if dp[N-MATCH_NUM[a]] == dp[N]-1:
                if N-MATCH_NUM[a] < min_cost and N-MATCH_NUM[a] != 0:
                    continue
                res += str(a)
                N -= MATCH_NUM[a]
                break
    print(res)
main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import sys

input = sys.stdin.readline

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

def main():
    N, M = [int(e) for e in input().split()]
    A = [int(e) for e in input().split()]

    # N 本で作れる桁の数
    dp = [-1 for _ in range(N+1)]
    dp[0] = 0
    dp[1] = 0
    for i in range(N+1):
        for a in A:
            dp[i] = max(dp[i], dp[i-MATCH_NUM[a]] + 1)

    max_digit_num = dp[N]

    A.sort(reverse=True)

    min_cost = 10
    for a in A:
        if MATCH_NUM[a] < min_cost:
            min_cost = MATCH_NUM[a]

    res = ''
    for _ in range(max_digit_num):
        for a in A:
            if dp[N-MATCH_NUM[a]] == dp[N]-1:
                if N-MATCH_NUM[a] <= min_cost and N-MATCH_NUM[a] != 0:
                    continue
                res += str(a)
                N -= MATCH_NUM[a]
                break
    print(res)
main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import sys

input = sys.stdin.readline

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

def main():
    N, M = [int(e) for e in input().split()]
    A = [int(e) for e in input().split()]

    # N 本で作れる桁の数
    dp = [-1 for _ in range(N+1)]
    dp[0] = 0
    dp[1] = 0
    for i in range(N+1):
        for a in A:
            dp[i] = max(dp[i], dp[i-MATCH_NUM[a]] + 1)

    max_digit_num = dp[N]

    A.sort(reverse=True)

    min_cost = 10
    for a in A:
        if MATCH_NUM[a] < min_cost:
            min_cost = MATCH_NUM[a]

    res = ''
    for i in range(max_digit_num):
        for a in A:
            if dp[N-MATCH_NUM[a]] == dp[N]-1:
                if N-MATCH_NUM[a] < min_cost and N-MATCH_NUM[a] != 0:
                    continue
                res += str(a)
                N -= MATCH_NUM[a]
                break
    print(res)
main()

Submission status: Runtime Error

Solution code:
# N = int(input())
# A = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]
# MOD = 10 ** 9 + 7
#

import sys

N, M = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
B = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]

D = dict()
# 1から9の数値:必要なマッチの本数
for a in A:
    D[a] = min(D.get(a, 999), B[a])

L = []
# (必要なマッチの本数, 1～10の数値)
for k, v in D.items():
    L.append((v, k))
L.sort()


# 残りn本のマッチ、現在の値val
# 戻り値：その最大値
def f(n, val):
    if n < 0:
        return 0
    elif n == 0:
        ret = list(str(val))
        ret.sort(reverse=True)
        print("".join(ret))
        sys.exit(0)
        return 0

    ret = 0
    for l in L:
        ret = max(ret, f(n - l[0], val * 10 + l[1]))
    return ret


ans = f(N, 0)

Submission status: Runtime Error

Solution code:
import itertools
from collections import defaultdict

N,M = map(int,input().split())
A = [int(x) for x in input().split()]
L = [None,2,5,5,4,5,6,3,7,6]

l_to_n = [[] for _ in range(10)]
for a in A[1:]:
  l_to_n[L[a]].append(a)
  
l_to_n = [(i,max(x)) for i,x in enumerate(l_to_n) if x]

se = {0} # 1000以下で作れる長さ

for l,_ in l_to_n:
  se = {x+y for x,y in itertools.product(se,range(0,1000,l)) if x+y < 1000}

answer = ''
m_L,x = l_to_n[0]
while N > 100:
  N -= m_L
  answer += str(x)
  
for l,x in l_to_n:
  while N-l in se:
    N -= l
    answer += str(x)
  if N == 0:
    break

answer = ''.join(sorted(answer,reverse=True))

print(answer)

Submission status: Runtime Error

Solution code:
def sub(N, M, As):

    d_cost = {
            "1": 2,
            "2": 5,
            "3": 5,
            "4": 4,
            "5": 5,
            "6": 6,
            "7": 3,
            "8": 7,
            "9": 6,
            }
    
    NINF = -10**6
    dp_table = [NINF for _ in range(N+1)]
    dp_table[0] = 0
    for i in range(N):
        if dp_table[i] < 0:
            continue
        for a in As:
            cost = i + d_cost[a]
            if cost <= N:
                dp_table[cost] = max(dp_table[cost], dp_table[i] + 1)

    Lmax = dp_table[N]

    life = N
    buf = []
    for i in range(Lmax):
        oks = [a for a in As if dp_table[life - d_cost[a]] == dp_table[life] - 1 and life - d_cost[a] >= 0]
        a_selected = max(oks)
        buf.append(a_selected)
        life = life - d_cost[a_selected]
    print("".join(buf))
            

if __name__ == "__main__":
    N, M = [int(e) for e in input().split()]
    As = [e for e in input().split()]
    sub(N, M, As)

Submission status: Runtime Error

Solution code:
def sub(N, M, As):

    d_cost = {
            "1": 2,
            "2": 5,
            "3": 5,
            "4": 4,
            "5": 5,
            "6": 6,
            "7": 3,
            "8": 7,
            "9": 6,
            }
    
    NINF = -10**6
    dp_table = [NINF for _ in range(N+1)]
    dp_table[0] = 0
    for i in range(N):
        for a in As:
            cost = i + d_cost[a]
            if cost <= N:
                dp_table[cost] = max(dp_table[cost], dp_table[i] + 1)

    Lmax = dp_table[N]

    life = N
    buf = []
    for i in range(Lmax):
        oks = [a for a in As if dp_table[life - d_cost[a]] == dp_table[life] - 1 and life - d_cost[a] >= 0]
        a_selected = max(oks)
        buf.append(a_selected)
        life = life - d_cost[a_selected]
    print("".join(buf))
            

if __name__ == "__main__":
    N, M = [int(e) for e in input().split()]
    As = [e for e in input().split()]
    sub(N, M, As)

Submission status: Runtime Error

Solution code:
from functools import lru_cache
def sub():
    N, M = [int(e) for e in input().split()]
    As = [e for e in input().split()]

    d_cost = {
            "1": 2,
            "2": 5,
            "3": 5,
            "4": 4,
            "5": 5,
            "6": 6,
            "7": 3,
            "8": 7,
            "9": 6,
            }
    
    
    NINF = -10**9
    @lru_cache(maxsize=None)   
    def dp(a_life):
        if a_life == 0:
            return 0
        cc = [a_life - d_cost[a] for a in As]
        cc = [c for c in cc if c >= 0]
        if len(cc) == 0:
            return NINF
        buf = [dp(c) + 1 for c in cc]
        return max(buf)
    
    Lmax = dp(N)
    
    life = N
    buf = []
    for i in range(Lmax):
        oks = [a for a in As if dp(life - d_cost[a]) == dp(life) - 1 and life - d_cost[a] >= 0]
        a_selected = max(oks)
        buf.append(a_selected)
        life = life - d_cost[a_selected]
    print("".join(buf))


sub()

Submission status: Runtime Error

Solution code:
from functools import lru_cache
def sub():
    N, M = [int(e) for e in input().split()]
    As = [e for e in input().split()]

    d_cost = {
            "1": 2,
            "2": 5,
            "3": 5,
            "4": 4,
            "5": 5,
            "6": 6,
            "7": 3,
            "8": 7,
            "9": 6,
            }
    
    
    NINF = -10**12
    @lru_cache(maxsize=None)   
    def dp(a_life):
        if a_life == 0:
            return 0
        cc = [a_life - d_cost[a] for a in As]
        cc = [c for c in cc if c >= 0]
        if len(cc) == 0:
            return NINF
        buf = [dp(c) + 1 for c in cc]
        return max(buf)
    
    Lmax = dp(N)
    
    life = N
    buf = []
    for i in range(Lmax):
        oks = [a for a in As if dp(life - d_cost[a]) == Lmax - (i+1)]
        a_selected = max(oks)
        buf.append(a_selected)
        life = life - d_cost[a_selected]
    print("".join(buf))


sub()