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:
#!/usr/bin/env python3
import sys

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

def sort_str(s):
    ret = list(s)
    ret.sort(reverse=True)
    return ''.join(ret)

def is_greater(a, b):
    if len(a) > len(b):
        return True
    elif len(a) < len(b):
        return False
    for i in range(len(a)):
        if a[i] > b[i]:
            return True
        else:
            return False
    return False

def _solve(n: int, m: int, A: "List[int]"):
    dp = [None] * (n + 1)
    dp[0] = ''
    for c in A:
        for i in range(n + 1):
            if i - a[c] >= 0 and dp[i - a[c]] is not None:
                tmp = sort_str(dp[i - a[c]] + str(c))
                if dp[i] is None or is_greater(tmp, dp[i]):
                    dp[i] = tmp
        #print(dp)
    print(dp[n])
    return

def solve(n: int, m: int, A: "List[int]"):
    dp = [-1] * (n + 1)
    memo = ['' for _ in range(n + 1)]
    dp[0] = 0
    A.sort(reverse=True)
    #A.sort()
    for c in A:
        for i in range(n + 1):
            if i - a[c] >= 0 and dp[i - a[c]] >= 0:
                dp[i] = max(dp[i], dp[i - a[c]] * 10 + c)
                #if dp[i] < dp[i - a[c]] + 1:
                #    dp[i] = dp[i - a[c]] + 1
                #    memo[i] = memo[i - a[c]] + str(c)
        #print(dp)
        #print(memo)
    print(dp[n])
    #ret = list(memo[n])
    #ret.sort(reverse=True)
    #ret = ''.join(ret)
    #print(ret)
    return



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:
from collections import defaultdict
N,M = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
cost = [0,2,5,5,4,5,6,3,7,6]
dp = defaultdict(lambda:'')
for a in A:
    dp[cost[a]] = str(a)
for i in range(N+1):
    for a in A:
        if dp[i-cost[a]] != '':
            if len(dp[i]) <= len(dp[i-cost[a]]+str(a)):
                dp[i] = dp[i-cost[a]]+str(a)
        ans = dp[N]
ans = list(map(int,list(ans)))
ans.sort(reverse=True)
print(''.join(list(map(str,ans))))

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    a,b = LI()
    if b%a == 0:
        print(a+b)
    else:
        print(b-a)
    return

#B
def B():
    n,m = LI()
    d = defaultdict(int)
    for i in range(n):
        l = LI()
        for j in range(1,len(l)):
            d[l[j]] += 1
    ans = 0
    for i in d.values():
        if i == n:
            ans += 1
    print(ans)
    return

#C
def C():
    def gcd(a,b):
        if a == 0:
            return b
        return gcd(b%a,a)
    n = I()
    a = LI()
    g = a[0]
    for i in range(1,n):
        g = gcd(g,a[i])
    print(g)
    return

#D
def D():
    n,m = LI()
    a = LI()
    f = [0,2,5,5,4,5,6,3,7,6]
    dp = [None for i in range(n+1)]
    dp[0] = []
    for j in a:
        for i in range(n+1):
            if i-f[j] >= 0 and dp[i-f[j]] != None:
                if dp[i] == None:
                    dp[i] = dp[i-f[j]]+[j]
                    dp[i].sort(reverse = True)
                elif len(dp[i]) < len(dp[i-f[j]])+1:
                    dp[i] = dp[i-f[j]]+[j]
                    dp[i].sort(reverse = True)
                elif len(dp[i]) == len(dp[i-f[j]])+1:
                    d = dp[i-f[j]]+[j]
                    d.sort(reverse = True)
                    if dp[i] < d:
                        dp[i] = d
    ans = 0
    k = pow(10,len(dp[n])-1)
    for i in range(len(dp[n])):
        ans += k*dp[n][i]
        k //= 10
    print(ans)
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    D()

Submission status: Accepted

Solution code:
# coding:utf-8

import sys
INF = float('inf')
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


def main():
    n, m = LI()
    A = LI()

    match = [6, 2, 5, 5, 4, 5, 6, 3, 7, 6]
    # dp[i]: ちょうどマッチをi本使ったときに作れる整数の最大の値
    dp = [-INF] * (n + 10)
    dp[0] = 0
    for i in range(n):
        for a in A:
            j = i + match[a]
            dp[j] = max(dp[j], dp[i] * 10 + a)

    return dp[n]


print(main())

Submission status: Accepted

Solution code:
# coding:utf-8

import sys
import math
INF = float('inf')
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


def main():
    n, m = LI()
    A = LI()
    A.sort()
    A.reverse()

    match = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
    # dp[i]: ちょうどマッチをi本使ったときに作れる整数の最大の桁数（-1: 作れない）
    dp = [-1] * (n + 1)
    dp[0] = 0
    res = [0] * (n + 1)
    for i in range(1, n + 1):
        for j in A:
            # 最上位桁の数字を決める
            # k: 最上位桁をjにしたときの残りのマッチの数
            k = i - match[j]
            if k < 0 or dp[k] == -1:
                continue

            if dp[i] < dp[k] + 1:
                dp[i] = dp[k] + 1
                res[i] = j * 10 ** dp[k] + res[k]

    return res[n]


print(main())

Submission status: Accepted

Solution code:
# coding:utf-8

import sys
import math
INF = float('inf')
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


def main():
    n, m = LI()
    A = LI()
    A.sort()
    A.reverse()

    match = [2, 5, 5, 4, 5, 6, 3, 7, 6]
    # dp[i]: ちょうどマッチをi本使ったときに作れる整数の最大の桁数（-1: 作れない）
    dp = [-1] * (n + 1)
    dp[0] = 0
    res = [0] * (n + 1)
    for i in range(1, n + 1):
        for j in A:
            # 最上位桁の数字を決める
            # k: 最上位桁をjにしたときの残りのマッチの数
            k = i - match[j - 1]
            if k < 0 or dp[k] == -1:
                continue

            if dp[i] < dp[k] + 1:
                dp[i] = dp[k] + 1
                res[i] = max(j * 10 ** dp[k] + res[k], res[k] * 10 + j)

    return res[n]


print(main())

Submission status: Accepted

Solution code:
#encoding: utf-8

N, M = map(int, input().split())
A = list(map(int, input().split()))
match = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]

A.sort()
A.reverse()

dp = [-1] * (N + 1)
dp[0] = 0

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

print(dp[N])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
a.reverse()
dp=[0]*(n+1)
ans=[0]*(n+1)
num=[0,2,5,5,4,5,6,3,7,6]
INF=10**18
for i in range(1,n+1):
  stack=[]
  chance=[]
  for j in a:
    if i-num[j]>=0:
      stack.append(dp[i-num[j]])
      chance.append([dp[i-num[j]],ans[i-num[j]]])
    else:
      stack.append(-INF)
      chance.append([-1,-1])
  dp[i]=max(stack)+1
  if dp[i]>0:
    for v in range(len(stack)):
      if stack[v]==max(stack):
        ans[i] += chance[v][1]+a[v]*10**(dp[i]-1)
        break
print(ans[n])

Submission status: Accepted

Solution code:
# coding: utf-8

def main():
    N, M = map(int, input().split())
    A = sorted(list(map(int, input().split())))[::-1]
    bar_num = [2,5,5,4,5,6,3,7,6]
       
    dp = [-1] * (N+5) ## restore dp result
    dp[0] = 0
    for i in range(N+1):
        for a in A:
            if i - bar_num[a-1] >= 0:
                dp[i] = max(dp[i], dp[i-bar_num[a-1]]*10+a)
    print(dp[N])
    
if __name__ =='__main__':
    main()

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
read_int = lambda : list(map(int,stdin.readline().split()))

N,M = read_int()

A = read_int()
# for index arrangement
A.sort(reverse=True)
A.insert(0,-1)

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

dp = [-1 for j in range(N+1)]
def solve():
    dp[0] = 0
    for i in range(M):
        for j in range(N+1):
            if j - W[A[i + 1]] >= 0 and dp[j - W[A[i + 1]]] >= 0:
                dp[j] = max(dp[j], dp[j - W[A[i + 1]]]*10 + A[i + 1])
                
if __name__ == "__main__":
    solve()
    print(dp[N])

Submission status: Accepted

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

N,M = read_int()

A = read_int()
# for index arrangement
A.sort(reverse=True)
A.insert(0,-1)

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

dp = [-1 for j in range(N+1)]
def solve():
    dp[0] = 0
    for i in range(M):
        digit = [0 for _ in range(N+1)]
        for j in range(N+1):
            if j - W[A[i + 1]] >= 0 and dp[j - W[A[i + 1]]] >= 0:
                dp[j] = max(dp[j], dp[j - W[A[i + 1]]]*10 + A[i + 1])
                
if __name__ == "__main__":
    solve()
    print(dp[N])

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
p=[-1]*(n+1)
a=list(map(int,input().split()))
e=[2,5,5,4,5,6,3,7,6]
p[0]=0
for i in range(n+1):
    for j in a:
        if i-e[j-1]>=0:
            p[i]=max(p[i],p[i-e[j-1]]*10+j)
print(p[-1])

Submission status: Accepted

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

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

dp = [-1] * (N+1)
dp[0] = 0
for i in range(1, N+1):
    max_scale = -1
    for num in useful_num_list:
        if need_matches[num] <= i:
            scale = dp[i-need_matches[num]] + 1
            if max_scale < scale:
                max_scale = scale
    dp[i] = max_scale

useful_num_list.sort(reverse=True)
ans = 0
n = N
while n > 0:
    for num in useful_num_list:
        if n < need_matches[num]:
            continue
        if dp[n] - 1 == dp[n - need_matches[num]]:
            ans += num * (10**(dp[n]-1))
            n -= need_matches[num]
            break
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
a=list(map(int,input().split()))
ma=[0,2,5,5,4,5,6,3,7,6]
a=sorted(a)
dp=[-1]*(n+1)
dp[0]=0
for i in range(m-1,-1,-1):
    for j in range(n+1):
        if dp[j]!=-1 and j+ma[a[i]]<=n:
            dp[j+ma[a[i]]]=max(10*dp[j]+a[i],dp[j+ma[a[i]]])
print(dp[n])

Submission status: Accepted

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

dp = [-1 for _ in range(N+1)]
dp[0] = 0
for i in range(N+1):
    for a in A:
        if i-match[a]>=0:
            dp[i] = max(dp[i],dp[i-match[a]]*10+a)

print(dp[-1])

Submission status: Accepted

Solution code:
n, m=map(int, input().split())
a=list(map(int, input().split()))
d={1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6}
memo=[0]*(n+1)
memo[0]=0
memo[1]=-10**10
for i in range(2, n+1):
    res=-10**10
    for ai in a:
        if d[ai]>i:
            continue
        res=max(res, ai+memo[i-d[ai]]*10)
    memo[i]=res
print(memo[n])

Submission status: Accepted

Solution code:
import sys
from functools import lru_cache


sys.setrecursionlimit(200000)
fin = sys.stdin.readline
num_matches_required = {n: nmatches for n, nmatches 
    in zip(range(1, 10), (2, 5, 5, 4, 5, 6, 3, 7, 6))}

N, M = map(int, fin().split())
nums = sorted(map(int, fin().split()), reverse=True)

@lru_cache(None)
def rec(i):
    if i < 0: 
        return float('-inf')
    elif i == 0: 
        return 0
    else:
        return max(
            rec(i - num_matches_required[num]) for num in nums
        ) + 1


num_digits = rec(N)
cur_num_matches = N
result = []
while cur_num_matches:
    for num in nums:
        if rec(cur_num_matches - num_matches_required[num]) == num_digits - len(result) - 1:
            result.append(str(num))
            cur_num_matches -= num_matches_required[num]
            break

print("".join(result))

Submission status: Accepted

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

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

def solve(n, m, a):

    a.sort(reverse = True)

    tmp = a.copy()
    for i in range(len(a) - 1, 0, -1):
        for j in range(i - 1, -1, -1):
            if W[a[i]] == W[a[j]]:
                a.pop(i)
                break

    by_value = [(v, W[v]) for v in a]
    by_weight = sorted(by_value, key = lambda x: x[1])
    v_to_w = {}
    w_to_v = {}
    for i, x in enumerate(by_value):
        for j, y in enumerate(by_weight):
            if x == y:
                v_to_w[i] = j
                w_to_v[j] = i
                break


    a_len = len(a)
    if a_len == 1:
        v, w = by_weight[0]
        return str(v) * (n // w)


    cnd = []
    w0 = by_weight[0][1]
    p = [0] * (a_len + 1)
    while p[-1] == 0:
        x = 0
        for i in range(1, a_len):
            x += p[i] * by_weight[i][1]
        if x <= n and (n - x) % w0 == 0:
            p[0] = (n - x) // w0
            cnd.append((sum(p), tuple([p[v_to_w[j]] for j in range(a_len)])))
        p[1] += 1
        for i in range(1, a_len):
            if p[i] == w0:
                p[i] = 0
                p[i + 1] += 1

    cnd.sort(key = lambda x: x[0], reverse = True)
    digits, _ = cnd[0]
    for i in range(1, len(cnd)):
        d, _ = cnd[i]
        if d < digits:
            cnd = cnd[:i]
            break

    cnd.sort(key = lambda x: x[1], reverse = True)

    ans = ''
    _, t = cnd[0]
    for i, x in enumerate(by_value):
        v, _ = x
        cnt = t[i]
        ans += str(v) * cnt

    return ans


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


    print(solve(n, m, a))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, M = map(int, raw_input().split())
A = map(int, raw_input().split())
all_cost = [-10**15, 2, 5, 5, 4, 5, 6, 3, 7, 6]

dp = [-10**15] * (N+1)

dp[0] = 0
for i in range(1, N+1, 1):
    max_val = -10**15
    for a in A:
        if i - all_cost[a] >= 0 and dp[i - all_cost[a]] != -10**15:
            val = dp[i - all_cost[a]] + 1
            if val > max_val: max_val = val
    dp[i] = max_val

A.sort(reverse=True)

result = ''
idx = N
while idx > 0:
    for a in A:
        if idx - all_cost[a] < 0: continue
        if dp[idx - all_cost[a]] == dp[idx] - 1:
            result += str(a)
            idx -= all_cost[a]
            break

print result

Submission status: Accepted

Solution code:
import sys
from functools import lru_cache
sys.setrecursionlimit(2*10**5)

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

INF = 10**15
# 各数字の消費マッチ棒
C = (100, 2, 5, 5, 4, 5, 6, 3, 7, 6)


# N=nのときの解に対応するベクトルを返す
@lru_cache(maxsize=None)
def dfs(n):
    return (
        [-INF for _ in range(9)] if n < 0 else
        [0 for _ in range(9)] if n == 0 else
        max(
            (
                [
                    t + 1 if i == a else t
                    for i, t in enumerate(dfs(n - C[a]), start=1)
                ]
                for a in A
            ),
            key=lambda x: [sum(x)] + list(reversed(x))
        )
    )


# 出力
ans = ''.join(str(a) * dfs(N)[a - 1] for a in sorted(A, reverse=True))
print(ans)

Submission status: Accepted

Solution code:
nn=[2,5,5,4,5,6,3,7,6]
n,m=map(int,input().split())
a=input().split()
b=[]
for i in range(m):
  a[i]=int(a[i])
  
if 5 in a:
  if 2 in a:
    a.remove(2)
  if 3 in a:
    a.remove(3)
elif 3 in a:
  if 2 in a:
    a.remove(2)
if 9 in a:
  if 6 in a:
    a.remove(6)
    
a.sort(reverse=True)
for i in range(len(a)):
  b.append(nn[a[i]-1])
  
dp=[-10*18 for _ in range(n+1)]
dp[0]=0
for i in range(n):
  for j in range(len(b)):
    if i+b[j]>n:
      continue
    dp[i+b[j]]=max(dp[i+b[j]],dp[i]+1)
    
k=dp[n]
ans=""
for i in range(k):
  for j in range(len(b)):
    if n-b[j]<0:
      continue
    if dp[n-b[j]]==dp[n]-1:
      ans+=str(a[j])
      n-=b[j]
      break
      
print(ans)

Submission status: Accepted

Solution code:
INF = 10 ** 6

def num(k):#各数字に使用するマッチ棒の本数を返す関数
    if k == 1:
        return 2
    elif k == 7:
        return 3
    elif k == 4:
        return 4
    elif k == 2 or k == 3 or k == 5:
        return 5
    elif k == 6 or k == 9:
        return 6
    elif k == 8:
        return 7

n, m = map(int,input().split())
l = list(map(int,input().split()))
l.sort(reverse = True)
         
dp = [(-1) * INF] * (n+1)

dp[0] = 0

for i in range(2,n+1):
    can = []
    for x in l:
        if i-num(x)>=0:
            can.append(dp[i-num(x)]+1)
    if can == []:
        dp[i] = (-1) * INF
    else:
        dp[i] = max(can)
        
#print(dp)

anslist = [0] * dp[n]

left = n

for j in range(dp[n],0,-1):#jは桁数
    if j == 1:
        for x in l:
            if num(x) == left:
                anslist[j-1] = x
                break
    else:
        for x in l:
            if dp[left-num(x)] == j - 1:
                anslist[j-1] = x#j桁目は10^(j-1)の位
                left = left-num(x)
                break
            
    #print([j,x,left])
#print(anslist)
            
            
ans = 0

for j in range(0,dp[n]):
    ans = ans + anslist[j] * (10 ** j)

print(ans)

Submission status: Accepted

Solution code:
n,m = (int(i) for i in input().split())
a = [int(i) for i in input().split()]
x,y,inf = [2,5,5,4,5,6,3,7,6],set(),float("inf")
dp,ans = [0,-inf],[]
def f(i,y):
    num = -inf
    for j in y:
        if i>=j: num = max(num,dp[i-j]+1)
    return num 
for i in a: y.add(x[i-1])
for i in range(2,n+1): dp.append(f(i,y))
a,N = sorted(a)[::-1],n
for i in range(dp[n]):
    for j in a:
        if N>=x[j-1] and dp[N-x[j-1]]==dp[N]-1:
            ans.append(str(j))
            N-=x[j-1]
            break
print("".join(ans))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
alist = list(sorted(map(int, input().split())))[::-1]
md = {1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6}

dp = [-float('inf') for _ in range(n+1)]
dp[0] = 0

for i in range(n+1):
  for a in alist:
    if i - md[a] >= 0:
      if dp[i] < dp[i - md[a]] + 1:
        dp[i] = dp[i - md[a]] + 1

ans = ''
res = n
while i > 0:
  for a in alist:
    if i >= md[a] and dp[i]-1 == dp[i-md[a]]:
      ans += str(a)
      i -= md[a]
      break

print(ans)

Submission status: Accepted

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
N, M = map(int, input().split())
A = list(map(int, input().split()))
A = sorted(A, reverse=True)

nums = {}
nums[1] = 2
nums[2] = 5
nums[3] = 5
nums[4] = 4
nums[5] = 5
nums[6] = 6
nums[7] = 3
nums[8] = 7
nums[9] = 6

dp = [-float('inf')]*(N+1)
dp[0] = 0

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

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

Submission status: Accepted

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

cost = sorted(list(zip([[2, 5, 5, 4, 5, 6, 3, 7, 6][a-1] for a in A], A)), key=lambda x: (x[0], -x[1]))

# 同じ画数の数字を除く
tmp = len(cost)
i = 1
while i < tmp:
    if cost[i][0] == cost[i-1][0]:
        cost.pop(i)
        tmp = len(cost)
    else:
        i += 1
cost.sort(key=lambda x:-x[1])

# Dynamic Programming
dp = [0] + [-10] * (N)  # dp[n]: n本までマッチ棒を使った場合の最大桁数
for i in range(2, N+1):
    dp[i] = max([-10] + [dp[i-c]+1 for c, _ in cost if i >= c])

n = N
out = ""
i = 0
while n:
    c, a = cost[i]
    if (n >= c) and (dp[n-c] == dp[n] - 1):
        n -= c
        out += str(a)
    else:
        i += 1
print(out)

Submission status: Accepted

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

cost = sorted(list(zip([[2,5,5,4,5,6,3,7,6][a-1] for a in A],A)),key = lambda x: (x[0],-x[1]))

#同じ画数の数字を除く
tmp = len(cost)
i = 1
while i < tmp:
    if cost[i][0] == cost[i-1][0]:
        cost.pop(i)
        tmp = len(cost)
    else:
        i += 1
cost.sort(key = lambda x:-x[1])

dp = [0]+[-10]*(N)
for i in range(2,N+1):
    dp[i] = max([-10]+[dp[i-a]+1 for a,_ in cost if i >= a])

n = N
out = ""
i = 0
while n:
    c , a = cost[i]
    if (n>=c) and (dp[n-c] == dp[n]-1):
        n -= c
        out += str(a)
    else:
        i+=1
print(out)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
A=list(map(int,input().split()))
match=[0,2,5,5,4,5,6,3,7,6]
make=dict()
for a in A:
    make[a]=match[a]
dp=[-1]*(N+1)
dp[0]=0
for k in range(1,1+N):
    for d,m in make.items():
        if k-m<0 or dp[k-m]==-1:continue
        dp[k]=max(dp[k],dp[k-m]+1)
        
ans=''
now=N
for k in range(dp[N]):
    res=(0,0)
    for d,m in make.items():
        if now-m<0:continue
        if dp[now-m]+1==dp[now] and res[0]<d:
            res=(d,m)
    ans+=str(res[0])
    now-=res[1]
print(int(ans))

Submission status: Accepted

Solution code:
match, _ = [int(item) for item in input().split()]
kind = sorted([int(item) for item in input().split()])

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

dp = [-1] * int(match + 1)

dp[0] = 0
for i in range (match + 1):
  for k in kind:
    if i < use[k]:
      continue
    dp[i] = max(dp[i], dp[i - use[k]] * 10 + k)
    
print(dp[match])

Submission status: Accepted

Solution code:
inf = 1 << 60
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] = i本でできる最大の数
dp = [-inf for i in range(N+1)]
dp[0] = 0
for i in range(N+1):
    for a in A:
        if i < use[a]:
            continue
        dp[i] = max(dp[i], dp[i-use[a]] * 10 + a)
print(dp[N])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(15000)

n, m = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]

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

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

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

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

i = dp(1)
a.sort()

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

print(int(s))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
numbers = list(map(int, input().split()))
cost = [2, 5, 5, 4, 5, 6, 3, 7, 6]

dp = [None] * (N + 10)
dp[0] = ""
for i in range(N):
    if dp[i] == None:
        continue
    for k in numbers:
        idx = i + cost[k - 1]
        s1 = dp[i] + str(k)
        s2 = dp[idx]

        if s2 == None or len(s1) > len(s2):
            dp[idx] = s1
        elif len(s1) == len(s2) and s1 > s2:
            dp[idx] = s1
print(dp[N])

Submission status: Accepted

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

dp = ["-" for n in range(10010)]

def compare_str(a, b):
    if a == "":
        return b
    elif len(a) == len(b):
        return a if a > b else b
    elif len(a) > len(b):
        return a
    return b
    
dp[0] = ""
for i in range(length + 1):
    if dp[i] != "-":
        for m in match:
            dp[i + cost[m]] = compare_str(dp[i + cost[m]], dp[i] + m)
print(dp[length])

Submission status: Accepted

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

dp = ["-" for n in range(10010)]

def compare_str(a, b):
    if a == "":
        return b
    elif len(a) == len(b):
        return a if a > b else b
    elif len(a) > len(b):
        return a
    return b
    
# for m in match:
#     dp[cost[m]] = m
dp[0] = ""
for i in range(length + 1):
    # print(dp, i)
    if dp[i] != "-":
        for m in match:
            # if i + cost[m] <= length:
            dp[i + cost[m]] = compare_str(dp[i + cost[m]], dp[i] + m)
print(dp[length])

Submission status: Accepted

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

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

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

print(int(ans))

Submission status: Accepted

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

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

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

print(int(ans[1:]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
INF = float('inf')
n, m = map(int, input().split())
a = list(map(int, input().split()))
cost = [2, 5, 5, 4, 5, 6, 3, 7, 6]
l = [[x, cost[x-1]] for x in a]
l = sorted(l, key = lambda x: x[1]*10-x[0])
r = l[0]
k = max(n-200, 0)//r[1]
n -= r[1]*k
_max = [0] + [-INF]*n
for i in range(1, n+1):
  if 50 < i < n-50:
    _max[i] = max(_max[i], _max[i-r[1]]*10 + r[0])
  else:
    for x in l:
      ind = i-x[1]
      if ind >= 0:
        _max[i] = max(_max[i], _max[ind]*10 + x[0])
ans = str(_max[n])
ans = ans[:10] + str(r[0])*k + ans[10:]
print(ans)

Submission status: Accepted

Solution code:
INF = float('inf')
n, m = map(int, input().split())
a = list(map(int, input().split()))
cost = [2, 5, 5, 4, 5, 6, 3, 7, 6]
l = [[x, cost[x-1]] for x in a]
l = sorted(l, key = lambda x: x[1]*10-x[0])
r = l[0]
_max = [0] + [-INF]*n
for i in range(1, n+1):
  if 42 < i < n-42:
    _max[i] = max(_max[i], _max[i-r[1]]*10 + r[0])
  else:
    for x in l:
      ind = i-x[1]
      if ind >= 0:
        _max[i] = max(_max[i], _max[ind]*10 + x[0])
ans = str(_max[n])
print(ans)

Submission status: Accepted

Solution code:
INF = float('inf')
n, m = map(int, input().split())
a = list(map(int, input().split()))
cost = [2, 5, 5, 4, 5, 6, 3, 7, 6]
l = [[x, cost[x-1]] for x in a]
l = sorted(l, key = lambda x: x[1]*10-x[0])
r = l[0]
_max = [0] + [-INF]*n
for i in range(1, n+1):
  for x in l:
    ind = i-x[1]
    if ind >= 0:
      _max[i] = max(_max[i], _max[ind]*10 + x[0])
ans = str(_max[n])
print(ans)

Submission status: Accepted

Solution code:
__MATCH = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6, ]
__INF = float('inf')


def match_matching(N: int, M: int, A: list) -> int:
    # dp で最大桁数を求める
    dp = [-__INF] * (N+1)
    dp[0] = 0
    for i in range(1, N+1):
        dp[i] = max([-__INF] +
                    [dp[i - __MATCH[a]] for a in A if i >= __MATCH[a]]) + 1

    # 各桁の数字を決める
    _A = sorted(A, reverse=True)
    used_matches = 0
    ans = 0
    for n in range(dp[N], 0, -1):
        for a in _A:
            used_matches += __MATCH[a]
            if used_matches <= N and dp[N-used_matches] == n - 1:
                ans = ans * 10 + a
                break
            used_matches -= __MATCH[a]

    return ans


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

    ans = match_matching(N, M, A)

    print(ans)