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:
n,m=map(int, input().split())  #複数数値入力
A=list(map(int, input().split()))  #リスト入力（数値)
num = [-1, 2, 5, 5, 4, 5, 6, 3, 7, 6]

A.sort(reverse=True)    # 大きい順に並べる

dp = [-1*float("inf")]*(n+1)    # その本数で作れる最大の桁数
# dp初期化 (0本では0桁, 各数字を1つ作る場合は1桁)
dp[0] = 0
for a in A:
    if num[a] <= n:
        dp[num[a]] = 1

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)

ans = ""
for i in range(dp[n]):  # 1桁ずつ考える
    for a in A: # 使える数1つずつ大きい方から考える
        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:
N, M = map(int, input().split())
A = list(map(int, input().split()))
num = [0, 2, 5, 5, 4, 5 ,6, 3, 7, 6]
dp = ["" for i in range(N+30)]
for i in range(N):
    if i!=0 and dp[i]=="":
        continue
    for a in A:
        tmpscore = dp[i]+str(a)
        if len(dp[i+num[a]]) < len(tmpscore):
            dp[i+num[a]] = tmpscore
        elif len(dp[i+num[a]]) > len(tmpscore):
            continue
        else:
            dp[i+num[a]] = max(dp[i+num[a]], tmpscore)
print(dp[N])

Submission status: Accepted

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 = ["" for i in range(50000)]
for i in range(N):
    if i!=0 and dp[i]=="":
        continue
    for a in A:
        if dp[i+num[a]] == "":
            dp[i+num[a]] = dp[i] + str(a)
        else:
            tmpscore = dp[i]+str(a)
            if len(dp[i+num[a]]) < len(tmpscore):
                dp[i+num[a]] = tmpscore
            elif len(dp[i+num[a]]) > len(tmpscore):
                continue
            else:
                dp[i+num[a]] = max(dp[i+num[a]], tmpscore)
print(dp[N])

Submission status: Accepted

Solution code:
# coding: utf-8
import sys

# import bisect
# import math
# import itertools

# import numpy as np


"""Template"""


class IP:
    """
    入力を取得するクラス
    """

    def __init__(self):
        self.input = sys.stdin.readline

    def I(self):
        """
        1文字の取得に使います
        :return: int
        """
        return int(self.input())

    def S(self):
        """
        1文字の取得(str
        :return: str
        """
        return self.input()

    def IL(self):
        """
        1行を空白で区切りリストにします(int
        :return: リスト
        """
        return list(map(int, self.input().split()))

    def SL(self):
        """
        1行の文字列を空白区切りでリストにします
        :return: リスト
        """
        return list(map(str, self.input().split()))

    def ILS(self, n):
        """
        1列丸々取得します(int
        :param n: 行数
        :return: リスト
        """
        return [int(self.input()) for _ in range(n)]

    def SLS(self, n):
        """
        1列丸々取得します（str
        :param n: 行数
        :return: リスト
        """
        return [self.input() for _ in range(n)]

    def SILS(self, n):
        """
        Some Int LineS
        横に複数、縦にも複数
        :param n: 行数
        :return: list
        """
        return [self.IL() for _ in range(n)]

    def SSLS(self, n):
        """
        Some String LineS
        :param n: 行数
        :return: list
        """
        return [self.SL() for _ in range(n)]


class Idea:
    def __init__(self):
        pass

    def HF(self, p):
        """
        Half enumeration
        半分全列挙です
        pの要素の和の組み合わせを作ります。
        ソート、重複削除行います
        :param p: list : 元となるリスト
        :return: list : 組み合わせられた和のリスト
        """
        return sorted(set(p[i] + p[j] for i in range(len(p)) for j in range(i, len(p))))

    def Bfs2(self, a):
        """
        bit_full_search2
        bit全探索の改良版
        全探索させたら2進数のリストと10進数のリストを返す
        :return: list２つ : １個目 2進数(16桁)  2個目 10進数
        """
        # 参考
        # https://blog.rossywhite.com/2018/08/06/bit-search/
        # https://atcoder.jp/contests/abc105/submissions/4088632
        value = []
        for i in range(1 << len(a)):
            output = []

            for j in range(len(a)):
                if self.bit_o(i, j):
                    """右からj+1番目のiが1かどうか判定"""
                    # output.append(a[j])
                    output.append(a[j])
            value.append([format(i, 'b').zfill(16), sum(output)])

        value.sort(key=lambda x: x[1])
        bin = [value[k][0] for k in range(len(value))]
        val = [value[k][1] for k in range(len(value))]
        return bin, val

    def S(self, s, r=0, m=-1):
        """
        ソート関係行います。色々な設定あります。
        :param s: 元となるリスト
        :param r: reversするかどうか 0=False 1=True
        :param m: （2次元配列）何番目のインデックスのソートなのか
        :return: None
        """
        r = bool(r)
        if m == -1:
            s.sort(reverse=r)
        else:
            s.sort(reverse=r, key=lambda x: x[m])

    def bit_n(self, a, b):
        """
        bit探索で使います。0以上のときにTrue出します
        自然数だからn
        :param a: int
        :param b: int
        :return: bool
        """
        return bool((a >> b & 1) > 0)

    def bit_o(self, a, b):
        """
        bit探索で使います。1のときにTrue出すよ
        oneで1
        :param a: int
        :param b: int
        :return: bool
        """
        return bool(((a >> b) & 1) == 1)

    def ceil(self, x, y):
        """
        Round up
        小数点切り上げ割り算
        :param x: int
        :param y: int
        :return: int
        """
        return -(-x // y)

    def ave(self, a):
        """
        平均を求めます
        :param a: list
        :return: int
        """
        return sum(a) / len(a)

    def gcd(self, x, y):
        if y == 0:
            return x
        else:
            return self.gcd(y, x % y)


"""ここからメインコード"""


def main():
    # 1文字に省略
    r, e = range, enumerate
    ip = IP()
    id = Idea()

    """この下から書いてね"""
    n, m = ip.IL()
    a = ip.IL()
    c = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
    f = [-1] * 10010
    f[0] = 0

    for i in r(n):
        i += 1
        for x in a:
            if i - c[x] >= 0:
                f[i] = max(f[i], f[i - c[x]] * 10 + x)

    print(f[n])


main()

Submission status: Accepted

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

A.sort(reverse=True)

# 各数字に必要なマッチの本数
num  = [0,2,5,5,4,5,6,3,7,6]
# dp : i本のマッチで実現できる最大の桁数
dp = [-1*float("inf")]*(N+1)
# dp初期化 (0本では0桁, 各数字を1つ作る場合は1桁)
dp[0] = 0
for a in A:
    if num[a] <= N:
        dp[num[a]] = 1

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)

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:
n, m = map(int, input().split())
lst = list(map(int, input().split()))
lst = sorted(lst, key = lambda x:-x)
dic = {1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6}

s = set()
for i in lst:
    s.add(dic[i])
s = list(sorted(s))

dp = [0] * (n+1)
for i in range(0, n+1):
    a = 0
    max_a = 0
    for j in s:
        if i-j < 0:
            pass
        elif i == j:
            a = 1
        elif i - j > 0 and dp[i-j] > 0:
            a = dp[i-j] + 1
        if max_a < a:
            max_a = a
    dp[i] = max_a

ans = ''
ans_digit = dp[n]
while len(ans) < ans_digit:
    if len(ans) == ans_digit-1:
        for i in lst:
            if n == dic[i]:
                ans += str(i)
                break
    else:
        for i in lst:
            if n - dic[i] >= 0:
                if dp[n] -1 == dp[n-dic[i]]:
                    ans += str(i)
                    n -= dic[i]
                    break
    
print(ans)

Submission status: Accepted

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

A.sort(reverse=True)

# 各数字に必要なマッチの本数
num  = [0,2,5,5,4,5,6,3,7,6]
# dp : i本のマッチで実現できる最大の桁数
dp = [-1*float("inf")]*(N+1000)
# dp初期化 (0本では0桁, 各数字を1つ作る場合は1桁)
dp[0] = 0
for a in A:
    dp[num[a]] = 1

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)

ans = ""
for i in range(dp[N]):
    for a in A:
        if dp[N-num[a]] == dp[N]-1  and  N-num[a] >= 0:
            ans += str(a)
            N -= num[a]
            break

print(ans)

Submission status: Accepted

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

N, M = map(int, input().split())
A = list(map(int, input().split()))
neginf = -1 * 1e20
D = [neginf]*(N+1)

def dp(n_match):
    D[0] = 0
    for n in range(1,n_match+1):
        arr = [D[n-costs[a-1]] if n-costs[a-1]>=0 else neginf for a in A]
        if max(arr) < 0:
            continue

        D[n] = max(arr)+1

def main():
    dp(N)
    n = N
    ans = ''
    while n>0:
        arr = [ a for a in A if n-costs[a-1] >= 0 and D[n-costs[a-1]]==D[n]-1 ]
        if len(arr)>0:
            a = max(arr)
            ans += str(a)
            n -= costs[a-1]
        # else:
        #     break
    print(ans)

main()

Submission status: Accepted

Solution code:
#!/mnt/c/Users/moiki/bash/env/bin/python
N,M = map(int, input().split())

cost = [0,2,5,5,4,5,6,3,7,6]
A =list(map(int, input().split()))
dp = [-1]*(N+1)
dp[0] = 0

for i in range(N):
    if dp[i] == -1:
        continue
    for c,a in zip( [cost[a] for a in A], A):
        if i + c <= N:
            dp[i+c] = dp[i]+1

# print(dp)
i = N
ans = ""
A = sorted(A, reverse=True)
while i > 0:
    for c,a in zip([cost[a] for a in A], A):
        if i-c >= 0 and dp[i-c] == dp[i]-1:
            ans += str(a)
            i -= c
            break # difficult !! 

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Feb 16 19:31:10 2019
ABC118D
@author: maezawa
"""
import copy

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

nmatch = [2,5,5,4,5,6,3,7,6]
rmatch = list(reversed(nmatch))
nmdic = dict([(i+1,nmatch[i]) for i in range(9)])
#nums = [[],[],[1],[7],[4],[2,3,5],[6,9],[8]]
nums = [[] for _ in range(10)]
for  i in a:
    nums[nmdic[i]].append(i)
        
#print(nmdic)
#print(nums)

dp = [[-1,[]] for _ in range(n+1)]
dp[0] = [0, []]
#print(dp)

for i in range(1, n+1):
    cnds = []
    for k in a:
        j = nmdic[k]
        if i-j < 0:
            continue
        if dp[i-j][0] == -1:
            continue
        cndo = dp[i-j][0]+1
        cndos = copy.copy(dp[i-j][1])
        cndos.append(max(nums[j]))
        cnds.append([cndo, cndos])
        #print(i, i-j, cnds, cndos)
    if cnds == []:
        continue
    dp[i] = max(cnds, key=lambda x: x[0])

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

Submission status: Accepted

Solution code:
import numpy as np

#initialization
nmatch = np.array([0,2,5,5,4,5,6,3,7,6])
N,M = map(int,input().split())
dp = [-1]*(N+1) # contains the number of digits it can make
dp[0] = 0
ff = np.array(list(map(int,input().split()))).reshape(-1,1)
fg = nmatch[ff].reshape(-1,1)
Atemp = np.concatenate([ff,fg],axis=1)
index0 = np.argsort(Atemp[:,0])
index1 = np.argsort(Atemp[:,1])
A = Atemp[index1] #sorted by the number of matches: ascending
B = Atemp[index0]
B = B[::-1] #sorted by the number: descending
for i in range(1,N+1):
    for k in range(M):
        j = A[k,1]
        i_old = i - j #available matches
        if (i-j) < 0:
            break
        if (i-j) == 0 and dp[i] == -1:
            dp[i] = 1
        if dp[i_old] != -1 and dp[i_old]+1 > dp[i]:
            dp[i] = dp[i_old] + 1
#print(dp)
ndigits = dp[N]
j = N
final_number = ''
for l in range(ndigits,0,-1):
    index = 0
    while True:
        temp_j = j - B[index,1]
        if temp_j < 0:
            index += 1
            continue
        if dp[temp_j] + 1 == dp[j]:
            final_number += str(B[index,0])
            j = temp_j
            break
        else:
            index += 1
        if index > M:
            break
print(int(final_number))

Submission status: Accepted

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 = []
    least_len = -1
    for l,a in sd:
        if i-l < 0: break
        if dp[i-l] is None: continue
        if cands and sum(dp[i-l].values())+1 < least_len:
            continue
        cands.append(copy(dp[i-l]))
        cands[-1][a] += 1
        least_len = sum(cands[-1].values())
    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: Accepted

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

''' 再帰が深すぎて, 再起不能
def solve(yoshida, possible, dp):
    if(yoshida == 0):
        dp[0] = 0
    elif(dp[yoshida] == -1):
        for x in possible:
            if(yoshida >= cost[x]):
                idx = yoshida - cost[x]
                solve(idx, possible, dp)
                a = (dp[idx]) * 10 + x
                dp[yoshida] = max(dp[yoshida], a)
'''

def solve(yoshida, possible, dp):
    dp[0] = 0
    for i in range(n):
        a = 10 * dp[i]
        for x in possible:
            dp[i + cost[x]] = max(dp[i + cost[x]], a + x)
if __name__ == '__main__':
    n, m = map(int, input().split())
    lst = list(map(int, input().split(" ")))
    DP = [-1] * (n + 10)
    solve(n, lst, DP)
    '''
    for i in range(n + 1):
        print("{} : {}".format(i, DP[i]))
    '''
    print(DP[n])

Submission status: Accepted

Solution code:
n, m = [int(i) for i in input().split(" ")]
a = [int(i) for i in input().split(" ")]

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

c = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
a.sort()
a = a[::-1]

for i in range(1, n + 1):
    l = -1
    argl = 0
    pl = 0
    for j in range(0, m):
        p = i - c[a[j]]
        if p >= 0 and dp[p] > l:
            l = dp[p]
            argl = j
            pl = p
    if l < 0:
        dp[i] = -1
    else:
        dp[i] = l + 1
        s[i] = a[argl]
        b[i] = pl

bi = n
u = ""
while bi > 0:
    u += str(s[bi])
    bi = b[bi]

print(u)

Submission status: Accepted

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

items = {
    1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6
}
dp = ["-"] * (N + 10000)

dp[0] = ""


def max_str(s, t):
    if s == "-":
        return t
    elif len(s) < len(t):
        return t
    elif len(s) == len(t):
        if s < t:
            return t
        else:
            return s
    else:
        return s


for i in range(N + 1):
    if dp[i] == "-":
        continue
    for a in a_list:
        dp[i + items[a]] = max_str(dp[i + items[a]], dp[i] + str(a))

print(dp[N])

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))
num = [2, 5, 5, 4, 5, 6, 3, 7, 6]
ans = {}
for i in range(N + 1):
    x = 0
    for j in A:
        k = num[j - 1]
        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)
    ans[i] = x
print(ans[N])

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
A = [int(a) for a in input().split()]
L = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
A.sort(reverse = True)
#print(A)
dp = [0] + ([-1]*N)
#print(dp)
for i in range(1, N+1):
    for a in A:
        if L[a] <= i:
            dp[i] = max(dp[i], dp[i-L[a]] * 10 + a)
#print(dp)
print(dp[-1])

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

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

n,m = li()
a = list(li())

use = {}
for ai in a:
    if dic[ai] not in use.keys():
        use.update({dic[ai]: ai})
    else:
        use[dic[ai]] = max(use[dic[ai]], ai)
        
# 最大順
desc = {}
edge = {}
for idx, num in enumerate(sorted(use.values(), reverse=True)):
    desc.update({idx: num})
    edge.update({idx: dic[num]})
    
        
# 遷移
INF = float('inf')
dp = [[-INF]*len(use) for _ in range(n+1)]
dp[0] = [0]*len(use)
for i in range(1, n+1):
    cand = dp[i].copy()
    for idx in range(len(use)):
        if i - edge[idx] < 0:
            continue

        if sum(cand) < sum(dp[i-edge[idx]])+1:
            tmp = dp[i-edge[idx]].copy()
            tmp[idx] += 1
            cand = tmp.copy()
            

        elif sum(cand) == sum(dp[i-edge[idx]])+1:
            tmp = dp[i-edge[idx]].copy()
            tmp[idx] += 1
            
            for orgi, tmpi in zip(cand, tmp):
                if orgi == tmpi:
                    continue
                
                elif orgi > tmpi:
                    break
                
                else:
                    cand = tmp.copy()
                    break
                
    dp[i] = cand
                

ans = ""
for num, cnt in zip(desc.values(), dp[-1]):
    ans = ans + str(num)*cnt
    
print(ans)

Submission status: Accepted

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] 

D = {} #同じ本数で作れる数字は大きい方に統一
for i in range(M):
  n = num[A[i]]
  if D.get(n):
    D[n] = max(D[n], A[i])
  else:
    D[n] = A[i]

#桁数を最大にした中で最上位が最大のものが分かれば良い
DP = [(-1, -1)]*(N+1) #DP[i] = (桁数, 含まれる最大の数字)
DP[0] = (0, 0)
for i in range(N+1):
  for key in D:
    if i - key >= 0 and DP[i-key] != -1:
      temp = (DP[i-key][0] + 1, max(DP[i-key][1], D[key]))
      DP[i] = max(DP[i], temp)

#復元
ans = ''
now = N
while now > 0:
  ans += str(DP[now][1])
  now = now - num[DP[now][1]]
print(ans)

Submission status: Accepted

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] 
D = {}
for i in range(M):
  n = num[A[i]]
  if D.get(n):
    D[n] = max(D[n], A[i])
  else:
    D[n] = A[i]

DP = [(-1, -1)]*(N+1)
DP[0] = (0, 0)
for i in range(N+1):
  for key in D:
    if i - key >= 0 and DP[i-key] != -1:
      temp = (DP[i-key][0] + 1, max(DP[i-key][1], D[key]))
      DP[i] = max(DP[i], temp)

ans = ''
now = N
while now > 0:
  ans += str(DP[now][1])
  now = now - num[DP[now][1]]
print(ans)

Submission status: Accepted

Solution code:
n,m,*a=map(int,open(0).read().split())
d=[0]*n+[-1]*9
for i in range(n):d[i+1]=max(j+d[i-int('0144345265'[j])]*10for j in a)
print(d[n])

Submission status: Accepted

Solution code:
n,m,*a=map(int,open(0).read().split())
d=[0]+[-1]*n*9
for i in range(n):d[i+1]=max(j+d[i-int('0144345265'[j])]*10for j in a)
print(d[n])

Submission status: Accepted

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

can_use = [False for i in range(10)]
for a in A:
    can_use[a] = True

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

dp = [-1 for i in range(10 ** 4 + 1)]
dp[0] = 0

for i in range(N):
    if dp[i] < 0:
        continue
    for d in range(1, 10):
        if can_use[d] and i + match[d] <= N:
            dp[i + match[d]] = max(dp[i + match[d]], dp[i] * 10 + d)

print(dp[N])

Submission status: Accepted

Solution code:
n,m,*a=map(int,open(0).read().split());d=[0]*n+[-1]*9
for i in range(n):d[i+1]=max(d[i-int("0144345265"[j])]*10+j for j in a)
print(d[n])

Submission status: Accepted

Solution code:
n,m,*a=map(int,open(0).read().split())
d=[0]*n+[-1]*9
for i in range(n):d[i+1]=max(d[i-int("0144345265"[j])]*10+j for j in a)
print(d[n])

Submission status: Accepted

Solution code:
n,m,*a=map(int,open(0).read().split())
d=[0]*n+[-1]*9
for i in range(1,n+1):d[i]=max(d[i-int("0255456376"[j])]*10+j for j in a)
print(d[n])

Submission status: Accepted

Solution code:
n,m,*a=map(int,open(0).read().split())
d=[0]*n*9+[-1]*n*9
for i in range(1,n+1):d[i]=max(d[i-int("0255456376"[j])]*10+j for j in a)
print(d[n])

Submission status: Accepted

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

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

As.sort(reverse=True)

# dp[i+1][j]: As[i]まで使って、マッチ棒j本で作れる整数MAX
dp = [[-float('inf')]*(N+1) for _ in range(M+1)]
dp[0][0] = 0
for i, A in enumerate(As, 1):
    for j in range(N+1):
        dp[i][j] = dp[i-1][j]
        if j >= nums[A]:
            dp[i][j] = max(dp[i][j], dp[i-1][j-nums[A]]*10+A, dp[i][j-nums[A]]*10+A)

print(dp[-1][-1])

Submission status: Accepted

Solution code:
n,m,*a=map(int,open(0).read().split())
d=[0]*n*9
for i in range(n):
 for j in a:c=i+int("0255456376"[j]);d[c]=max(d[c],(d[i]*10+j)*(i<1or d[i]>0))###
print(d[n])

Submission status: Accepted

Solution code:
n,m,*a=map(int,open(0).read().split());d=[0]*n*9
for i in range(n):
 for j in a:
  if d[i]or i<1:c=i+int("0255456376"[j]);d[c]=max(d[c],d[i]*10+j)
print(d[n])

Submission status: Accepted

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

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

B = [0 for i in range(10)]
C = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
for i in range(10):
    if i in A:
        B[i] = C[i]

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

# print(dp)
                
ans = 0
for i in range(10):
    ans = max(ans, dp[0][i])

print(ans)

Submission status: Accepted

Solution code:
import time
n, m = map(int, input().split())
numbers = list(map(int, input().split()))
costs = [0,2,5,5,4,5,6,3,7,6]
f = [-1]*10010
f[0] = 0
for i in range(1, n+1):
    for x in numbers:
        if i-costs[x] >= 0:
            f[i] = max(f[i], f[i-costs[x]]*10+x)
print(f[n])

Submission status: Accepted

Solution code:
n,m,*a=map(int,open(0).read().split())
d=[0]*n*9
for i in range(n):
 for j in a:c=i+(0,2,5,5,4,5,6,3,7,6)[j];d[c]=max(d[c],(d[i]*10+j)*(i<1or d[i]>0))
print(d[n])

Submission status: Accepted

Solution code:
n,m,*a=map(int,open(0).read().split())
d=[0]*n*9
for i in range(n):
 for j in a:
  if d[i]or i<1:c=i+(0,2,5,5,4,5,6,3,7,6)[j];d[c]=max(d[c],d[i]*10+j)
print(d[n])

Submission status: Accepted

Solution code:
n,m,*a=map(int,open(0).read().split())
d=[0]*n*9
for i in range(n):
 for j in a:
  c=(0,2,5,5,4,5,6,3,7,6)[j]
  if d[i]or i<1:d[i+c]=max(d[i+c],d[i]*10+j)
print(d[n])

Submission status: Accepted

Solution code:
n,m,*a=map(int,open(0).read().split())
c=(0,2,5,5,4,5,6,3,7,6)
d=[0]*n*9
for i in range(n):
 for j in a:
  c=(0,2,5,5,4,5,6,3,7,6)[j]
  if d[i]or i<1:d[i+c]=max(d[i+c],d[i]*10+j)
print(d[n])

Submission status: Accepted

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

# n,m = [2, 9]
# a = [1, 2, 3, 4, 5, 6, 7, 8, 9]

a.sort()
table = {1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}

dp = ["" for i in range(max(n + 1, m+1))]
for x in a:
    dp[table[x]] = str(x)


def str_max(maxstrs):
    maxstrlen = max(map(lambda x:len(x), maxstrs))
    maxstr = max(filter(lambda x:len(x) == maxstrlen, maxstrs))
    return maxstr


for i in range(n + 1):
    for x in a:
        tmpstr = str(x)
        tmprest = i - table[x]
        if tmprest < 0:
            tmpstr = ""
        if 0 <= tmprest:
            # load dp
            tmp = dp[tmprest]
            if tmp == "":
                tmpstr = ""
            else:
                tmpstr = tmp + str(x)
        dp[i] = str_max([dp[i], tmpstr])

print(dp[n])

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
A=list(input().split())
c=[0,2,5,5,4,5,6,3,7,6]

dp=['']*(n+1)
dp[0]=''
for i in range(1,n+1):
    max=''
    for j in range(m):
        if (i-c[int(A[j])]>0 and dp[i-c[int(A[j])]]!='') or (i-c[int(A[j])]==0):
            if len(dp[i-c[int(A[j])]]+A[j])>len(max):
                max=dp[i-c[int(A[j])]]+A[j]
            elif len(dp[i-c[int(A[j])]]+A[j])==len(max) and dp[i-c[int(A[j])]]+A[j]>max:
                max=dp[i-c[int(A[j])]]+A[j]
    dp[i]=max
print(dp[n])

Submission status: Accepted

Solution code:
from pprint import pprint
def arr_scan():
    return list(map(int, input().split(' ')))

n, m = arr_scan()
# todo: improve description
# dp[n][letters]: represents the max
# length of letter achievable upto dp[i]: ith length strings  
dp = ['' for _ in range(n + 1)]
costs = [0,2,5,5,4,5,6,3,7,6]

# keep in mind the off-set of 1 because 
# available digits for forming the letters
# is from 1-9 i.e. 9 digits only

letters = arr_scan()

# row wise
for wt in range(1, n + 1):
    # do for all available digits
    for l in letters:
        # lookback
        if wt - costs[l] >= 1 and dp[wt - costs[l]] != '':
            if len(dp[wt - costs[l]]) + 1 > len(dp[wt]):
                dp[wt] = max(dp[wt - costs[l]] + str(l), str(l) + dp[wt - costs[l]])
            elif len(dp[wt- costs[l]]) + 1 == len(dp[wt]): 
                dp[wt] = max(dp[wt], dp[wt - costs[l]] + str(l), str(l) + dp[wt - costs[l]])
        elif wt == costs[l]:
            if len(dp[wt]) == 1:
                dp[wt] = max(dp[wt], str(l))
            elif dp[wt] == '':
                dp[wt] = str(l)
        # check with current cost of n and the letter
# pprint(dp)
print(dp[n])

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
needs = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [-1] * (n + 8)
dp[0] = 0
for a in sorted(map(int, input().split()), reverse=True):
    na = needs[a]
    for i in range(n + 1):
        if dp[i] == -1:
            continue
        dp[i + na] = max(dp[i + na], dp[i] * 10 + a)
print(dp[n])

Submission status: Accepted

Solution code:
from collections import defaultdict

n, m = map(int, input().split())
needs = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
usable = defaultdict(lambda: 0)
for a in map(int, input().split()):
    na = needs[a]
    usable[na] = max(usable[na], a)
use_keys = sorted(usable.keys())

dp = [-1] * (n + 8)
dp[0] = 0
for a in sorted(usable.values(), reverse=True):
    na = needs[a]
    for i in range(n + 1):
        if dp[i] == -1:
            continue
        dp[i + na] = max(dp[i + na], dp[i] * 10 + a)

print(dp[n])

Submission status: Accepted

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

def solve():
    N, M  = map(int, input().split())
    A = sorted(list(map(int, input().split())), reverse=1)
    I = [0,2,5,5,4,5,6,3,7,6]
    dp_a = [0 for _ in range(8)]
    for i in range(2, N+1):
        dp_a[i%8] = max((10*dp_a[j%8]+a for j,a in ((i-I[a], a) for a in A) if j >= 0 and (dp_a[j%8] != 0 or I[a] == i)), default=0)
    res = str(dp_a[i%8])
    return str(res)
if __name__ == '__main__':
    print(solve())

Submission status: Accepted

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

def f(x):
    """数xを作るために必要なマッチ棒の本数を返す関数

    :type x: str
    :param x: マッチ棒で作る数
    :rtype: int
    :return: xを作るために必要なマッチ棒の本数
    """

    num_base = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
    ret = 0
    for i in range(len(x)):
        ret += num_base[int(x[i])]

    return ret


def max_num(x, y):
    """xとyの大きいほうを返す関数。
    1.文字列の長さが長い方が大きい
    2.文字列の長さが等しいとき、文字列として比較して大きい方が大きい

    :type x: str
    :param x: マッチ棒で作る数
    :type y: str
    :param y: マッチ棒で作る数
    :rtype: str
    :return: 大きい方の数
    """

    if len(x) > len(y):
        return x
    elif len(y) > len(x):
        return y
    else:
        if x > y:
            return x
        else:
            return y


dp = [""] * (n + 1)
for j in range(2, n + 1):
    for i in range(m):
        match = f(str(a[i]))

        if j == match:
            dp[j] = max_num(dp[j], dp[j - match] + str(a[i]))
            dp[j] = max_num(dp[j], str(a[i]) + dp[j - match])

        elif j > match:
            if dp[j - match] != "":
                dp[j] = max_num(dp[j], dp[j - match] + str(a[i]))
                dp[j] = max_num(dp[j], str(a[i]) + dp[j - match])

print(dp[n])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
import copy
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, M, A):
    c = [
        -1,
        2, # 1 
        5, # 2
        5, # 3
        4, # 4
        5, # 5
        6, # 6
        3, # 7
        7, # 8
        6, # 9
        ]
    
    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)
    if 6 in A and 9 in A:
        A.remove(6)



    dp = [None] * (N+1) 
    dp[N] = 0
    for i in range(N, 0, -1):
        if dp[i] is None:
            continue
        
        for a in A:
            if i - c[a] < 0:
                continue
            
            if dp[i-c[a]] is None or dp[i] * 10 + a > dp[i-c[a]]:
                dp[i-c[a]] =  dp[i] * 10 + a

    return dp[0]


def main():
    # N = read_int()
    N, M = read_int_n()
    A = read_int_n()
    print(slv(N, M, A))


if __name__ == '__main__':
    main()