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:
# -*- 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:
            s = ''.join(sorted(dp[i]+str(a), reverse=True))
            t = dp[i+need[a]]
            if t == '':
                t = '0'
            dp[i+need[a]] = str(max(int(t), int(s)))
print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    dp = [-1] * (N+1)
    dp[0] = 0
    cost = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
    for i in range(N+1):
        for d in A:
            if i < cost[d]:
                continue
            prev = dp[i - cost[d]]
            if prev == -1:
                continue
            elif prev == 0:
                candidate = d
            else:
                candidate = max(int("{}{}".format(prev, d)),
                                int("{}{}".format(d, prev)))
            dp[i] = max(dp[i], candidate)
    print(dp[N])


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def main():
	n, m = list(map(int, input().split()))
	nums = list(map(int, input().split()))

	num2match = {key:val for key, val in {1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6}.items() if key in nums}
	dp = ["na" for i in range(n + 1)] # マッチをn本使った時に作れる最大の数

	dp[0] = ""
	val_set = set(num2match.values())
	match2num = {v:max([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] != "na":
				tmp = str(match2num[val]) + str(dp[i - val])
				if dp[i] == "na" or int(tmp) >= int(dp[i]):
					dp[i] = tmp

	print(int(dp[n]))

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
match = dict(zip([i+1 for i in range(9)], [2, 5, 5, 4, 5, 6, 3, 7, 6]))
N, M = map(int, input().split())
A = list(map(int, input().split()))

max_number_by = {}


for a in A:
    match_number = match[a]
    if(match_number not in max_number_by):
        max_number_by[match_number] = -1
    max_number_by[match_number] = max(max_number_by[match_number], a) 

mm = [-1 for i in range(10**4+7)]
mm[0] = 0
for i in range(N+1):
    for j in range(i):
        if(i-j not in max_number_by or mm[j]==-1):
            continue
        if(int(str(mm[j])+str(max_number_by[i-j])) > mm[i]):
            mm[i] = int(str(mm[j])+str(max_number_by[i-j]))

print(mm[N])

Submission status: Time Limit Exceeded

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


# 桁数の一番大きいものが最大。そのあと数を大きい順に並べればいい
dp = [0]*(N+1)       # dp[i]: i 本のマッチで条件を満たす整数の最大桁数
cost = [ 0, 2, 5, 5, 4, 5, 6, 3, 7, 6 ]  # 各数字に必要なマッチ棒の数(逆順)

for num_match in range( 2, N+1 ):
    for Aj in A:
        if num_match >= cost[Aj]:
            dp[num_match] = max( dp[num_match], dp[num_match-cost[Aj]]+1 )


# 求めた桁数 dp[N] を用いて順序を求める
ans = ""
digit = dp[N]

A.sort( reverse=True )
while N > 0:
    for Ai in A:
        if N-cost[Ai] >=0 and dp[N-cost[Ai]] == digit-1:
            ans += str(Ai)
            N -= cost[Ai]
            digit -= 1
            break

print( ans )

Submission status: Time Limit Exceeded

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

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

dp = [[-1 for n in range(N+1)] for m in range(M+1)]
dp[0][0] = 0
#keta
dp_r = [[-1 for n in range(N+1)] for m in range(M+1)]
#m

for m in range(1,M+1):
    for n in range(N+1):
        #dp[m][n] = max(dp[m-1][n],
        #dp[m][n-c[A[m-1]-1]] + 1 if (n-c[A[m-1]-1])>=0 and dp[m][n-c[A[m-1]-1]] != -1 else -1)
        if n-c[A[m-1]-1] >= 0 and dp[m][n-c[A[m-1]-1]] != -1:
            if dp[m-1][n] < (dp[m][n-c[A[m-1]-1]] + 1):
                dp[m][n] = dp[m][n-c[A[m-1]-1]] + 1
                dp_r[m][n] = 1
            elif dp[m-1][n] == (dp[m][n-c[A[m-1]-1]] + 1):
                dp[m][n] = dp[m][n-c[A[m-1]-1]] + 1
                dp_r[m][n] = 2
            else:
                dp[m][n] = dp[m-1][n]
                dp_r[m][n] = 0
        else:
            dp[m][n] = dp[m-1][n]
            dp_r[m][n] = 0


#import pprint
#pprint.pprint(dp,width=100)
#pprint.pprint(dp_r,width=100)

def trace(dp,m,n):
    r=[[]]
    for _ in range(N+M+2):
        if m==0 and n==0:
            return r
        elif dp_r[m][n] == 0:
            m = m-1
        elif dp_r[m][n] == 1:
            r = [r_+[m] for r_ in r]
            n = n-c[A[m-1]-1]
        elif dp_r[m][n] == 2:
            r_1 = trace(dp,m-1,n)
            r_2 = trace(dp,m,n-c[A[m-1]-1])
            return [r[0]+r_ for r_ in r_1] + [r[0]+r_+[m] for r_ in r_2]


tm = trace(dp,M,N)
#print(tm)
####   one_trace
#cr = []
#m, n = M, N
#for _ in range(N+M+2):
#    if m == 0 and n == 0:
#        break
#    elif dp_r[m][n] == 0:
#        m = m - 1
#    else:
#        #print(dp_r[m][n])
#        cr += [c[A[dp_r[m][n]-1]-1]]
#        n = n - c[A[dp_r[m][n]-1]-1]
#print(cr)

d = {}
for a in A:
    d[a] = c[a-1]

#print(d)

inv_d = {}
for k,v in d.items():
    if v in inv_d:
        if k > inv_d[v]:
            inv_d[v] = k
    else:
        inv_d[v] = k
#print(inv_d)


#from operator import itemgetter

ans = []
for tm_ in tm:
    ans_ = [inv_d[c[A[m-1]-1]] for m in tm_]
    ans_.sort(reverse=True)
    ans += [ans_]

ans.sort(reverse=True)
#print(ans)
for ans_ in ans[0]:
    print(ans_,sep='',end='')
print()

Submission status: Time Limit Exceeded

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

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

dp = [[-1 for n in range(N+1)] for m in range(M+1)]
dp[0][0] = 0
#keta
dp_r = [[-1 for n in range(N+1)] for m in range(M+1)]
#m

for m in range(1,M+1):
    for n in range(N+1):
        #dp[m][n] = max(dp[m-1][n],
        #dp[m][n-c[A[m-1]-1]] + 1 if (n-c[A[m-1]-1])>=0 and dp[m][n-c[A[m-1]-1]] != -1 else -1)
        if n-c[A[m-1]-1] >= 0 and dp[m][n-c[A[m-1]-1]] != -1:
            if dp[m-1][n] < (dp[m][n-c[A[m-1]-1]] + 1):
                dp[m][n] = dp[m][n-c[A[m-1]-1]] + 1
                dp_r[m][n] = 1
            elif dp[m-1][n] == (dp[m][n-c[A[m-1]-1]] + 1):
                dp[m][n] = dp[m][n-c[A[m-1]-1]] + 1
                dp_r[m][n] = 2
            else:
                dp[m][n] = dp[m-1][n]
                dp_r[m][n] = 0
        else:
            dp[m][n] = dp[m-1][n]
            dp_r[m][n] = 0


#import pprint
#pprint.pprint(dp,width=100)
#pprint.pprint(dp_r,width=100)

def trace(dp):
    m = len(dp)-1
    n = len(dp[0])-1
    r=[[]]
    for _ in range(N+M+2):
        if m==0 and n==0:
            return r
        elif dp_r[m][n] == 0:
            m = m-1
        elif dp_r[m][n] == 1:
            r = [r_+[m] for r_ in r]
            n = n-c[A[m-1]-1]
        elif dp_r[m][n] == 2:
            r_1 = trace([dp_[:n+1] for dp_ in dp[:m]])
            r_2 = trace([dp_[:n-c[A[m-1]-1]+1] for dp_ in dp[:m+1]])
            return [r[0]+r_ for r_ in r_1] + [r[0]+r_+[m] for r_ in r_2]

tm = trace(dp)
#print(tm)
####   one_trace
#cr = []
#m, n = M, N
#for _ in range(N+M+2):
#    if m == 0 and n == 0:
#        break
#    elif dp_r[m][n] == 0:
#        m = m - 1
#    else:
#        #print(dp_r[m][n])
#        cr += [c[A[dp_r[m][n]-1]-1]]
#        n = n - c[A[dp_r[m][n]-1]-1]
#print(cr)

d = {}
for a in A:
    d[a] = c[a-1]

#print(d)

inv_d = {}
for k,v in d.items():
    if v in inv_d:
        if k > inv_d[v]:
            inv_d[v] = k
    else:
        inv_d[v] = k
#print(inv_d)


#from operator import itemgetter

ans = []
for tm_ in tm:
    ans_ = [inv_d[c[A[m-1]-1]] for m in tm_]
    ans_.sort(reverse=True)
    ans += [ans_]

ans.sort(reverse=True)
#print(ans)
for ans_ in ans[0]:
    print(ans_,sep='',end='')
print()

Submission status: Time Limit Exceeded

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

import array
from bisect import *
from collections import *
import fractions
import heapq
from itertools import *
import math
import random
import re
import string
import sys

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

needs = [0,2,5,5,4,5,6,3,7,6]
need_to_ch = {}
for a in sorted(As):
    need = needs[a]
    need_to_ch[need] = str(a)

ans = 0
needs = list(need_to_ch.keys())
def dfs(idx, remain, used):
    global ans
    need = needs[idx]
    if idx == len(needs) - 1:
        if remain % need:
            return
        used += [remain // need]
        s = ''
        for (n, ch), use in zip(need_to_ch.items(), used):
            s += ch * use
        ans = max(ans, int(''.join(sorted(s, reverse=True))))
    else:
        for i in range(0, remain + 1, need):
            dfs(idx + 1, remain - i, used + [i // need])
dfs(0, N, [])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10000)

def main():
    r = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
    #    -  1  2  3  4  5  6  7  8  9

    N, M = [int(x) for x in input().split()]
    A = [int(x) for x in input().split()]

    rate = [a/r[a] for a in A]
    rate.sort()

    memo = {} #  N : int

    def greedy(N): # int -> [char]
        """
        """
        #print("ENTER greedy(N=%s)" % N, A, N in memo)
        if N in memo:
            return memo[N]
        M = 0
        result = None
        for a in A:
            #print("  greedy(N=%s) a=%s, M=%s" % (N, a, M))
            if r[a] > N:
                continue
            elif r[a] == N:
                n = a
            else:
                g = greedy(N - r[a])
                if g is None:
                    continue
                n = int(
                        "".join(sorted(list(str(g)) +[str(a)], reverse=True))
                    )
            if M < n:
                result = n
                M = n
        if result is None:
            memo[N] = None
        memo[N] = result
        return result

    answer = greedy(N)
    print(answer)

main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
import sys

#    -  1  2  3  4  5  6  7  8  9

def chmax(n, m):
    if n[0] == None:
        return (int(m), [str(m)])
    #print("n[1]", n[1])
    ch = sorted(n[1] + [str(m)], reverse=True)
    #print("ch", ch)
    return int("".join(ch)), ch

def main():
    r = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
    N, _ = [int(x) for x in input().split()]
    A = [int(x) for x in input().split()]
    A = sorted(A, reverse=True)

    dp = [(0, [])] * (N + 9)#  N : int
    dp[0] = (None , [])

    for i in range(0, N+1):
        if dp[i][0] == 0:
            continue
        for a in A:
            m = chmax(dp[i], a)
            if dp[i+r[a]][0] < m[0]:
                dp[i+r[a]] = m
        #print("%8d" % i, dp[i])
    print(dp[N][0])

main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
import sys

r = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
#    -  1  2  3  4  5  6  7  8  9

MAXINT = 0xffffffff

def chmax(n, m):
    if n == None:
        return m
    return int("".join(sorted(list(str(n)) + [str(m)], reverse=True)))

def main():
    N, _ = [int(x) for x in input().split()]
    A = [int(x) for x in input().split()]
    A = sorted(A, reverse=True)
    dp = [0] * (N + 9)#  N : int
    dp[0] = None 

    for i in range(0, N+1):
        if dp[i] == 0:
            continue
        for a in A:
            m = chmax(dp[i], a)
            if dp[i+r[a]] < m:
                dp[i+r[a]] = m
        #print("%8d" % i, dp[i])
    print(dp[N])


main()

Submission status: Time Limit Exceeded

Solution code:
def f(x):
    k = int(x)
    return c[k], k


c = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
N, M = list(map(int, input().split()))
A = list(map(f, input().split()))
A = sorted(A, key=lambda x: x[0] * 10 - x[1])

# 数字を作成するのに必要なマッチ数のリストを作成
b = []
dic = {}
n = 0
for d in A:
    if n != d[0]:
        b.append(d[0])
        n = d[0]
        dic[n] = d[1]

ans = [0] * b[0]
n = b[0]
while True:
    max_ = 0
    for d in b:
        if n - d == 0:
            if dic[d] > max_:
                max_ = dic[d]
        elif n - d > 0 and ans[n - d] > 0:
            t = dic[d] * (10 ** len(str(ans[n - d]))) + ans[n - d]
            max_ = max(max_, t)

    if n == N:
        print(max_)
        break
    ans.append(max_)
    n += 1

Submission status: Time Limit Exceeded

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

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

cost = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
cd = {}
for a in A:
    if cost[a] in cd:
        cd[cost[a]] = max(cd[cost[a]], a)
    else:
        cd[cost[a]] = a

dp = [(0, [])]
for i in range(1, N + 1):
    mx, mxl, mxs = int(-1e10), [], ""
    for c in cd:
        if i - c >= 0 and mx <= dp[i - c][0] + 1 and 0 <= dp[i - c][0] and mxs <= ''.join(map(str, sorted(dp[i - c][1], reverse=True))):
            mx, mxl = dp[i - c][0] + 1, dp[i - c][1] + [cd[c]]
            mxs = ''.join(map(str, sorted(dp[i - c][1], reverse=True)))
    dp.append((mx, mxl))

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

Submission status: Time Limit Exceeded

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

dp = [-INF]*(N+1)
dp[0] = 0
for i in range(N):
    for j in src:
        if i + arr[j] <= N:
            dp[i + arr[j]] = max(dp[i + arr[j]], dp[i] + 1)
ans = ''
while(N>0):
    for i in src[::-1]:
        if N - arr[i] > 0 and dp[N-arr[i]] == dp[N] - 1:
            ans += str(i)
            N -= arr[i]
            break
print(ans if ans else 0)

Submission status: Time Limit Exceeded

Solution code:
def keta(a):
    counter = 0
    while a >= 10**counter:
        counter += 1
    return counter

def add(dp,i,before,k): #kは追加する数字
    tens = keta(before)
    if before*10 + k >= k * (10**tens) + before:
        return before*10 + k
    else:
        return k * (10**tens) + before

    

make = {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()))

use = dict()
for i in range(m):
    use[a[i]] = make[a[i]]

dp = [0 for i in range(n+1)]
for i in use:
    if n >= use[i]:
        if dp[use[i]] == 0:
            dp[use[i]] = i
        else:
            if i > dp[use[i]]:
                dp[use[i]] = i

for i in range(1,n+1):
    for k in use:
        if i-use[k] >= 0:
            before = dp[i-use[k]]
            if before != 0:
                temp = add(dp,i,before,k)
                #print(before,temp)
                if temp > dp[i]:
                    dp[i] = temp
print(dp[n])

Submission status: Time Limit Exceeded

Solution code:
mtch = {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()))

dp = [["-" for j in range(N + 1)] for i in range(N//2 + 1)]
dp[0][0] = ""

for i in range(N//2 + 1):
    for j in range(N + 1):
        for a in A:
            if dp[i][j] != "-" and j + mtch[a] <= N:
                added = dp[i][j] + str(a)
                if dp[i + 1][j + mtch[a]] < added:
                    dp[i + 1][j + mtch[a]] = added

for i in range(N//2, -1, -1):
    if dp[i][N] != "-":
        print(dp[i][N])
        break

Submission status: Time Limit Exceeded

Solution code:
mtch = {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()))

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

for i in range(N + 1):
    for j in range(N + 1):
        for a in A:
            if dp[i][j] != "-" and j + mtch[a] <= N:
                added = dp[i][j] + str(a)
                if dp[i + 1][j + mtch[a]] < added:
                    dp[i + 1][j + mtch[a]] = added

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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from copy import copy

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

ms = [2,5,5,4,5,6,3,7,6]
dic = defaultdict(lambda: 0)
for a in A:
    dic[ms[a-1]] = max(dic[ms[a-1]], a)

sd = sorted(dic.items())

dp = [None] * (N+1)
dp[0] = defaultdict(lambda: 0)

for i in range(sd[0][0], N+1):
    cands = []
    for l,a in sd:
        if i-l < 0: break
        if dp[i-l] is None: continue
        cands.append(copy(dp[i-l]))
        cands[-1][a] += 1
    if not cands: continue
    max_v = 0
    max_j = -1
    for j,cand_dic in enumerate(cands):
        tmp_s = ''
        for a,n in sorted(cand_dic.items(), reverse=True):
            tmp_s += str(a) * n
        tmp_v = int(tmp_s)
        if tmp_v > max_v:
            max_v = tmp_v
            max_j = j
    dp[i] = cands[max_j]

ans = ''
for a,n in sorted(dp[-1].items(), reverse=True):
    ans += str(a) * n
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))
num = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
B = [(i, num[i]) for i in A]
ans = {}
for i in range(N + 1):
    x = '0'
    for j, k in B:
        if i - k < 0:
            continue
        if i == k:
            x = str(max(int(x), int(j)))
            continue
        an = ans[i - k]
        if an == '0':
            continue
        if str(j) > an[0]:
            y = str(j) + an
        else:
            y = an + str(j)
        x = str(max(int(x), int(y)))
    ans[i] = x
print(ans[N])

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))
num = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
B = [(i, num[i]) for i in A]
ans = {0: 0, 1: 0}
for i in range(2, N + 1):
    x = 0
    for j, k in B:
        if i - k < 0:
            continue
        if i == k:
            x = max(x, j)
            continue
        an = ans[i - k]
        if an == 0:
            continue
        x = max(x, an * 10 + j)
        x = max(x, j * 10 ** len(str(an)) + an)
    ans[i] = x
print(ans[N])

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))
num = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
ans = {0: 0, 1: 0}
for i in range(2, N + 1):
    x = 0
    for j in A:
        k = num[j]
        if i - k < 0:
            continue
        if i == k:
            x = max(x, j)
            continue
        an = ans[i - k]
        if an == 0:
            continue
        x = max(x, an * 10 + j)
        x = max(x, j * 10 ** len(str(an)) + an)
    ans[i] = x
print(ans[N])

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))
num = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
ans = {0: 0, 1: 0}
for i in range(2, N + 1):
    x = 0
    for j in A:
        k = num[j]
        if i - k < 0:
            continue
        if i == k:
            x = max(x, j)
            continue
        if i - k in ans:
            an = ans[i - k]
            if an == 0:
                continue
            x = max(x, an * 10 + j)
            x = max(x, j * 10 ** len(str(an)) + an)
    ans[i] = x
print(ans[N])

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
A = set(map(int, input().split()))
num = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
ans = {0: 0, 1: 0}
for i in range(2, N + 1):
    x = 0
    for j in range(1, 10):
        k = num[j]
        if j not in A or i - k < 0:
            continue
        if i == k:
            x = max(x, j)
            continue
        if i - k in ans:
            an = ans[i - k]
            if an == 0:
                continue
            x = max(x, an * 10 + j)
            x = max(x, j * 10 ** len(str(an)) + an)
    ans[i] = x
print(ans[N])

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
A = set(map(int, input().split()))
num = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
ans = {0: 0, 1: 0}
for i in range(2, N + 1):
    x = 0
    for j in range(1, 10):
        k = num[j]
        if j not in A or i - k < 0:
            continue
        if i == k:
            x = max(x, j)
            continue
        if i - k in ans:
            an = ans[i - k]
            if an == 0:
                continue
            x = max(x, an * 10 + j)
            x = max(x, j * 10 ** len(str(an)) + an)
    ans[i] = x
print(ans[N])

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
A = set(map(int, input().split()))
num = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
ans = {}
for i in range(N + 1):
    x = 0
    for j in range(1, 10):
        k = num[j]
        if j not in A or i - k < 0:
            continue
        if i == k:
            x = max(x, j)
            continue
        if i - k in ans:
            an = ans[i - k]
            if an == 0:
                continue
            x = max(x, an * 10 + j)
            x = max(x, int(str(j)+str(an)))
    ans[i] = x
print(ans[N])

Submission status: Time Limit Exceeded

Solution code:
def main():
    N,M = map(int, input().split())
    A = list(map(int, input().split()))
    #A.insert(0)
    use = [0,2,5,5,4,5,6,3,7,6]

    # dp[i][j] = 残りj本でできる最大の数
    dp = []
    for i in range(N//2+11):
        dp.append([-1 for j in range(N+1)])
    dp[0][N] = 0

    for i in range(1,N//2+11):
        for n in range(0,N+1):
            for a in A:
                if n + use[a] > N:
                    dp[i][n] = max(dp[i][n], dp[i-1][n])
                else:
                    dp[i][n] = max(dp[i][n], dp[i-1][n+use[a]]*10+a)
        #for n in range(0,N+1):
        #    print('%8d' % dp[i][n], end='')
        #print()
        if dp[i] == dp[i-1]:
            print(dp[i][0])
            return

main()

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
A = set(map(int, input().split()))
num = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
ans = {}
for i in range(N + 1):
    x = 0
    for j in range(1, 10):
        k = num[j]
        if j not in A or i - k < 0:
            continue
        if i == k:
            x = max(x, j)
            continue
        if i - k in ans:
            an = ans[i - k]
            if an == 0:
                continue
            x = max(x, an * 10 + j)
            x = max(x, j * 10 ** len(str(an)) + an)
    ans[i] = x
print(ans[N])

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
*A, = map(int, input().split())
 
cost_define = [2,5,5,4,5,6,3,7,6]
 
C = []
A = sorted(A)
for a in A:
  C.append(cost_define[a-1])
 
#まず最小コストで桁を決定
min_cost = 7
min_cost_index = 0
for i in range(len(C)):
  #あと勝ち
  if (C[i] <= min_cost):
    min_cost_index = i
    min_cost = C[i]
min_cost_number = A[min_cost_index]
keta = N // min_cost
amari = (N - (keta*min_cost))
#print(min_cost, min_cost_number, keta, amari)
 
#余ったら最大桁から増やしていく
res = ""
while (0 < keta):
  if (0 < amari):
    found = False
    for (c,a) in zip(reversed(C),reversed(A)):
      #print(c,a,amari)
      c -= min_cost
      if (0 < c):
        if (c <= amari):
          n = min(keta, amari // c)
          amari -= (c * n)
          res += str(a) * n
          keta -= n
          found = True
          break
      elif (0 == c):
        found = False
        break
    if not found:
      res += str(min_cost_number) * keta
      keta = 0
      break
  else:
    res += str(min_cost_number) * keta
    keta = 0
    break
  #print(keta, res)
 
#まだ余っていたら最下位から数を減らしてでも本数を使い切る
while (0 < amari):
  tmp_c = 0
  tmp_a = 0
  for (c,a) in zip(C,A):
    c -= min_cost
    if (c <= amari):
      #あと勝ち
      if (tmp_c <= c):
      	tmp_c = c
      	tmp_a = a
  n = 1
  amari -= (tmp_c * n)
  #print(amari,tmp_c)

  new_res = res[:-(keta+n)] + str(tmp_a)*n
  if (0 < keta):
    new_res += res[-(keta):]
  res = new_res
  keta += n
 
print(res)

Submission status: Time Limit Exceeded

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

DP = [0] * (N+1)

for i in range(N+1):
    for j in range(M):
        n = num[A[j]]
        if i - n >= 0:
            DP[i] = max(DP[i], DP[i-n]+1)

A.sort(reverse = True)

ans = ""
remain = DP[N]
match = N
while match > 0:
    if remain == 1:
        for i in range(M):
            if num[A[i]] == match:
                ans += str(A[i])
                print(ans)
                exit()
    for i in range(M):
        n = num[A[i]]
        if match - n >= 0 and DP[match - n] == DP[match] - 1:
            ans += str(A[i])
            remain -= 1
            match -= n
            break

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
def  inpl(): return list(map(int, input().split()))
N, M = inpl()
A = sorted(inpl())
cost = [1e9, 2, 5, 5, 4, 5, 6, 3, 7, 6]
ucost = set([cost[a] for a in A])

DP = [-1000000]*(N+1)
for a in A:
    if cost[a] <= N:
        DP[cost[a]] = 1

for i in range(N):
    v = DP[i]
    for a in A:
        c = cost[a]
        if i + c > N:
            break
        DP[i+c] = max(DP[i+c], v+1)
rA = A[::-1]


t = N
ans = 0
while t:
    for a in rA:
        if t - cost[a] < 0:
            continue
        if DP[t] == DP[t - cost[a]] + 1:
            ans = 10*ans + a
            t -= cost[a]
            break
print(ans)

Submission status: Time Limit Exceeded

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

DP = [0] * (N+1)

for i in range(N+1):
    for j in range(M):
        n = num[A[j]]
        if i - n >= 0:
            DP[i] = max(DP[i], DP[i-n]+1)

A.sort(reverse = True)

ans = ""
remain = DP[N]
match = N
while match > 0:
    for i in range(M):
        n = num[A[i]]
        if match - n >= 0 and DP[match - n] == DP[match] - 1:
            ans += str(A[i])
            match -= n
            break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
Matches = {str(num): c for num, c in zip([1, 2, 3, 4, 5, 6, 7, 8, 9], [2, 5, 5, 4, 5, 6, 3, 7, 6])}


def solve(N, M, As):
    Ms = {num: c for num, c in Matches.items() if int(num) in As}
    dp = ["-1" for _ in range(N + 1)]
    dp[0] = "0"
    for n in range(N + 1):
        for num, c in Ms.items():
            if n - c >= 0:
                if dp[n - c] == "-1":
                    continue
                if dp[n - c] == "0":
                    dp[n] = str(max(int(num), int(dp[n])))
                else:
                    dp[n] = str(max(int(dp[n - c] + num),
                                int(num + dp[n - c]),
                                int(dp[n])))
    return int(dp[N])


if __name__ == "__main__":
    N, M = tuple(map(int, input().split(" ")))
    As = list(map(int, input().split(" ")))
    print(solve(N, M, As))

Submission status: Time Limit Exceeded

Solution code:
Matches = {str(num): c for num, c in zip([1, 2, 3, 4, 5, 6, 7, 8, 9], [2, 5, 5, 4, 5, 6, 3, 7, 6])}


def solve(N, M, As):
    Ms = {num: c for num, c in Matches.items() if int(num) in As}
    dp = ["-1" for _ in range(N + 1)]
    dp[0] = "0"
    for n in range(N + 1):
        for num, c in Ms.items():
            if n - c >= 0:
                if dp[n - c] == "-1":
                    continue
                if dp[n - c] == "0":
                    dp[n] = str(max(int(num), int(dp[n])))
                else:
                    dp[n] = str(max(int(dp[n - c] + num),
                                int(num + dp[n - c]),
                                int(dp[n])))
    return int(dp[N])

if __name__ == "__main__":
    N, M = tuple(map(int, input().split(" ")))
    As = list(map(int, input().split(" ")))
    print(solve(N, M, As))

Submission status: Time Limit Exceeded

Solution code:
Matches = {num: c for num, c in zip([1, 2, 3, 4, 5, 6, 7, 8, 9], [2, 5, 5, 4, 5, 6, 3, 7, 6])}

def solve(N, M, As):
    Ms = {num: c for num, c in Matches.items() if num in As}
    dp = [-1 for _ in range(N + 1)]
    dp[0] = 0
    for n in range(N + 1):
        for num, c in Ms.items():
            if n - c >= 0:
                if dp[n - c] == -1:
                    continue
                if dp[n - c] == 0:
                    dp[n] = max(num, dp[n])
                else:
                    dp[n] = max(int(str(dp[n - c]) + str(num)),
                                int(str(num) + str(dp[n - c])),
                                dp[n])
    return dp[N]

if __name__ == "__main__":
    N, M = tuple(map(int, input().split(" ")))
    As = list(map(int, input().split(" ")))
    print(solve(N, M, As))

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
A=list(map(int,input().split()))
num=[0,2,5,5,4,5,6,3,7,6]
dp=[0]
keta=[0]
tmp=0
tmp1=0
tmp_keta=-1
tmp1_keta=-1
for i in range(1,N+1):
    tmp=-1
    tmp_keta=-1
    for j in A:
        tmp1=-1
        tmp1_keta=-1
        if(i-num[j]>=0):
            if(dp[i-num[j]]>0):
                tmp1=dp[i-num[j]]+j*(10**keta[i-num[j]])
                tmp1_keta=keta[i-num[j]]+1
            elif(dp[i-num[j]]==0):
                tmp1=j
                tmp1_keta=1

            if(tmp1>tmp):
                tmp=tmp1
                tmp_keta=tmp1_keta
                
    dp.append(tmp)
    keta.append(tmp_keta)
print(dp[N])