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: Accepted

Solution code:
#123456789
#255456376
n, m = map(int, input().split())
a = list(map(int , input().split()))
a.sort()
t = [2,5,5,4,5,6,3,7,6]
cost = []
for i in range(m):
    cost.append(t[a[i]-1])
#print(a)
#print(cost)
min_c = min(cost)
digit = n // min_c # 最大桁数
s = n % min_c # 最大桁まで作った余りの本数

max_ai = 0
import itertools
for i in itertools.product(list(range(m+1)), repeat=min(digit, 5)):
    #print(i)
    t = list(i)
    ci = sum(list(map(lambda j: cost[j-1] if j != 0 else 0, t)))
    ai = ''.join(map(lambda j: str(a[j-1]) if j != 0 else '', t))
    if digit <= 5:
        if ci == n:
            max_ai = max(max_ai, int(ai))
    else:
        if ci == (n - min_c * (digit - 5)):
            max_ai = max(max_ai, int(ai))
    #print(ci, max_ai)
min_chr = ''
for i in reversed(range(m)):
    if min_c == cost[i]:
        min_chr = a[i]
        break

if digit <= 5:
    print(max_ai)
else:
    ans = list(str(max_ai)) + ([str(min_chr)] * (digit - 5))
    ans.sort(reverse=True)
    print(''.join(ans))


"""
chg = []
while s > 0:
    #print(s, chg)
    for i in reversed(range(m)):
        if min_c + s == cost[i]:
            chg.append(a[i])
            s = 0
            break
    for i in reversed(range(m)):
        if min_c < cost[i] and cost[i] < min_c + s:
            chg.append(a[i])
            s = min_c + s - cost[i]
            break

#print(chg)
min_chr = ''
for i in reversed(range(m)):
    if min_c == cost[i]:
        min_chr = a[i]
        break

ans = chg + ([min_chr] * (d - len(chg)))
ans.sort(reverse=True)
print(''.join(map(str, ans)))
"""

Submission status: Accepted

Solution code:
def main():
    C = [2, 5, 5, 4, 5, 6, 3, 7, 6]
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    dp = [0] + [-1] * N
    K = {a: C[a - 1] for a in A}

    for i in range(min(K.values()), N + 1):
        try:
            dp[i] = max(dp[i - v] * 10 + k for k, v in K.items() if i - v >= 0 and dp[i - v] >= 0)
        except ValueError:
            dp[i] = -1
    print(dp[N])
main()

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()


def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    Match = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
    
    dp = [(0, 0)] * (N + 1) # dp[i] = (i本のマッチで作れる最大の整数, その整数の桁数)
    for n in range(N + 1):
        for a in A:
            if n - Match[a] < 0: continue
            if n - Match[a] == 0:
                dp[n] = max(dp[n], (a, 1))
                continue
            number, l = dp[n - Match[a]]
            if number != 0: dp[n] = max(dp[n], (number + a * 10**l, l + 1))
    print(dp[N][0])

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
# import math
# from string import ascii_lowercase, ascii_upper_case, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
from copy import copy, deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)


def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1               # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    
    n, m = mi()
    A = lmi()
    # A の前処理 (同じ必要本数なのに値が小さいやつらが入っていたら削除しておく)
    if 6 in A and 9 in A:
        A.remove(6)
    if 2 in A and 5 in A:
        A.remove(2)
    if 3 in A and 5 in A:
        A.remove(3)
    if 2 in A and 3 in A:
        A.remove(2)    

    # 各数字とマッチの必要本数の対応テーブル
    num_to_match = {1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6}
    match_to_num = dict()
    for num in A:
        match_to_num[num_to_match[num]] = num

    
    needed_match = [num_to_match[num] for num in A]

    # dp[i] = (指定された数字を使い i 本全部を使って作れる最大桁数, 使用数字のカウンタ)
    dp = [[None, None] for _ in range(n + 1)]
    dp[0][0] = 0
    dp[0][1] = Counter()

    def counter_gt(c1, c2):
        # print(f"{c1} {c2}")
        return sorted(tuple(c1.items()), key=lambda x: x[0], reverse=True) > sorted(tuple(c2.items()), key=lambda x: x[0], reverse=True)

    for i in range(n + 1):
        digit_max = 0
        counter_memo = None
        for match in needed_match:
            if i - match >= 0 and dp[i - match][0] is not None:
                tmp = copy(dp[i - match][1])
                tmp[match_to_num[match]] += 1
                if dp[i - match][0] + 1 > digit_max or (dp[i - match][0] + 1 == digit_max and counter_gt(tmp, counter_memo)):
                    digit_max = dp[i - match][0] + 1
                    counter_memo = copy(dp[i - match][1])
                    counter_memo[match_to_num[match]] += 1 

        if digit_max != 0:
            dp[i][0] = digit_max
            dp[i][1] = counter_memo

    # print('')
    # for elm in dp:
    #     print(elm)
    
    char_array = [None] * dp[n][0]
    cnt = 0
    t = sorted(dp[n][1].items(), key=lambda x: x[0], reverse=True)
    for k, v in t:
        for i in range(v):
            char_array[i + cnt] = str(k)
        cnt += v
    print(''.join(char_array))




if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():

    needs = [2, 5, 5, 4, 5, 6, 3, 7, 6]
    N, M = map(int, input().split())
    A = sorted(list(map(int, input().split())), reverse=True)

    dp = [-1]*(N+1)
    # 初期条件
    dp[0] = 0

    # ループ
    for a in A:
        na = needs[a-1]
        for i in range(N+1):
            if i-na >= 0:
                if dp[i-na] == -1:
                    continue
                dp[i] = max(dp[i], dp[i-na]*10+a)

    print(dp[N])


resolve()

Submission status: Accepted

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

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

dp = [-1] * (N + 10)
dp[0] = 0
for i in range(N + 1):
    if dp[i] == -1:
        continue
    for a in A:
        dp[i + M_lst[a]] = max(dp[i + M_lst[a]], dp[i] * 10 + a)
print(dp[N])

Submission status: Accepted

Solution code:
# D - Match Matching

N, M = map(int, input().split())
A = list(int(x) for x in input().split())
match_list = [('0', 6), ('1', 2), ('2', 5), ('3', 5), ('4', 4), ('5', 5), ('6', 6), ('7', 3), ('8', 7), ('9', 6)]
MA = []
for a in A:
    MA.append(match_list[a])
MA.sort(key=lambda x: x[0], reverse=True)

# dp[i] := i本のマッチを使って作れる最大桁数
dp = [-1] * (N+1)
dp[0] = 0
for i in range(N+1):
    for j in range(M):
        if i-MA[j][1] >= 0:
            dp[i] = max(dp[i], dp[i-MA[j][1]] + 1)

remain_keta = dp[N]
remain_match = N
ans = ''
for i in range(dp[N]):
    for ma in MA:
        # 大きい数字から一桁使った時に、
        # 残り桁がちょうど一桁減っている場合
        if remain_match >= ma[1] and dp[remain_match - ma[1]] == remain_keta - 1:
            ans +=  ma[0]
            remain_keta -= 1
            remain_match -= ma[1]
            break

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
try:
    from typing import Dict, List
except ImportError:
    pass


def solve(N: int, M: int, A: "List[int]"):
    mn = [6, 2, 5, 5, 4, 5, 6, 3, 7, 6]
    A.sort(reverse=True)
    dp = [-1] * (N + 1)
    dp[0] = 0
    for i in range(1, N + 1):
        m = -1
        for Ai in A:
            if i - mn[Ai] >= 0 and dp[i - mn[Ai]] >= 0:
                m = max(m, dp[i - mn[Ai]] + 1)
        if m >= 0:
            dp[i] = m
    assert dp[N] >= 0
    k = N
    res = []  # type: List[int]
    while dp[k]:
        for Ai in A:
            if k - mn[Ai] >= 0 and dp[k - mn[Ai]] == dp[k] - 1:
                res.append(Ai)
                k -= mn[Ai]
                break

    print("".join(str(d) for d in res))


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]"
    solve(N, M, A)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def num_to_match(n):
    if n == 1:
        return 2
    elif n == 7:
        return 3
    elif n == 4:
        return 4
    elif n in [2, 3, 5]:
        return 5
    elif n in [6, 9]:
        return 6
    else:
        return 7


def max_length(N, match):
    match = set(match)
    INF = 10**15
    dp = [- INF for _ in range(N + 1)]
    dp[0] = 0
    for n in range(1, N + 1):
        max_l = dp[n]
        for m in match:
            if n - m >= 0 and dp[n - m] >= 0:
                max_l = max([max_l, 1 + dp[n - m]])
        dp[n] = max_l
    return dp


def main():
    N, _ = list(map(int, input().split(' ')))
    A = list(map(int, input().split(' ')))
    A.sort(reverse=True)
    match = list(map(num_to_match, A))
    max_l = max_length(N, match)
    digits = [0 for _ in range(max_l[N])]
    n_match = N
    for i in range(max_l[N]):
        for a in A:
            ma = num_to_match(a)
            if n_match - ma < 0:
                continue
            if max_l[n_match - ma] == max_l[n_match] - 1:
                digits[i] = a
                n_match -= ma
                break
    print(''.join(map(str, digits)))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
a = list(map(int, input().split()))
matchlist = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
numberlist = []
for i in range(m):
    numberlist.append(matchlist[a[i]])
numberlist = set(numberlist)
#dp[i]:i本でのmax桁
dp = [-10000000]*(n+1)
dp[0] = 0
for i in range(n):
    for j in numberlist:
        if i+j <= n:
            dp[i+j] = max(dp[i+j], dp[i]+1)


ans = []
d = dp[n]
a.sort(reverse = True)
for i in range(d):
    for j in a:
        if n - matchlist[j] >= 0:
            if dp[n] == dp[n-matchlist[j]] + 1:
                n -= matchlist[j]
                ans.append(j)
                break
print("".join(map(str,ans)))

Submission status: Accepted

Solution code:
from collections import defaultdict

def f(a, b):
    for i in range(9,0,-1):
        if a[i] == b[i]: continue
        elif a[i] > b[i]:
            return True
        else:
            return False
    return False

N, M = map(int, input().split())
se = set()
A = list(map(int, input().split()))
toNum = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [[] for i in range(N+1)]
done = [False for i in range(N+10)]
done[N] = True
dics = [defaultdict(int) for i in range(N+1)]
for i in range(N-1, -1, -1):
    for a in A:
        num = toNum[a]
        if not done[i+num]: continue
        l = len(dp[i+num])+1
        d = dics[i+num].copy()
        d[a] += 1
        if l > len(dp[i]) or (l == len(dp[i]) and f(d, dics[i])):
            dp[i] = dp[i+num] + [a]
            done[i] = True
            dics[i] = d
dp[0].sort(reverse=True)
print(*dp[0], sep='')

Submission status: Accepted

Solution code:
# Python3 (3.4.3)
import sys
input = sys.stdin.readline

# -------------------------------------------------------------
# function
# -------------------------------------------------------------


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

# 各数字に必要なマッチの本数
num = [0,2,5,5,4,5,6,3,7,6]

# dp : i本のマッチで作ることが可能な最大の桁数
dp = [-float("inf")]*(N+1)
# dp初期化 
#   - 0本 -> 0桁
#   - 各数字を1つ作る場合は1桁
dp[0] = 0
for a in A:
    if num[a] <= N:
        dp[num[a]] = 1

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

# 復元
A.sort(reverse=True)
ans = ""
for i in range(dp[N]):
    for a in A:
        if N-num[a] >= 0 and dp[N-num[a]] == dp[N]-1:
            ans += str(a)
            N -= num[a]
            break

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
N,M,*A = map(int, open(0).read().split())
ls = [0]*10
ls[1] = 2
ls[2] = 5
ls[3] = 5
ls[4] = 4
ls[5] = 5
ls[6] = 6
ls[7] = 3
ls[8] = 7
ls[9] = 6
dic = defaultdict(int)
for a in A:
  k = ls[a]
  dic[k] = max(dic[k],a)
dp = [-1]*(N+1)
for k in dic.keys():
  if k>N:
    continue
  dp[k] = dic[k]
for i in range(N+1):
  for k in dic.keys():
    if i-k>0 and dp[i-k]!=-1:
      m = dp[i-k]*10+dic[k]
      dp[i] = max(dp[i], m)
print(dp[N])

Submission status: Accepted

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

if 1 in A:
    if N%2==0:
        print("1"*(N//2))
    else:
        if 7 in A:
            print("7"+"1"*(N//2-1))
        elif 5 in A:
            print("5"+"1"*(N//2-2))
        elif 3 in A:
            print("3"+"1"*(N//2-2))
        elif 2 in A:
            print("2"+"1"*(N//2-2))
        else:
            print("8"+"1"*(N//2-3))
elif 7 in A:
    if N%3==0:
        print("7"*(N//3))
    elif N%3==1:
        if 4 in A:
            print("7"*(N//3-1)+"4")
        elif 8 in A:
            print("8"+"7"*(N//3-2))
        elif 5 in A:
            print("7"*(N//3-3)+"55")
        elif 3 in A:
            print("7"*(N//3-3)+"33")
        elif 2 in A:
            print("7"*(N//3-3)+"22")
    else:
        if 5 in A:
            print("7"*(N//3-1)+"5")
        elif 3 in A:
             print("7"*(N//3-1)+"3")
        elif 2 in A:
            print("7"*(N//3-1)+"2")
        elif 4 in A:
            print("7"*(N//3-2)+"44")
        elif 8 in A:
            print(print("7"*(N//3-4)+"88"))

else:
    B=[[] for i in range(0,10)]
    for i in range(0,M):
        if 2 in A:
            B[5].append(2)
        if 3 in A:
            B[5].append(3)
        if 4 in A:
            B[4].append(4)
        if 5 in A:
            B[5].append(5)
        if 6 in A:
            B[6].append(6)
        if 8 in A:
            B[7].append(8)
        if 9 in A:
            B[6].append(9)


    dp=['n' for i in range(0,max(10,N+1))]
    for i in range(0,min(N+1,10)):
        if i==2:
            if 2 in A:
                dp[5]='2'
        if i==3:
            if 3 in A:
                dp[5]='3'
        if i==4:
            if 4 in A:
                dp[4]='4'
        if i==5:
            if 5 in A:
                dp[5]='5'
        if i==6:
            if 6 in A:
                dp[6]='6'
        if i==8:
            if 8 in A:
                dp[7]='8'
        if i==9:
            if 9 in A:
                dp[6]='9'

    if N>=6:
        a='0'
        b='0'
        c='0'
        if dp[6]=='n':
            a=int(a)
            b=int(b)
            c=int(c)
            x=max(a,b,c)
            if x!=0:
                dp[6]=str(x)
        else:
            a=int(a)
            b=int(b)
            c=int(c)
            d=int(dp[6])
            dp[6]=str(max(a,b,c,d))

    if N>=7:
        a='0'
        b='0'
        c='0'
        d='0'
        if dp[7]=='n':
            a=int(a)
            b=int(b)
            c=int(c)
            d=int(d)
            x=max(a,b,c,d)
            if x!=0:
                dp[7]=str(x)
        else:
            a=int(a)
            b=int(b)
            c=int(c)
            d=int(d)
            e=int(dp[7])
            dp[7]=str(max(e,a,b,c,d))

    for i in range(8,N+1):
        a='0'
        b='0'
        c='0'
        d='0'
        e='0'
        f='0'
        if B[4] and dp[i-4]!='n':
            c='4'+dp[i-4]
        if B[5] and dp[i-5]!='n':
            d=str(max(B[5]))+dp[i-5]
        if B[6] and dp[i-6]!='n':
            e=str(max(B[6]))+dp[i-6]
        if B[7] and dp[i-7]!='n':
            f='8'+dp[i-7]
        a=int(a)
        b=int(b)
        c=int(c)
        d=int(d)
        e=int(e)
        f=int(f)
        x=max(a,b,c,d,e,f)
        if x==0:
            dp[i]='n'
        else:
            dp[i]=str(x)
    print(int(dp[N]))

Submission status: Accepted

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

if 1 in A:
    if N%2==0:
        print("1"*(N//2))
    else:
        if 7 in A:
            print("7"+"1"*(N//2-1))
        elif 5 in A:
            print("5"+"1"*(N//2-2))
        elif 3 in A:
            print("3"+"1"*(N//2-2))
        elif 2 in A:
            print("2"+"1"*(N//2-2))
        else:
            print("8"+"1"*(N//2-3))
else:
    B=[[] for i in range(0,10)]
    for i in range(0,M):
        if 2 in A:
            B[5].append(2)
        if 3 in A:
            B[5].append(3)
        if 4 in A:
            B[4].append(4)
        if 5 in A:
            B[5].append(5)
        if 6 in A:
            B[6].append(6)
        if 7 in A:
            B[3].append(7)
        if 8 in A:
            B[7].append(8)
        if 9 in A:
            B[6].append(9)


    dp=['n' for i in range(0,max(10,N+1))]
    for i in range(0,min(N+1,10)):
        if i==2:
            if 2 in A:
                dp[5]='2'
        if i==3:
            if 3 in A:
                dp[5]='3'
        if i==4:
            if 4 in A:
                dp[4]='4'
        if i==5:
            if 5 in A:
                dp[5]='5'
        if i==6:
            if 6 in A:
                dp[6]='6'
        if i==7:
            if 7 in A:
                dp[3]='7'
        if i==8:
            if 8 in A:
                dp[7]='8'
        if i==9:
            if 9 in A:
                dp[6]='9'

    if N>=6:
        a='0'
        b='0'
        c='0'
        if B[3]!=[]:
            b='77'
        if dp[6]=='n':
            a=int(a)
            b=int(b)
            c=int(c)
            x=max(a,b,c)
            if x!=0:
                dp[6]=str(x)
        else:
            a=int(a)
            b=int(b)
            c=int(c)
            d=int(dp[6])
            dp[6]=str(max(a,b,c,d))

    if N>=7:
        a='0'
        b='0'
        c='0'
        d='0'
        if B[3]!=[] and dp[4]!='n':
            b='7'+dp[4]
        if B[4]!=[] and dp[3]!='n':
            c='47'
        if dp[7]=='n':
            a=int(a)
            b=int(b)
            c=int(c)
            d=int(d)
            x=max(a,b,c,d)
            if x!=0:
                dp[7]=str(x)
        else:
            a=int(a)
            b=int(b)
            c=int(c)
            d=int(d)
            e=int(dp[7])
            dp[7]=str(max(e,a,b,c,d))

    for i in range(8,N+1):
        a='0'
        b='0'
        c='0'
        d='0'
        e='0'
        f='0'
        if B[3] and dp[i-3]!='n':
            b='7'+dp[i-3]
        if B[4] and dp[i-4]!='n':
            c='4'+dp[i-4]
        if B[5] and dp[i-5]!='n':
            d=str(max(B[5]))+dp[i-5]
        if B[6] and dp[i-6]!='n':
            e=str(max(B[6]))+dp[i-6]
        if B[7] and dp[i-7]!='n':
            f='8'+dp[i-7]
        a=int(a)
        b=int(b)
        c=int(c)
        d=int(d)
        e=int(e)
        f=int(f)
        x=max(a,b,c,d,e,f)
        if x==0:
            dp[i]='n'
        else:
            dp[i]=str(x)
    print(int(dp[N]))

Submission status: Accepted

Solution code:
N, M = map(int,input().split())
A = list(map(int,input().split()))
A.sort(reverse = True)
d = [0,2,5,5,4,5,6,3,7,6]
S = set()
for a in A:
    S.add(d[a])

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

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

ans = 0
digit = dp[N]

for i in range(digit-1, -1, -1):
    if i != 0:
        for a in A:
            if dp[N-d[a]] == i:
                ans = ans * 10 + a
                N -= d[a]
                break
    else:
        for a in A:
            if N == d[a]:
                ans = ans * 10 + a
                break
print(ans)

Submission status: Accepted

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

d1 = {1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}
d2 = {2:[1],3:[7],4:[4],5:[5,3,2],6:[9,6],7:[8]}

# dp[i]:i本のマッチを使用した場合の最大桁数
dp = [-float('inf') for _ in range(n+1)]
dp[0] = 0
for i in range(1,n+1):
  for ai in a:
    if i-d1[ai] >= 0:
      dp[i] = max(dp[i-d1[ai]]+1,dp[i])

a.sort(reverse = True)
ans = ''
r = n
k = dp[n]
while(r > 0):
  for ai in a:
    if r-d1[ai] >= 0 and dp[r-d1[ai]] == k-1:
      ans += str(ai)
      r -= d1[ai]
      k -= 1
      break

print(ans)

Submission status: Accepted

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

T=[0,2,5,5,4,5,6,3,7,6]
B=[]
for i in A:
    B.append(T[i])
B=sorted(list(set(B)))
dp=[0 for i in range(N+1)]
AB=[[i,T[i]] for i in A]
AB=sorted(AB,reverse=True)

for i in range(1,N+1):
    for j in B:
        if i-j>=0 and dp[i-j]!=-1:
            dp[i]=max(dp[i],dp[i-j]+1)
            #print(i,j,dp[i])
    if dp[i]==0:
        dp[i]=-1
#print(dp)
#print(AB)

c=N
U=[0 for i in range(8)]
while c>0:
    for i in range(len(AB)):
        if c-AB[i][1]>=0 and dp[c]==dp[c-AB[i][1]]+1:
            U[AB[i][1]]+=1
            c-=AB[i][1]
            break
#print(U)

ans=""
if 9 in A:
    ans+='9'*U[6]
    U[6]=0
if 8 in A:
    ans+='8'*U[7]
if 7 in A:
    ans+='7'*U[3]
if 6 in A:
    ans+='6'*U[6]
if 5 in A:
    ans+='5'*U[5]
    U[5]=0
if 4 in A:
    ans+='4'*U[4]
if 3 in A:
    ans+='3'*U[5]
    U[5]=0
if 2 in A:
    ans+='2'*U[5]
if 1 in A:
    ans+='1'*U[2]

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline

def main():
    N,M = map(int,input().split())
    a = list(map(int,input().split()))
    d = [-1,2,5,5,4,5,6,3,7,6]
    
    keta = [-1]*(N+10)
    keta[0] = 0
    
    for i in range(N):
        for num in a:
            if keta[i] != -1:
                keta[i+d[num]] = keta[i]+1

    use = N
    
    ans = [-1]*(N+10)
    ans[0] = 0
    for i in range(N):
        for num in a:
            if keta[i+d[num]] == keta[i]+1:
                ans[i+d[num]] = max(ans[i+d[num]],ans[i]*10+num)
    
    print(ans[N])
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
a=list(map(int,input().split()))
d=dict()
need=[0,2,5,5,4,5,6,3,7,6]
for i in range(m):
    if need[a[i]] not in d:
        d[need[a[i]]]=a[i]
    else:
        if a[i]>d[need[a[i]]]:
            d[need[a[i]]]=a[i]
d=list(d.items())
d.sort()
m=len(d)
dp=[[-1]*10 for _ in range(n+1)]
dp[0]=[0]*10
for i in range(n+1):
    for j in range(m):
        if i-d[j][0]>=0 and dp[i-d[j][0]][0]!=-1:
            if dp[i][0]==dp[i-d[j][0]][0]+1:
                ok=False
                for k in reversed(range(1,10)):
                    if k==d[j][1]:
                        if dp[i][k]<dp[i-d[j][0]][k]+1:
                            ok=True
                            break
                        if dp[i][k]>dp[i-d[j][0]][k]+1:
                            break
                    else:
                        if dp[i][k]<dp[i-d[j][0]][k]:
                            ok=True
                            break
                        if dp[i][k]>dp[i-d[j][0]][k]:
                            break
                if ok:
                    for k in range(10):
                        dp[i][k]=dp[i-d[j][0]][k]
                    dp[i][d[j][1]]+=1
                    dp[i][0]+=1
            elif dp[i][0]<dp[i-d[j][0]][0]+1:
                for k in range(10):
                    dp[i][k]=dp[i-d[j][0]][k]
                dp[i][d[j][1]]+=1
                dp[i][0]+=1
ans=str()
for i in reversed(range(1,10)):
    ans+=str(i)*dp[-1][i]
print(ans)
#print(d)
#print(dp[-1])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
INF = float("inf")
# 解説参照

def main():
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort(reverse=True)  # 使用可能は数字は大きい順にソートしておく
    cost = [-1, 2, 5, 5, 4, 5, 6, 3, 7, 6]
    # dp[i]:= マッチi本で作れる最大桁数
    dp = [-1] * (n + 1)
    dp[0] = 0
    for i in range(1, n + 1):
        for aj in a:
            if i - cost[aj] < 0:
                continue
            dp[i] = max(dp[i], dp[i - cost[aj]] + 1)
    digits = dp[n]
    ans = ""
    rest = n
    # 上から貪欲
    while digits:
        for aj in a:
            if rest - cost[aj] < 0:
                continue
            if dp[rest - cost[aj]] == digits - 1:
                ans += str(aj)
                rest -= cost[aj]
                digits -= 1
                break
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

A=list(map(int,input().split()))
A.sort(reverse=True)
honsuu=[0,2,5,5,4,5,6,3,7,6]

def ketadp(N,M,A):
  dp=[0]*(N+1)
  for i in range(N):
    for j in A:
      if (i+1-honsuu[j])==0 or (i+1-honsuu[j]>0 and dp[i+1-honsuu[j]]!=0):
        dp[i+1]=max(dp[i+1],dp[i+1-honsuu[j]]+1)
  return dp
  

ans=""
keta=ketadp(N,M,A)
remain=keta[N]
match=N
#print(keta)

while(match>0):
  for i in A:
    #print(i,match,remain,keta[match-honsuu[i]])
    if match-honsuu[i]<0:
      continue;
    if(keta[match-honsuu[i]]==remain-1) and not (match-honsuu[i]!=0 and remain==1):
      ans+=str(i)
      remain-=1
      match-=honsuu[i]
      break;
print(ans)

Submission status: Accepted

Solution code:
import math
from collections import Counter
n, m = map(int, input().split())
a = list(map(int, input().split()))

if 9 in a and 6 in a:
    a.remove(6)
if 5 in a:
    if 2 in a:
        a.remove(2)
    if 3 in a:
        a.remove(3)
if 3 in a and 2 in a:
    a.remove(2)

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

dp = [None] * (n+1)
dp[0] = Counter([])

int_dp = [0] * (n+1)

for i in range(1, n+1):
    for j in a:
        if i >= req_m[j] and dp[i-req_m[j]] is not None:
            v = dp[i-req_m[j]] + Counter([j])
            if dp[i] is None:
                dp[i] = v
            else:
                if sum(dp[i].values()) < sum(v.values()):
                    dp[i] = v
                elif sum(dp[i].values()) == sum(v.values()):
                    if sorted(dp[i].elements(), reverse=True) < sorted(v.elements(), reverse=True):
                        dp[i] = v

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

Submission status: Accepted

Solution code:
# dpに最大桁数を持たせる
N,M = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)
f = [-1, 2,5,5,4,5,6,3,7,6] # 1-indexed

# dp[i]: マッチi本数で作れる最大の桁数(int)
dp = [-float('inf')]*(N+1)
dp[0] = 0
for i in range(N+1):
    nxt = dp[i]
    for aj in A:
        if i-f[aj]<0: continue
        nxt = max(nxt, 
                  dp[i-f[aj]] + 1)
    dp[i] = nxt
    #print(dp)
#print(dp[N])
keta = dp[N]
ans = ""
matchs = N
# 上位の桁から貪欲に
while keta>0:
    for aj in A:
        if matchs-f[aj] < 0: continue
        if dp[matchs-f[aj]] == keta-1:
            ans += str(aj)
            matchs -= f[aj]
            keta -= 1
            break
print(ans)

Submission status: Accepted

Solution code:
# 解説放送の１つめ
N,M = map(int, input().split())
A = list(map(int, input().split()))
f = [-1, 2,5,5,4,5,6,3,7,6] # 1-indexed

# dp[i]: マッチi本数で作れる最大の数(str)
dp = [None]*(N+1)
dp[0] = ""

# strの数の大きいほう
def max_str(s1:str, s2:str)->str:
    """return bigger one"""
    l1, l2 = len(s1), len(s2)
    if l1 != l2:
        return s1 if l1>l2 else s2
    if l1 == l2: 
        return s1 if s1>s2 else s2
    
for i in range(2, N+1):
    nxt = ""
    for aj in A:
        # 配列外参照と，i本ちょうどで作れないものはだめ
        if i-f[aj]<0 or dp[i-f[aj]]==None: continue
        nxt = max_str(nxt, 
                      dp[i-f[aj]]+str(aj))
    if nxt!="":
        dp[i] = nxt
    #print(dp)
print(dp[N])

Submission status: Accepted

Solution code:
def max_for_str(a, b):
    if len(a) > len(b):
        return a
    elif len(a) < len(b):
        return b
    else:#This case is unlikely to happen.
        for c1, c2 in zip(a, b):
            if c1 > c2:
                return a
            elif c1 < c2:
                return b
        return a
            
match = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]

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

dp = [None] * (N+1)
dp[0] = ""

for i in range(N+1):
    for A in As:
        if i - match[int(A)] >= 0 and not dp[i - match[int(A)]] is None:
            if dp[i] is None:
                dp[i] = A + dp[i - match[int(A)]]
            else:
                dp[i] = max_for_str(dp[i] , A + dp[i - match[int(A)]])

print(dp[N])