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:
n, m = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]

key = {1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6}
#k = [1, 7, 4, 5, 3, 2, 9, 6, 8]

dpi = [-1<<50] * 9 + [0]
def dp(i):
    '''i should be started from 1'''

    ans = []
    for j in a:
        ans.append(dpi[len(dpi) - key[j]] + 1)
    dpi.append(max(ans))

    if i == n:
        return dpi[len(dpi) - 1]
    else:
        return dp(i + 1)

i = dp(1)
a.sort()

s = ''
cur = -1
for j in range(i):
    for k in reversed(a):
        if dpi[cur-key[k]] == dpi[cur] - 1:
            s += str(k)
            cur -= key[k] 
            break
        else:
            continue

print(int(s))

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
A.reverse()
match = [2,5,5,4,5,6,3,7,6]
dp = [0]*(N+1)
for i in range(N+1):
  L = []
  for j in range(M):
    if i-match[A[j]-1] >= 0:
      L.append(dp[i-match[A[j]-1]]+1)
  L.sort()
  if len(L) >= 1:
    dp[i] = L[len(L)-1]
ans = ''
while N > 0:
  for i in range(M):
    if dp[N-match[A[i]-1]] == dp[N]-1:
      if dp[N]-1 != 0:
        ans += str(A[i])
        N -= match[A[i]-1]
        break
      else:
        for k in range(M):
          if match[A[k]-1] == N:
            ans += str(A[k])
            N = 0
            break
print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
length, types = map(int, input().split(" "))
match = [n for n in input().split(" ")]
cost = defaultdict(int)
cost.update({"1":2, "2":5, "3":5, "4":4, "5":5, "6":6, "7":3, "8":7, "9":6})

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

def compare_str(a, b):
    if a == "":
        return b
    elif len(a) == len(b):
        return a if a > b else b
    elif len(a) > len(b):
        return a
    return b
        

for m in match:
    dp[cost[m]] = m

for i in range(length):
    # print(dp, i)
    if dp[i]:
        for m in match:
            if i + cost[m] <= length:
                dp[i + cost[m]] = compare_str(dp[i + cost[m]], dp[i] + m)
print(dp[length])

Submission status: Runtime Error

Solution code:
from collections import defaultdict
length, types = map(int, input().split(" "))
match = [n for n in input().split(" ")]
cost = defaultdict(int)
cost.update({"1":2, "2":5, "3":5, "4":4, "5":5, "6":6, "7":3, "8":7, "9":6})

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

def compare_str(a, b):
    if len(a) == len(b):
        return a if a > b else b
    elif len(a) > len(b):
        return a
    return b
        

for m in match:
    dp[cost[m]] = m

for i in range(length):
    # print(dp, i)
    if dp[i]:
        for m in match:
            if i + cost[m] <= length:
                if dp[i + cost[m]]:
                    dp[i + cost[m]] = compare_str(dp[i + cost[m]], dp[i] + m)
                else:
                    dp[i + cost[m]] = dp[i] + m
print(dp[length])

Submission status: Runtime Error

Solution code:
from collections import defaultdict
length, types = map(int, input().split(" "))
match = [n for n in input().split(" ")]
cost = defaultdict(int)
cost.update({"1":2, "2":5, "3":5, "4":4, "5":5, "6":6, "7":3, "8":7, "9":6})

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

for m in match:
    dp[cost[m]] = str(m)

for i in range(length):
    # print(dp, i)
    if dp[i]:
        for m in match:
            if i + cost[m] <= length:
                if dp[i + cost[m]]:
                    dp[i + cost[m]] = str(max(int(dp[i + cost[m]]), int(dp[i] + m)))
                else:
                    dp[i + cost[m]] = dp[i] + m
print(dp[length])

Submission status: Runtime Error

Solution code:
num_A = {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()
A.reverse()

INF = 10 ** 6
dp = [-INF for i in range(N + 1)]    # get the max digit size using i matches
dp[0] = 0
for i in range(1, N + 1):
    next_num = [Ai for Ai in A if num_A[Ai] <= i]
    if next_num != []:
        dpi_candidate = [dp[i - num_A[next_numi]] + 1
                         for next_numi in next_num]
        dp[i] = max(dpi_candidate)

remain_match = N
ans = "0"
while remain_match > 0:
    for Ai in A:
        if dp[remain_match - num_A[Ai]] == dp[remain_match] - 1:
            ans += str(Ai)
            remain_match -= num_A[Ai]
            break

print(int(ans[1:]))

Submission status: Runtime Error

Solution code:
num_A = {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()
A.reverse()

INF = 10 ** 6
dp = [-INF for i in range(N + 1)]    # get the max digit size using i matches
dp[0] = 0
for i in range(1, N + 1):
    next_num = [Ai for Ai in A if num_A[Ai] <= i]
    if next_num != []:
        dpi_candidate = [dp[i - num_A[next_numi]] + 1
                         for next_numi in next_num]
        dp[i] = max(dpi_candidate)

remain_match = N
ans = ""
while 1:
    for Ai in A:
        if dp[remain_match - num_A[Ai]] == dp[remain_match] - 1:
            ans += str(Ai)
            remain_match -= num_A[Ai]
            break
    if remain_match == 0:
        break
print(int(ans))

Submission status: Runtime Error

Solution code:
num_A = {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()
A.reverse()

INF = 10 ** 6
dp = [-INF for i in range(N + 1)]    # get the max digit size using i matches
dp[0] = 0
for i in range(1, N + 1):
    next_num = [Ai for Ai in A if num_A[Ai] <= i]
    if next_num != []:
        dpi_candidate = [dp[i - num_A[next_numi]] + 1
                         for next_numi in next_num]
        dp[i] = max(dpi_candidate)

remain_match = N
ans = ""
while remain_match > 0:
    for Ai in A:
        if dp[remain_match - num_A[Ai]] == dp[remain_match] - 1:
            ans += str(Ai)
            remain_match -= num_A[Ai]
            break

print(int(ans))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(1000000)

N,M = map(int,input().split())
ma = list(map(int,input().split()))
n = len(a)
ma_map = [ -1, 2, 5, 5, 4, 5, 6, 3, 7, 6 ]
memo = [-1] * 100000

def dp(num):
	if memo[num] != -1: return memo[num]
	if num == 0: return 0

	ret = -1
	for p in ma:
		if 0 <= num - ma_map[p]:
			ret = max(dp(num - ma_map[p]) * 10 + p, ret)

	memo[num] = ret
	return ret

ma.sort()
print(dp(N))

Submission status: Runtime Error

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


def __select_use_num(N: int, A: list) -> list:
    if N == 0:
        return []

    for a in A:
        if N < __MATCH[a]:
            continue

        l = __select_use_num(N-__MATCH[a], A)
        if l is None:
            continue

        return [a] + l

    return None


def match_matching(N: int, M: int, A: list) -> int:
    _A = sorted(A, key=lambda x: __MATCH[x])
    nums = sorted(__select_use_num(N, _A), reverse=True)
    ans = ''.join(map(str, nums))
    return int(ans)


if __name__ == "__main__":
    N, M = [int(s) for s in input().split()]
    A = [int(s) for s in input().split()]

    ans = match_matching(N, M, A)

    print(ans)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

import sys

#          x  1  2  3  4  5  6  7  8  9
num     = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
rev_num = [0, 6, 7, 3, 6, 5, 4, 5, 5, 2]

inf = 10000000000

def main():
    sp = [int(e) for e in input().split(" ")]
    n = sp[0]
    m = sp[1]

    # 使える桁が入る
    A = [int(e) for e in input().split(" ")]

    # 最大桁を求める
    # マッチ数が同じ場合、桁の大きい方で順位づけする
    # 0 <= i < n において、マッチ i 本をちょうど使って作成できる最大の桁を求める
    dp = [0] * (n+1)

    for i in range(1, n+1):
        max = 0
        matched = False
        for j in A:
            if dp[i-num[j]] == -inf or i-num[j] < 0:
                continue
            matched = True
            tmp = dp[i-num[j]] + 1
            if tmp > max:
                max = tmp
        if not matched:
            dp[i] = -inf
        else:
            dp[i] = max

    A.sort()
    A.reverse()

    # print(dp[n], dp)

    n2 = n;
    while n2 != 0:
        # print("--- n = {} --".format(n2))
        for e in A:
            # print("e = {}, dp[n-num(e)] = {}, dp[n]-1 = {}".format(e, dp[n2-num[e]], dp[n2]-1))
            if dp[n2-num[e]] == dp[n2]-1:
                # print('select = {} ({})'.format(e, num[e]))
                n2 -= num[e]
                print(e, end="")
                break
    print()

main()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000000000)
 
ma_map = [ -1, 2, 5, 5, 4, 5, 6, 3, 7, 6 ]
N, M = (int(i) for i in input().split())
ma = list(int(i) for i in input().split())
memo = [-1] * 100000
 
def dfs(num):
	if memo[num] != -1: return memo[num]
	if num == 0: return 0
 
	ret = -1
	for p in ma:
		if 0 <= num - ma_map[p]:
			ret = max(dfs(num - ma_map[p]) * 10 + p, ret)
 
	memo[num] = ret
	return ret
 
ma.sort()
print(dfs(N))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(1000000)

ma_map = [ -1, 2, 5, 5, 4, 5, 6, 3, 7, 6 ]
N, M = (int(i) for i in input().split())
ma = list(int(i) for i in input().split())
memo = [-1] * 100000

def dfs(num):
	if memo[num] != -1: return memo[num]
	if num == 0: return 0

	ret = -1
	for p in ma:
		if 0 <= num - ma_map[p]:
			d = dfs(num - ma_map[p])
			if d == -1: continue
			ret = max(dfs(num - ma_map[p]) * 10 + p, ret)

	memo[num] = ret
	return ret

print(ma_map[2])
ma.sort()
println("{}".format(dfs(N)))

Submission status: Runtime Error

Solution code:
ma_map = [ -1, 2, 5, 5, 4, 5, 6, 3, 7, 6 ]
N, M = (int(i) for i in input().split())
ma = list(int(i) for i in input().split())
memo = [-1] * 100000

def dfs(num):
	if memo[num] != -1: return memo[num]
	if num == 0: return 0

	ret = -1
	for p in ma:
		if 0 <= num - ma_map[p]:
			d = dfs(num - ma_map[p])
			if d == -1: continue
			ret = max(dfs(num - ma_map[p]) * 10 + p, ret)

	memo[num] = ret
	return ret

print(ma_map[2])
ma.sort()
print(dfs(N))

Submission status: Runtime Error

Solution code:
ma_map = [ -1, 2, 5, 5, 4, 5, 6, 3, 7, 6 ]
N, M = (int(i) for i in input().split())
ma = list(int(i) for i in input().split())
memo = [-1] * 100000

def dfs(num):
	if memo[num] != -1: return memo[num]
	if num == 0: return 0

	ret = -1
	for p in ma:
		if 0 <= num - ma_map[p]:
			ret = max(dfs(num - ma_map[p]) * 10 + p, ret)

	memo[num] = ret
	return ret

print(ma_map[2])
ma.sort()
print(dfs(N))

Submission status: Runtime Error

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

dp = [-1 for i in range(N + 1)]

cost = []
for i in range(M):
    cost.append([A[i], match[A[i]]])

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

tmp = 0 #使ったマッチの数
res = ''
cost.sort(key=lambda x: x[0], reverse=True)
for i in range(dp[N]):
    for j in range(M):
        if dp[N - cost[j][1] - tmp] == dp[N - tmp] - 1:
            res = res + str(cost[j][0])
            tmp += cost[j][1]
            break
            
print(res)

Submission status: Runtime Error

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

n_use = dict(zip(range(1, 10), [2, 5, 5, 4, 5, 6, 3, 7, 6]))
dp = [(0, 0)]*(n+1) # digit and produced number
for a_j in a:
    dp[n_use[a_j]] = (1, max(dp[n_use[a_j]][1], a_j))
for i in range(1, n+1):
    for a_j in a:
        d_cur, path_cur = dp[i]
        i_prev = i - n_use[a_j]
        if i_prev < 0:
            continue
        if dp[i_prev][0] == 0:
            continue
        else:
            d_prev, path_prev = dp[i_prev]
            path_new = a_j*pow(10, d_prev) + path_prev
            if path_new > path_cur:
                dp[i] = (d_prev+1, path_new)
            
# print(dp)
print(dp[-1][1])

Submission status: Runtime Error

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

n_use = dict(zip(range(1, 10), [2, 5, 5, 4, 5, 6, 3, 7, 6]))
dp = ['']*(n+1)
for a_i in a:
    dp[n_use[a_i]] = str(a_i)
for i in range(1, n+1):
    for a_j in a:
        path_cur = '0' if dp[i] == '' else dp[i]
        i_prev = i - n_use[a_j]
        if i_prev < 0:
            continue
        else:
            path_prev = dp[i_prev]
            if len(path_prev) == 0:
                continue
            path_new = str(a_j)+path_prev
            dp[i] = str(max(int(path_cur), int(path_new)))
            
# print(dp)
print(dp[-1])

Submission status: Runtime Error

Solution code:
m = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
N, M = map(int, input().split())
A = list(map(int, input().split()))
dp = [0] + [-N] * N
for x in range(1, N + 1):
    mx = -N
    for j in range(M):
        num = x - m[A[j]]
        if num >= 0:
            if mx < dp[num] + 1:
                mx = dp[num] + 1
    if mx < 0:
        dp[x] = -N
    else:
        dp[x] = mx

A.sort(reverse=True)
nd = dp[N]
n = N
for i in range(N):
    for a in A:
        if dp[n - m[a]] == nd - 1:
            nd -= 1
            n -= m[a]
            print(a, end="")
            break
print()

Submission status: Runtime Error

Solution code:
n,m=list(map(int,input().split()))
arr=list(map(int,input().split()))
dic={1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}
dp=[0]*(n+1)
for num in arr:
    dp[dic[num]]=num
    
for i in range(2,n+1):
    currentmax=0
    current=dp[i]
    for num in arr:
        if i>dic[num]:
            if currentmax<dp[i-dic[num]]:
                currentmax=dp[i-dic[num]]
                current=num
    pref=str(current)
    if currentmax==0:
        suff=str('')
    else:
        suff=str(currentmax)
    dp[i]=int(suff+pref)
print(dp[n])

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
A = list(map(int,input().split()))
max_sum = 0
def return_num(x):
    x_num = [0,2,5,5,4,5,6,3,7,6]
    return x_num[x]
def dp(x):
    if x==0:
        return ""
    elif x<0:
        return "-1"
    string_list = []
    for i in range(M):
        string_list.append(dp(x-return_num(A[i]))+str(A[i]))
    return str(max([int(i) for i in string_list]))
print(dp(N))

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))
INF = 10**(10**4)
COST = [INF,2,5,5,4,5,6,3,7,6]

min_cost = min(list(map(lambda a: COST[a], A)))
max_digits = N // min_cost

def dfs(n, digits):
    if digits * min_cost > n:
        return -INF
    if digits == 0:
        if n == 0:
            return 0
        else:
            return -INF
    elif digits < 0:
        return - INF
    results = []
    for a in A:
        res = a * 10 ** (digits - 1) + dfs(n-COST[a], digits-1)
        results.append(res)
    return max(results)

print(dfs(N, max_digits))

Submission status: Runtime Error

Solution code:
n, m = [int(i) for i in input().split()]
am = sorted([int(i) for i in input().split()],reverse=True)
c = [2, 5, 5, 4, 5, 6, 3, 7, 6]

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

for i in range(n+1):
    max_tmp = -float("inf")
    for j in am:
        if i-c[j-1]>=0:
            max_tmp = max(dp[i-c[j-1]]+1, max_tmp)
    dp[i] = max(dp[i],max_tmp)


flag = True
result = 0
tmp_n = n
x = 0
y = x
while flag==True:
    if tmp_n-c[am[x]-1] >= 0 and dp[tmp_n-c[am[x]-1]] == dp[tmp_n] - 1:
        result = result * 10 + am[x]
        tmp_n = tmp_n-c[am[x]-1]
        x = 0
    elif tmp_n-c[am[x]-1]<0:
        x = x + 1
        if x == len(am):
            one = result%10
            result = int((result-one)/10)
            tmp_n +=c[one-1]
            x = am.index(one)+1

    elif x < len(am)-1:
         x+=1

    if tmp_n==0:
        break


print(result)

Submission status: Runtime Error

Solution code:
n, m = [int(i) for i in input().split()]
am = sorted([int(i) for i in input().split()],reverse=True)
c = [2, 5, 5, 4, 5, 6, 3, 7, 6]

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

for i in range(n+1):
    max_tmp = -float("inf")
    for j in am:
        if i-c[j-1]>=0:
            max_tmp = max(dp[i-c[j-1]]+1, max_tmp)
    dp[i] = max(dp[i],max_tmp)



flag = True
result = 0
tmp_n = n
x = 0
y = x
while flag==True:

    if tmp_n-c[am[x]-1] >= 0 and dp[tmp_n-c[am[x]-1]] == dp[tmp_n] - 1:
        result = result * 10 + am[x]
        tmp_n = tmp_n-c[am[x]-1]
        x = 0
    elif tmp_n-c[am[x]-1]<0:
        x = x + 1
        if x == len(am):
            one = result%10
            result = int((result-one)/10)
            tmp_n +=c[one-1]
            x = am.index(one)+1

    elif x < len(am):
         x+=1

    if tmp_n==0:
        break


print(result)

Submission status: Runtime Error

Solution code:
import sys
readline = sys.stdin.readline
write = sys.stdout.write

def num(key):
    if key == 1:
        return 2
    elif key == 7:
        return 3
    elif key == 4:
        return 4
    elif key == 9 or key == 6:
        return 6
    elif key == 8:
        return 7
    else:
        return 5

N, M, = readline().split()
N = int(N)
M = int(M)
A = list(map(int, readline().split()))
A.sort(reverse = True)
dp = [-float('inf'),] *(N+1)
dp[0] = 0
for i in range(1, N+1):
    temp = []
    for j in range(M):
        if i - num(A[j]) >= 0:
            temp.append(dp[i-num(A[j])] + 1)
    if len(temp) > 0:
        dp[i] = max(temp)

digit = dp[N]
ans = []
for i in range(digit):
    for j in range(M):
        if dp[N-num(A[j])] == dp[N] - 1 and N - num(A[j]) >= 0:
            ans.append(A[j])
            N = N - num(A[j])
            break
for i in range(digit):
    write(str(ans[i]))
write("\n")

Submission status: Runtime Error

Solution code:
import sys
readline = sys.stdin.readline
write = sys.stdout.write

def num(key):
    if key == 1:
        return 2
    elif key == 7:
        return 3
    elif key == 4:
        return 4
    elif key == 9 or key == 6:
        return 6
    elif key == 8:
        return 7
    else:
        return 5

N, M, = readline().split()
N = int(N)
M = int(M)
A = list(map(int, readline().split()))
A.sort(reverse = True)
dp = [-float('inf'),] *(N+1)
dp[0] = 0
for i in range(1, N+1):
    temp = []
    for j in range(M):
        if i - num(A[j]) >= 0:
            temp.append(dp[i-num(A[j])] + 1)
    if len(temp) > 0:
        dp[i] = max(temp)

digit = dp[N]
ans = [0,] *(digit)
for i in range(digit):
    for j in range(M):
        if dp[N-num(A[j])] == dp[N] - 1:
            ans[i] = A[j]
            N = N - num(A[j])
            break
for i in range(digit):
    write(str(ans[i]))
write("\n")

Submission status: Runtime Error

Solution code:
import sys
readline = sys.stdin.readline
write = sys.stdout.write

def num(key):
    if key == 1:
        return 2
    elif key == 7:
        return 3
    elif key == 4:
        return 4
    elif key == 9 or key == 6:
        return 6
    elif key == 8:
        return 7
    else:
        return 5

N, M, = readline().split()
N = int(N)
M = int(M)
A = list(map(int, readline().split()))
A.sort(reverse = True)
dp = [-float('inf'),] *(N+1)
dp[0] = 0
for i in range(A[-1], N+1):
    temp = []
    for j in range(M):
        if i - num(A[j]) >= 0:
            temp.append(dp[i-num(A[j])] + 1)
    if len(temp) > 0:
        dp[i] = max(temp)

digit = dp[N]
ans = [0,] *(digit)
for i in range(digit):
    for j in range(M):
        if dp[N-num(A[j])] == dp[N] - 1:
            ans[i] = A[j]
            N = N - num(A[j])
            break
for i in range(digit):
    write(str(ans[i]))
write("\n")

Submission status: Runtime Error

Solution code:
import numpy as np

INF = 1000000000000000000


define = np.array([0,2,5,5,4,5,6,3,7,6])
N,M = map(int,input().split())
tA = list(map(int,input().split()))
dp = [-INF] * (N+1)
dp[0] = 0

A = define[tA]

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

max = 0
dict = {}
for i,v in zip(A,tA):
    dict[i] = v
    
dict = sorted(dict.items(), key=lambda x: -x[1])
ans = ''

tmpN = N

while tmpN > 0:
    for (ma, num) in dict:
        if tmpN - ma < 0:
            continue
        if dp[tmpN] == dp[tmpN-ma] + 1:
            ans += str(num)
            tmpN -= ma
            break
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np

define = np.array([0,2,5,5,4,5,6,3,7,6])
N,M = map(int,input().split())
tA = list(map(int,input().split()))
dp = [-1] * (N+1)
dp[0] = 0

A = define[tA]

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

max = 0
dict = {}
for i,v in zip(A,tA):
    dict[i] = v
    
dict = sorted(dict.items(), key=lambda x: -x[1])
ans = ''

tmpN = N

while tmpN > 1:
    for (ma, num) in dict:
        if tmpN - ma < 0:
            continue
        if dp[tmpN] == dp[tmpN-ma] + 1:
            ans += str(num)
            tmpN -= ma
            break
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np

define = np.array([0,2,5,5,4,5,6,3,7,6])
N,M = map(int,input().split())
tA = list(map(int,input().split()))
dp = [-1] * (N+1)
dp[0] = 0

A = define[tA]

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

max = 0
dict = {}
for i,v in zip(A,tA):
    dict[i] = v
    
dict = sorted(dict.items(), key=lambda x: -x[1])
ans = ''

tmpN = N

while tmpN > 0:
    for (ma, num) in dict:
        if tmpN - ma < 0:
            continue
        if dp[tmpN] == dp[tmpN-ma] + 1:
            ans += str(num)
            tmpN -= ma
            break
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np

define = np.array([0,2,5,5,4,5,6,3,7,6])
N,M = map(int,input().split())
tA = list(map(int,input().split()))
dp = [0] * (N+1)

A = define[tA]

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

max = 0
dict = {}
for i,v in zip(A,tA):
    dict[i] = v
    
dict = sorted(dict.items(), key=lambda x: -x[1])
ans = ''

tmpN = N

while tmpN > 0:
    for (k,v) in dict:
        if dp[tmpN - k] == dp[tmpN] -1:
            if dp[N] - 1 == len(ans):
                if tmpN - k == 0:
                    ans = ans + str(v)
                    tmpN = tmpN - k
                    break 
            else:
                ans = ans + str(v)
                tmpN = tmpN - k
                break 

print(ans)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
num = [0,2,5,5,4,5,6,3,7,6]
#      0,1,2,3,4,5,6,7,8,9
n,m = map(int, input().split())
al = list(map(int, input().split()))

INF = 10**18
dp = [-INF for _ in range(n+1)]
dp[0] = 0

for i in range(1,n+1):
    for a in al:
        if i-num[a]>=0:
            dp[i] = max(dp[i], dp[i-num[a]]+1)

res = []
al.sort(reverse=True)

while n>0:
    for a in al:
        if dp[n-num[a]]==dp[n]-1:
            res.append(str(a))
            n -= num[a]
            break

print("".join(res))

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))
B = [6,2,5,5,4,5,6,3,7,6] # B[i]がiを作るのに必要なマッチ棒の数

C = []
for a in A:
  C.append(B[a])
  
dp = [0] * (N+1)

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

X = max(dp)
pos = N
ans = ""
#print(X)
for cnt in range(X):
  for i in range(9,0,-1):
    if i in A:
      if dp[pos] != dp[pos-B[i]] + 1:
        continue
      if cnt == X-1 and pos - B[i] != 0:
        continue
      pos = pos - B[i]
      ans = ans + str(i)
      break
      
print(ans)

Submission status: Runtime Error

Solution code:
import sys

d=[0,2,5,5,4,5,6,3,7,6]
b=[]

n = map(int, raw_input().split())
a = map(int, raw_input().split())

for x in a:
    b.append(d[x])

def max_num(x, a, b):
    results=[]
    max=0
    for z, y in enumerate(b):
	if x==y:
            results.append([a[z], [a[z]]])
        elif x>y:
            if max_num(x-y, a, b)!=None:
                t=0
                result=max_num(x-y, a, b)
                result[1].append(a[z])
                result[1].sort()
                for num, res in enumerate(result[1]):
                    t+=res*(10**num)
                results.append([t, result[1]])
            else:
                continue
    if results==[]:
        return
    results.sort()
    results.reverse()
    return results[0][0], results[0][1]

print(max_num(n[0], a, b)[0])

Submission status: Runtime Error

Solution code:
inf = float("inf")
N, M = map(int, input().split())
A = map(int, input().split())
C = [2, 5, 5, 4, 5, 6, 3, 7, 6]
costs = {m: C[m - 1] for m in A}
dp = [0]
for i in range(1, N + 1):
    dp.append(
        max([dp[i - c] if i - c >= 0 else -inf for c in costs.values()]) + 1)

digits = list(costs.keys())
digits = sorted(digits, reverse=True)
num = N
result = []
for _ in range(dp[N]):
    for digit in digits:
        if dp[num - costs[digit]] != -inf and dp[num - costs[digit]] == dp[num] - 1:
            result.append(str(digit))
            num -= costs[digit]
            break
print("".join(result))

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
As = list(map(int, input().split()))
 
def num(i):
  return [2, 5, 5, 4, 5, 6, 3, 7, 6][i-1]
 
d = [0] + [-1] * (N + 1)

for i in range(1, N+1):
  d[i] = max(d[i - num(A)] * 10 + A for A in As)

print(d[N])

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
As = [int(input()) for i in range(M)]
 
def num(i):
  m = [2, 5, 5, 4, 5, 6, 6, 3, 7, 6]
  return m[i + 1]
 
d = [0] + [-1] * (N * 10)
for i in range(N+1):
  d[i] = max(d[i - num(A)] * 10 + A for A in As)

print(d[N])

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
As = [int(input()) for i in range(M)]
 
def num(i):
  m = [2, 5, 5, 4, 5, 6, 6, 3, 7, 6]
  return m[i + 1]
 
d = [0] + [-1] * (N + 1)
for i in range(N+1):
  d[i] = max([d[i - num(A)] * 10 + A for A in As])

print(d[N])

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
As = [int(input()) for i in range(M)]

def num(i):
  m = [2, 5, 5, 4, 5, 6, 6, 3, 7, 6]
  return m[i + 1]

d = [0] + [-1] * (N + 1)
for i in range(N+1):
  d[i] = max(d[i - num(A)] * 10 + A for A in As)

print(d[N])

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
As = [int(input()) for i in range(M)]

def num(i):
  m = [2, 5, 5, 4, 5, 6, 6, 3, 7, 6]
  return m[i + 1]

d = [-1] * (N + 1)
for i in range(N+1):
  d[i] = max(d[i - num(A)] * 10 + A for A in As)

print(d[N])

Submission status: Runtime Error

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

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

memo = [ ["-1"]*N  for _ in range((10**4)//2 + 1) ]
def dfs(dig,num):
    if memo[dig][num] != "-1":
        return memo[dig][num]

    returnSet = []
    for a in A:
        if n[a-1] + num < N:
            ret = dfs(dig+1,num+n[a-1])
            if ret == "-1":
                continue
            else:
                returnSet.append(str(a)+ret)
        elif n[a-1] + num == N:
            returnSet.append(str(a))
    
    if returnSet == []:
        return "-1"
    memo[dig][num] = max(returnSet,key=lambda x: (len(x),x))
    return memo[dig][num]

print(dfs(0,0))

Submission status: Runtime Error

Solution code:
N, M = [int(x) for x in input().split()]
a = sorted([int(x) for x in input().split()])
INF = 10**9

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

keta = [-INF for _ in range(N+1)]
keta[0] = 0
for i in range(1, N+1):
    cand = [keta[i-num[aa]] for aa in a if i-num[aa] >= 0]
    if len(cand) > 0:
        keta[i] = max(cand) + 1

n = N
ans = ""
while n > 0:
    cand = [aa for aa in a if keta[n]-1 == keta[n-num[aa]]]
    if len(cand) > 0:
        ans += str(max(cand))
        n = n - num[max(cand)]
print(ans)

Submission status: Runtime Error

Solution code:
#わからんテスト
import copy

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

t = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
L = {}
for i in A:
  if t[i] in L:
    if L[t[i]] < i:
      L[t[i]] = i
  else:
    L[t[i]] = i

dp = [[0 for j in range(10)] for i in range(N)]
for i in L.items():
  dp[i[0] - 1][i[1]] = 1

Submission status: Runtime Error

Solution code:
#わからんテスト
import copy

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

t = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
L = {}
for i in A:
  if t[i] in L:
    if L[t[i]] < i:
      L[t[i]] = i
  else:
    L[t[i]] = i

dp = [[0 for j in range(10)] for i in range(N)]
for i in L.items():
  dp[i[0] - 1][i[1]] = 1
for i in range(N):
  if max(dp[i]) == 0:
    continue
  for j in L.items():
    k = i + j[0]
    if k < N:
      t = copy.deepcopy(dp[i])
      t[j[1]] += 1
      if sum(t) > sum(dp[k]):
        dp[k] = t
      else:
        for ii in range(9, 0, -1):
          if t[ii] > dp[k][ii]:
            dp[k] = t
            break
          elif t[ii] < dp[k][ii]:
            break

Submission status: Runtime Error

Solution code:
import copy

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

t = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
L = {}
for i in A:
  if t[i] in L:
    if L[t[i]] < i:
      L[t[i]] = i
  else:
    L[t[i]] = i
  
dp = [[0 for j in range(10)] for i in range(N)]
for i in L.items():
  dp[i[0] - 1][i[1]] = 1
for i in range(N):
  if max(dp[i]) == 0:
    continue
  for j in L.items():
    k = i + j[0]
    if k < N:
      t = copy.deepcopy(dp[i])
      t[j[1]] += 1
      if sum(t) > sum(dp[k]):
        tt = dp[k]
        dp[k] = t
        del tt
      else:
        for ii in range(9, 0, -1):
          if t[ii] > dp[k][ii]:
            tt = dp[k]
            dp[k] = t
            del tt
            break
          elif t[ii] < dp[k][ii]:
            break
          
t = dp[-1]
Ans = ""
for i in range(9, 0, -1):
  for j in range(t[i]):
    Ans += str(i)
    
print(Ans)