Problem:


Score : 400 points

Problem Statement

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

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

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

Constraints

All values in input are integers.

2 \leq N \leq 10^4

1 \leq M \leq 9

1 \leq A_i \leq 9

A_i are all different.

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

Input

Input is given from Standard Input in the following format:

N M
A_1 A_2 ... A_M

Output

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

Sample Input 1

20 4
3 7 8 4

Sample Output 1

777773

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

Sample Input 2

101 9
9 8 7 6 5 4 3 2 1

Sample Output 2

71111111111111111111111111111111111111111111111111

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

Sample Input 3

15 3
5 4 6

Sample Output 3

654



Sample input:
20 4
3 7 8 4


Sample output:
777773

Submission status: Time Limit Exceeded

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

HUGE = 10**6

COST = [HUGE,2,5,5,4,5,6,3,7,6]

def better(s1, s2):
    if s1 is None:
        return s2
    if s2 is None:
        return s1
    if len(s1) == len(s2):
        return max(s1, s2)
    else:
        return max(s1, s2, key=len)

from functools import lru_cache
@lru_cache(maxsize=None)
def rec(remain, num):
    if num == 0:
        return '' if remain==0 else None
    ans = None
    numstr = ''
    for i in range(0, remain+1, COST[num]):
        tmp = rec(remain -i, num-1)
        if tmp is not None:
            ans = better(ans, numstr + tmp)
        numstr += str(num)
    return ans

for i in range(1, 9+1):
    if i not in A:
        COST[i] = HUGE

print(rec(N, 9))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


def solve(N: int, M: int, A: "List[int]"):
    cs = [0, 2 , 5 , 5 , 4 , 5 , 6 , 3 , 7 , 6 ]
    dp = [[-float('inf')] * (N + 1) for _ in range(N // 2 + 1)]
    for i in range(len(dp)):
        dp[i][0] = 0

    for i in range(len(dp) - 1):
        for j in range(len(dp[i])):
            for a in A:
                c = cs[a]
                if j + c <= N:
                    dp[i+1][j + c] = max(dp[i+1][j + c], 10 * dp[i][j] + a)
    return dp[-1][N]


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [ int(next(tokens)) for _ in range(M) ]  # type: "List[int]"
    result = solve(N, M, A)
    print(result)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

dp=[ None for i in range(N+1) ] 
dp[0]=""


for i in range(N):
	if dp[i] is not None:
		for a in A:
			match_cnt=match[a]
			if 0<=i+match_cnt<=N:
				if dp[i+match_cnt] is None:
					dp[i+match_cnt]=dp[i]+str(a)
				else:
					if int(dp[i+match_cnt]) < int( dp[i]+str(a) ):
						dp[i+match_cnt]=dp[i]+str(a)				

print dp[N]

Submission status: Time Limit Exceeded

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

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

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


dp=[ None for i in range(N+1) ] 
dp[0]=""


for i in range(N):
	if dp[i] is not None:
		for a in A:
			match_cnt=match[a]
			if 0<=i+match_cnt<=N:
				if dp[i+match_cnt] is None:
					dp[i+match_cnt]=dp[i]+str(a)
				else:
					if int(dp[i+match_cnt]) < int( dp[i]+str(a) ):
						dp[i+match_cnt]=dp[i]+str(a)				

print dp[N]

Submission status: Time Limit Exceeded

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

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

T=[(1,2),(2,5),(3,5),(4,4),(5,5),(6,6),(7,3),(8,7),(9,6)]

P=[]
for i in A: P.append(T[i-1])

dp=[ None for i in range(N+1) ] 
dp[0]=""

for i in range(N+1):
	for a,match_cnt in P:
		if 0<=i-match_cnt:
			dp_src=dp[i-match_cnt]  #dpの遷移元
			if dp_src is not None:
				if dp[i] is None:
					dp[i]=dp_src+str(a)
				else:
					if int(dp[i])<int( dp_src+str(a) ):
						dp[i]=dp_src+str(a)	
print dp[N]

Submission status: Time Limit Exceeded

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

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

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

dp=[ None for i in range(N+1) ] 
dp[0]=""

for i in range(N+1):
	for a in A:
		match_cnt=match[a]
		if 0<=i-match_cnt:
			dp_src=dp[i-match_cnt]  #dpの遷移元
			if dp_src is not None:
				if dp[i] is None:
					dp[i]=dp_src+str(a)
				else:
					if int(dp[i])<int( dp_src+str(a) ):
						dp[i]=dp_src+str(a)	
print dp[N]

Submission status: Time Limit Exceeded

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

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

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

dp=[ None for i in range(N+1) ] 
dp[0]=""

for i in range(N+1):
	for a in A:
		match_cnt=match[a]
		if 0<=i-match_cnt and dp[i-match_cnt] is not None:
			if dp[i] is None:
				dp[i]=dp[i-match_cnt]+str(a)
			else:
				if int(dp[i])<int( dp[i-match_cnt]+str(a) ):
					dp[i]=dp[i-match_cnt]+str(a)
				
print dp[N]

Submission status: Time Limit Exceeded

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

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

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

#1桁の最小マッチ本数は2本（=1）なので、桁数の最大はN/2
keta=N/2	

dp=[ {} for i in range(keta+1) ] 
dp[0][0]=""

for i in range(keta):
	for j, num in dp[i].items():
		for a in A:
			match_cnt=match[a]
			if j+match_cnt  in dp[i+1]:
				dp[i+1][ j+match_cnt]= max ( dp[i+1][ j+match_cnt], dp[i][j]+str(a) )
			else:
				dp[i+1][ j+match_cnt]=dp[i][j]+str(a)		


for i in range(keta,-1,-1):
	if N in dp[i]:
		print dp[i][N]
		break

Submission status: Time Limit Exceeded

Solution code:
if __name__ == "__main__":
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    cost = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
    Num = [0] * (N+10)

    Num[0] = 0
    for i in range(1, N+1):
        L = [0]
        for idx in A:
            if i - cost[idx] < 0:
                continue
            elif i == cost[idx]:
                L.append(idx)
            elif Num[i - cost[idx]] != 0:
                l = list(str(Num[i - cost[idx]])) + [str(idx)]
                l.sort(reverse = 1)
                L.append(int("".join(l)))
            else:
                continue
            Num[i] = max(L)

    print(Num[N])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000)

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

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

# Aの各要素の画数
count_list = [num_dict[a] for a in A]

# 最小の画数
min_matches = min(count_list)

# 画数の最小の値のうち最大の数値
min_num_list = []
[min_num_list.append(a) for a in A if num_dict[a] == min_matches]
min_num = max(min_num_list)


# 数値とあまり消化数のペア
A.sort(reverse=True)
res = {a: num_dict[a]-min_matches for a in A}


def dfs(nums, target, num_count):
    if len(nums) > num_count:
        return None

    if target > 0:
        for a in A:
            ret = dfs(nums+[a], target-res[a], num_count)
            if ret is not None:
                return ret
        return None
    elif target == 0:
        return nums
    else:
        return None


for num_count in range(N//min_matches, 0, -1):
    # あまりの本数
    mod = N - min_matches*num_count

    # あまりをどう分配するか(DFS)
    share = dfs([], mod, num_count)
    if share is not None:
        out_list = sorted([min_num]*(num_count-len(share))+share, reverse=True)
        out_list = [str(item) for item in out_list]
        print(''.join(out_list))
        break

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000)

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

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

# Aの各要素の画数
count_list = [num_dict[a] for a in A]

# 最小の画数
min_matches = min(count_list)

# 画数の最小の値のうち最大の数値
min_num_list = []
[min_num_list.append(a) for a in A if num_dict[a] == min_matches]
min_num = max(min_num_list)


# 数値とあまり消化数のペア
A.sort(reverse=True)
res = {a: num_dict[a]-min_matches for a in A}


def dfs(nums, target, num_count):
    if len(nums) > num_count:
        return None
    if target == 0:
        return nums
    elif target < 0:
        return None
    else:
        for a in A:
            ret = dfs(nums+[a], target-res[a], num_count)
            if ret is not None:
                return ret
        return None


for num_count in range(N//min_matches, 0, -1):
    # あまりの本数
    mod = N - min_matches*num_count

    # あまりをどう分配するか(DFS)
    share = dfs([], mod, num_count)
    if share is not None:
        out_list = sorted([min_num]*(num_count-len(share))+share, reverse=True)
        out_list = [str(item) for item in out_list]
        print(''.join(out_list))
        break

Submission status: Time Limit Exceeded

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

numbers = {'1': 2, '2': 5, '3': 5, '4': 4, '5': 5, '6': 6, '7': 3, '8': 7, '9': 6}
cand = {a: numbers[a] for a in A}
dp = {i: '-1' for i in range(N+1)}
dp[0] = ''
for i in range(N+1):
    for a in A:
        if i+cand[a] <= N:
            dp[i+cand[a]] = str(max(int(dp[i+cand[a]]), int(dp[i] + a)))
print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
a = sorted(list(map(int,input().split())), reverse=True)
match = [[0,0], [1,2], [2,5], [3,5], [4,4], [5,5], [6,6], [7,3], [8,7], [9,6]]

value = []
cost = []
for i in range(len(a)):
        value.append(a[i])
        cost.append(match[a[i]][1])

dp = [-1]*(n+1)
dp[0] = ""
for i in range(1,n+1):
    for j in range(len(value)):
        tmp_dp_i = 0
        if i - cost[j] >= 0:
            if i - cost[j] == 0 or (i - cost[j] > 0 and dp[i - cost[j]] != -1):
                tmp_dp_i = str(value[j]) + dp[i-cost[j]]
                tmp_dp_i = int(tmp_dp_i)
                if int(dp[i]) < tmp_dp_i:
                    dp[i] = str(tmp_dp_i)
print(dp[n])

Submission status: Time Limit Exceeded

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

import sys
INT_MIN = sys.maxsize * -1
match = [-100,2,5,5,4,5,6,3,7,6]
CHOICES = []
for i in A:
    if (i == 6) and (9 in A):
        continue
    if (i == 3) and (5 in A):
        continue
    if (i == 2) and (3 in A or 5 in A):
        continue
    CHOICES.append([i, match[i]])
CHOICES.sort(reverse=True)

ans = [0]
#print(CHOICES)
for i in range(1,N+1):
    ans.append(INT_MIN)
    for c in CHOICES:
        if  i - c[1] == 0:
            ans[i] = max(ans[i], int(str(c[0])))
        elif i - c[1] >= 0 and ans[i - c[1]] != INT_MIN:
            ans[i] = max(ans[i], int(str(c[0]) + str(ans[i - c[1]])))

print(ans[N])

Submission status: Time Limit Exceeded

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

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

memo = [-1] * (N + 1)
memo[N] = 0
while 1:
    next_memo = [-1] * (N + 1)
    next_memo[0] = memo[0]
    fin = True
    for i in range(N, 0, -1):
        if memo[i] < 0: continue

        for j in range(1, 10):
            if not j in A: continue
            idx = i - V[j]
            if idx >= 0:
                next_memo[idx] = max(next_memo[idx], memo[i] * 10 + j)
                if idx >0:
                    fin = False
    memo = next_memo
    if fin:
        break
print(memo[0])

Submission status: Time Limit Exceeded

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

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

memo = [-1] * (N + 1)
memo[N] = 0
while 1:
    next_memo = [-1] * (N + 1)
    next_memo[0] = memo[0]
    for i in range(N, 0, -1):
        if memo[i] < 0: continue

        for j in range(1, 10):
            if not j in A: continue
            idx = i - V[j]
            if idx >= 0:
                next_memo[idx] = max(next_memo[idx], memo[i] * 10 + j)
    memo = next_memo
    if all((v == -1 for v in memo[1:])):
        break
print(memo[0])

Submission status: Time Limit Exceeded

Solution code:
from math import floor,log10
import sys
stdin = sys.stdin
read_int = lambda : list(map(int,stdin.readline().split()))
read_str = lambda : stdin.readline().rstrip()

N,M = read_int()

A = read_int()
# for index arrangement
A.append(-1)
A.sort()

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

dp = [-1 for j in range(N+1)]
def solve():
    dp[0] = 0
    for i in range(M):
        for j in range(N+1):
            v = A[i + 1]
            if j - W[A[i + 1]] >= 0 and dp[j - W[A[i + 1]]] >= 0:
                d = 0
                if dp[j - W[A[i + 1]]] > 0:
                    d = len(str(dp[j - W[A[i + 1]]]))
                v = A[i + 1]*10**d
                dp[j] = max(dp[j], dp[j - W[A[i + 1]]] + v)

                
if __name__ == "__main__":
    solve()
    print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N,M = map(int,input().split())
A = list(map(int,input().split()))
list_ = [0,2,5,5,4,5,6,3,7,6]
a = [list_[i] for i in A]

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

for i in range(N+1):
	for j in range(M):
		if i < a[j]:
			continue
		else:
			if (dp[i-a[j]]==0) and (i==a[j]):
				dp[i] = max(A[j],dp[i])
			elif dp[i-a[j]]==0:
				continue
			else:
				ma = "".join(sorted(str(dp[i - a[j]])+str(A[j]),reverse=True))
				dp[i] = max(int(ma),dp[i])
print(dp[i])

Submission status: Time Limit Exceeded

Solution code:

N,M = map(int,input().split())
A = list(map(int,input().split()))
list_ = [0,2,5,5,4,5,6,3,7,6]
a = [list_[i] for i in A]

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

for i in range(N+1):
	for j in range(M):
		if i < a[j]:
			continue
		else:
			if (dp[i-a[j]]==0) and (i==a[j]):
				dp[i] = max(A[j],int(dp[i]))
			elif dp[i-a[j]]==0:
				continue
			else:
				ma = "".join(sorted(str(dp[i - a[j]])+str(A[j]), reverse=True))
				dp[i] = max(int(ma),int(dp[i]))
print(int(dp[i]))

Submission status: Time Limit Exceeded

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)]+[(0, -float('inf'))]*n # 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
        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: Time Limit Exceeded

Solution code:
from operator import itemgetter

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

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

c = []

for x in a:
    if x in [1, 4, 7, 8]:
        c.append((str(x), b[x - 1]))

if 5 in a:
    c.append(('5', 5))
elif 3 in a:
    c.append(('3', 5))
elif 2 in a:
    c.append(('2', 5))

if 9 in a:
    c.append(('9', 6))
elif 6 in a:
    c.append(('6', 6))

c = sorted(c, key=itemgetter(1), reverse=True)

dp = [0 for _ in range(n + 8)]

for x, y in c:
    dp[y] = int(x)

for i in range(2, n + 1):
    if dp[i] == 0:
        continue
    for x, y in c:
        dp[i + y] = max(dp[i + y], int(x + str(dp[i])))

print(dp[n])

Submission status: Time Limit Exceeded

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

# N本 まで使うか 10^4
dp=[0] * (N+1)

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

# 桁を追加する→最大のものに桁追加だから、問題なし
# 桁を入れ替える→無駄、初期状態では0桁しかないので単純に足す
# どの桁に追加すればよいか？二分探索をして決める。つまり、最大にしたいので逆順ソート済みにする？不要。先頭と末尾に追加で対応

def digit(x):
  d = 0
  while x % 10 != 0:
    d += 1
    x //= 10
  return d

for i in range(N+1):
    for a in A:
      # i > 0なら何かしら選んでないといけない
       if i + cost[a] <= N and (i == 0 or dp[i] > 0):
        new_i = i + cost[a]
        # 桁求める、数値のまま。桁まで保持しておけば計算の必要ない？そもそも64ビット越えなのでその対処が必要？
        d = digit(dp[i])
        tmp1 = dp[i] + (10** d) * a
        tmp2 = dp[i] * 10 + a
        tmps = [dp[new_i], tmp1, tmp2]
        m = max(tmps)
        dp[new_i] = m
        # print(new_i, tmps, m)

print(dp[N])

Submission status: Time Limit Exceeded

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

# N本 まで使うか 10^4
dp=[0] * (N+1)

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

# 桁を追加する→最大のものに桁追加だから、問題なし
# 桁を入れ替える→無駄、初期状態では0桁しかないので単純に足す
# どの桁に追加すればよいか？二分探索をして決める。つまり、最大にしたいので逆順ソート済みにする？不要。先頭と末尾に追加で対応

for i in range(N+1):
    for a in A:
      # i > 0なら何かしら選んでないといけない
       if i + cost[a] <= N and (i == 0 or dp[i] > 0):
        new_i = i + cost[a]
        # 桁求める、数値のままであとでやる。とりあえずpypy
        d = len(str(dp[i])) if dp[i] else 0
        tmp1 = dp[i] + (10** d) * a
        tmp2 = dp[i] * 10 + a
        tmps = [dp[new_i], tmp1, tmp2]
        m = max(tmps)
        dp[new_i] = m
        # print(new_i, tmps, m)


print(dp[N])

Submission status: Time Limit Exceeded

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

# N本 まで使うか 10^4
dp=[0] * (N+1)

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

# 桁を追加する→最大のものに桁追加だから、問題なし
# 桁を入れ替える→無駄、初期状態では0桁しかないので単純に足す
# どの桁に追加すればよいか？二分探索をして決める。つまり、最大にしたいので逆順ソート済みにする？不要。先頭と末尾に追加で対応

for i in range(N+1):
    for a in A:
      # i > 0なら何かしら選んでないといけない
       if i + cost[a] <= N and (i == 0 or dp[i] > 0):
        new_i = i + cost[a]
        # 桁求める
        d = len(str(dp[i])) if dp[i] else 0
        tmp1 = dp[i] + (10** d) * a
        tmp2 = dp[i] * 10 + a
        tmps = [dp[new_i], tmp1, tmp2]
        m = max(tmps)
        dp[new_i] = m
        # print(new_i, tmps, m)


print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000)
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: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
N,M=map(int,input().split())
A=list(map(int,input().split()))
B=[0,2,5,5,4,5,6,3,7,6]
D=[]
for a in A:
	for aa in A:
		if B[a]==B[aa] and a!=aa:
			d=min(a,aa)
			if d not in D:
				D.append(d)
		if B[a]%B[aa]==0 and a!=aa and B[a]!=B[aa]: #B[a]>B[aa]
			if a not in D:
				D.append(a)

#print(D)
for d in D:
	A.remove(d)
for i in range(len(A)):
	for ii in range(i):
		if B[A[i]]<B[A[ii]]:
			A[i],A[ii]=A[ii],A[i]
#print(A)
C=[None for _ in range(N+1)]
C[0]=''
def DP(n):
	global C
	#print(n)
	#print(C)
	if C[n] != None:
		return C[n]
	else:
		R=[-1 for _ in range(10)]
		for a in A:
			if n-B[a] <0:
				break
			if C[n-B[a]]==None:
				DP(n-B[a])
			if C[n-B[a]]!='-1':
				R[a]=int(str(a)+C[n-B[a]])
		#print(R)
		r=str(max(R))
		C[n]=r
		return r
print(DP(N))
#print(C)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**5)
N,M=map(int,input().split())
A=list(map(int,input().split()))
B=[0,2,5,5,4,5,6,3,7,6]
D=[]
for a in A:
	for aa in A:
		if B[a]==B[aa] and a!=aa:
			d=min(a,aa)
			if d not in D:
				D.append(d)
#print(D)
for d in D:
	A.remove(d)
for i in range(len(A)):
	for ii in range(i):
		if B[A[i]]<B[A[ii]]:
			A[i],A[ii]=A[ii],A[i]
C=[None for _ in range(N+1)]
C[0]=''
def DP(n):
	global C
	#print(n)
	#print(C)
	if C[n] != None:
		return C[n]
	else:
		R=[-1 for _ in range(10)]
		for a in A:
			if n-B[a] <0:
				break
			if C[n-B[a]]==None:
				DP(n-B[a])
			if C[n-B[a]]!='-1':
				R[a]=int(str(a)+C[n-B[a]])
		#print(R)
		r=str(max(R))
		C[n]=r
		return r
print(DP(N))
#print(C)

Submission status: Time Limit Exceeded

Solution code:
import sys
from operator import itemgetter
sys.setrecursionlimit(10**5)
N,M=map(int,input().split())
A=list(map(int,input().split()))
B=[0,2,5,5,4,5,6,3,7,6]
D=[]
for a in A:
    for aa in A:
        if B[a]==B[aa] and a!=aa:
            d=min(a,aa)
            if d not in D:
                D.append(d)
#print(D)
for d in D:
    A.remove(d)
for i in range(len(A)):
    for ii in range(i):
        if B[A[i]]<B[A[ii]]:
            A[i],A[ii]=A[ii],A[i]
C=[None for _ in range(N+1)]
C[0]=''
def DP(n):
    #print(n)
    global C
    if C[n] != None:
        return C[n]
    else:
        R=[-1]
        for a in A:
            if n-B[a] <0:
                break
            if C[n-B[a]]==None:
                DP(n-B[a])
            if C[n-B[a]]!='-1':
                R.append(int(str(a)+C[n-B[a]]))
        r=str(max(R))
        C[n]=r
        return r
print(DP(N))
#print(C)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**5)
N,M=map(int,input().split())
A=list(map(int,input().split()))
B=[0,2,5,5,4,5,6,3,7,6]
D=[]
for a in A:
    for aa in A:
        if B[a]==B[aa] and a!=aa:
            d=min(a,aa)
            if d not in D:
                D.append(d)
#print(D)
for d in D:
    A.remove(d)
for i in range(len(A)):
    for ii in range(i):
        if B[A[i]]<B[A[ii]]:
            A[i],A[ii]=A[ii],A[i]
C=[None for _ in range(N+1)]
C[0]=''
def DP(n):
    #print(n)
    global C
    if C[n] != None:
        return C[n]
    else:
        R=[-1]
        for a in A:
            if n-B[a] <0:
                break
            if DP(n-B[a])!='-1':
                R.append(int(str(a)+C[n-B[a]]))
        r=str(max(R))
        C[n]=r
        return r
print(DP(N))
#print(C)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**5)
N,M=map(int,input().split())
A=list(map(int,input().split()))
B=[0,2,5,5,4,5,6,3,7,6]
C=[None for _ in range(N+1)]
C[0]=''
def DP(n):
    global C
    if n<0:
        return '-1'
    if C[n] != None:
        return C[n]
    else:
        r=-1
        for a in A:
            if DP(n-B[a])!='-1':
                r=max(r,int(str(a)+C[n-B[a]]))
        r=str(r)
        C[n]=r
        return r
#print(C)
print(DP(N))

Submission status: Time Limit Exceeded

Solution code:
def main():
	n, m = list(map(int, input().split()))
	nums = list(map(int, input().split()))
	
	d = {1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6}
	num2match = {key:val for key, val in d.items() if key in nums}
	
	dp = [-1 for i in range(n + 1)]

	dp[0] = 0
	val_set = set(num2match.values())
	match2num = {v:max([int(key) for key, val in num2match.items() if val == v]) for v in val_set}
 
	for i in range(2, n + 1):
		for val in val_set:
			if i >= val and dp[i - val] > 0:
				tmp = match2num[val] * (10 ** len(str(dp[i - val]))) + dp[i - val]
				dp[i] = max(dp[i], tmp)
			elif i >= val and dp[i - val] == 0:
				tmp = match2num[val]
				dp[i] = max(dp[i], tmp)
	
	#print(num2match)
	#print(match2num)
	#print(dp)
	print(int(dp[n]))
 
if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
import time

N, M = [int(i) for i in input().split()]
A = [s for s in input().split()]
numDict = {"1":2, "2":5, "3":5, "4":4, "5":5, "6":6, "7":3, "8":7, "9":6}

def strNumSort(strNum, addStrNum):
    addIntNum = int(addStrNum)
    for i in range(len(strNum)):
        if addIntNum >= int(strNum[i]):
            return int("{0}{1}{2}".format(strNum[:i], addIntNum, strNum[i:]))
    return int(strNum + addStrNum)

start = time.time()

dp = [0 for _ in range(N + 1)]
matches = 0

for i in range(N + 1):
    for strNum in A:
        if i - numDict[strNum] == 0:
            dp[i] = max(dp[i], int(strNum))
            continue
        if i - numDict[strNum] > 0 and dp[i - numDict[strNum]] != 0:
            dp[i] = max(dp[i], strNumSort(str(dp[i - numDict[strNum]]), strNum))

print(dp[N])

#elapsed_time = time.time() - start
#print(elapsed_time)

Submission status: Time Limit Exceeded

Solution code:
def f(x,a):
    while x>0:
        a*=10
        x//=10
    return a

n,m=map(int,input().split())
cost=[0,2,5,5,4,5,6,3,7,6]
la=[int(i) for i in input().split()]
la.sort()
ma=[0 for i in range(10010)]
for a in la:
    ma[cost[a]]=a
for i in range(2,n+1):
    if ma[i]==0:
        continue
    for a in la:
        ma[i+cost[a]]=max(ma[i+cost[a]],max(ma[i]*10+a,ma[i]+f(ma[i],a)))
print(ma[n])

Submission status: Time Limit Exceeded

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

import sys, re
from collections import deque, defaultdict, Counter
from math import sqrt, hypot, factorial, pi, sin, cos, radians, log10
if sys.version_info.minor >= 5: from math import gcd
else: from fractions import gcd 
from heapq import heappop, heappush, heapify, heappushpop
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul, xor
from copy import copy, deepcopy
from functools import reduce, partial
from fractions import Fraction
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def round(x): return int((x*2+1) // 2)
def fermat(x, y, MOD): return x * pow(y, MOD-2, MOD) % MOD
def lcm(x, y): return (x * y) // gcd(x, y)
def lcm_list(nums): return reduce(lcm, nums, 1)
def gcd_list(nums): return reduce(gcd, nums, nums[0])
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, M = MAP()
A = LIST()
need = [0,2,5,5,4,5,6,3,7,6]

dp = [''] * (N+10)
for a in A:
    dp[need[a]] = max(dp[need[a]], str(a))

for i in range(N):
    if dp[i] != '':
        for a in A:
            # 基本は文字列の長さ(桁数)で比較
            if len(dp[i+need[a]]) < len(dp[i])+1:
                dp[i+need[a]] = dp[i]+str(a)
            # それが同じ時だけ降順ソートして大小比較
            elif len(dp[i+need[a]]) == len(dp[i])+1:
                b = ''.join(sorted(dp[i]+str(a), reverse=True))
                c = ''.join(sorted(dp[i+need[a]], reverse=True))
                dp[i+need[a]] = max(b, c)
print(''.join(sorted(dp[N], reverse=True)))

Submission status: Time Limit Exceeded

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

import sys, re
from collections import deque, defaultdict, Counter
from math import sqrt, hypot, factorial, pi, sin, cos, radians, log10
if sys.version_info.minor >= 5: from math import gcd
else: from fractions import gcd 
from heapq import heappop, heappush, heapify, heappushpop
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul, xor
from copy import copy, deepcopy
from functools import reduce, partial
from fractions import Fraction
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def round(x): return int((x*2+1) // 2)
def fermat(x, y, MOD): return x * pow(y, MOD-2, MOD) % MOD
def lcm(x, y): return (x * y) // gcd(x, y)
def lcm_list(nums): return reduce(lcm, nums, 1)
def gcd_list(nums): return reduce(gcd, nums, nums[0])
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, M = MAP()
A = LIST()
need = [0,2,5,5,4,5,6,3,7,6]

dp = [''] * (N+10)
for a in A:
    dp[need[a]] = max(dp[need[a]], str(a))

for i in range(N):
    if dp[i] != '':
        for a in A:
            # 基本は文字列の長さ(桁数)で比較
            if len(dp[i+need[a]]) < len(dp[i])+1:
                dp[i+need[a]] = dp[i]+str(a)
            # それが同じ時だけ数値変換して大小比較
            elif len(dp[i+need[a]]) == len(dp[i])+1:
                b = int(''.join(sorted(dp[i]+str(a), reverse=True)))
                c = int(''.join(sorted(dp[i+need[a]], reverse=True)))
                dp[i+need[a]] = str(max(b, c))
print(''.join(sorted(dp[N], reverse=True)))

Submission status: Time Limit Exceeded

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

import sys, re
from collections import deque, defaultdict, Counter
from math import sqrt, hypot, factorial, pi, sin, cos, radians, log10
if sys.version_info.minor >= 5: from math import gcd
else: from fractions import gcd 
from heapq import heappop, heappush, heapify, heappushpop
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul, xor
from copy import copy, deepcopy
from functools import reduce, partial
from fractions import Fraction
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def round(x): return int((x*2+1) // 2)
def fermat(x, y, MOD): return x * pow(y, MOD-2, MOD) % MOD
def lcm(x, y): return (x * y) // gcd(x, y)
def lcm_list(nums): return reduce(lcm, nums, 1)
def gcd_list(nums): return reduce(gcd, nums, nums[0])
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, M = MAP()
A = LIST()
need = [0,2,5,5,4,5,6,3,7,6]

dp = [0] * (N+10)
for a in A:
    dp[need[a]] = max(dp[need[a]], a)

for i in range(N):
    if dp[i] != 0:
        for a in A:
            s = int(''.join(sorted(str(dp[i])+str(a), reverse=True)))
            t = dp[i+need[a]]
            dp[i+need[a]] = max(t, s)
print(dp[N])