Problem:


Score : 400 points

Problem Statement

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

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

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

Constraints

All values in input are integers.

2 \leq N \leq 10^4

1 \leq M \leq 9

1 \leq A_i \leq 9

A_i are all different.

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

Input

Input is given from Standard Input in the following format:

N M
A_1 A_2 ... A_M

Output

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

Sample Input 1

20 4
3 7 8 4

Sample Output 1

777773

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

Sample Input 2

101 9
9 8 7 6 5 4 3 2 1

Sample Output 2

71111111111111111111111111111111111111111111111111

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

Sample Input 3

15 3
5 4 6

Sample Output 3

654



Sample input:
20 4
3 7 8 4


Sample output:
777773

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
a = list(map(int,input().split()))
b = [0,2,5,5,4,5,6,3,7,6]
ab = {}
for i in a:
    ab[i] = b[i]
dp = [0]*(n+10)
dp[0] = ""
for i in range(n+1):
    if dp[i] == 0:
        continue
    for j in ab.keys():
        try:
            dp[i+ab[j]] = str(max(int(dp[i+ab[j]]),int(dp[i]+str(j)),int(str(j)+dp[i])))
        except:
            dp[i+ab[j]] = str(max(int(dp[i+ab[j]]),j))
print(dp[n])

Submission status: Time Limit Exceeded

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

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

A.sort(reverse=1)
CS = [None,2,5,5,4,5,6,3,7,6]

memo = {}
def dfs(rest, i):
    key = (rest, i)
    if key in memo:
        return memo[key]
    if i == M:
        return [] if rest == 0 else None
    v = A[i]; c = CS[v]
    r = None
    k = 0
    while k*c <= rest:
        r0 = dfs(rest-k*c, i+1)
        if r0 is not None:
            r0 = [k] + r0
            if r is None or (sum(r) < sum(r0) or (sum(r) == sum(r0) and r < r0)):
                r = r0
        k += 1
    memo[key] = r
    return r
res = dfs(N, 0)
ans = []
for i in range(M):
    ans.append(str(A[i]) * res[i])
print(*ans, sep='')

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
a = list(map(int, input().split()))
l = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [-1] * (n+1)
dp[0] =  0

for i in range(n+1):
    for j in a:
        if i + l[j] < n+1:
            dp[i + l[j]] = max(dp[i + l[j]], dp[i]*10 + j)
print(dp[-1])

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
l=list(map(int,input().split()))
w=[2,5,5,4,5,6,3,7,6]
l.sort()
dp=[0]*(max(N+1,8))
for j in l:
   dp[w[j-1]]=j
for i in range(N):
   if dp[i]!=0:
      for j in l:
         if w[j-1]+i<=N:
            dp[i+w[j-1]]=max(dp[i+w[j-1]],dp[i]*10+j)
print(dp[N])

Submission status: Accepted

Solution code:
def main():
    n, m = map(int, input().split())
    a = set(map(int, input().split()))

    # type(x) == type(y) == string
    def bigger(x, y):
        if len(x) > len(y):
            return x
        elif len(x) < len(y):
            return y
        elif x < y:
            return y
        else:
            return x

    l = []
    if 1 in a:
        l.append((2, '1'))

    if 7 in a:
        l.append((3, '7'))

    if 4 in a:
        l.append((4, '4'))

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

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

    if 8 in a:
        l.append((7, '8'))

    dp = [None] * (n+1)
    dp[0] = ''
    for i in range(1, n+1):
        for cost, char in l:
            if i - cost < 0 or dp[i-cost] is None:
                continue
            candidate = max(dp[i-cost] + char, char + dp[i-cost])
            if dp[i] is None:
                dp[i] = candidate
            else:
                dp[i] = bigger(dp[i], candidate)

    print(dp[n])

main()

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
a = list(map(int, input().split()))
dp = [-1] * (n * 18)
for i in range(n * 9):
    dp[i] = 0
lis = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
for i in range(n):
    cnt = -float("inf")
    for j in a:
        cnt = max(cnt, dp[i + 1 - lis[j]] * 10 + j)
    dp[i + 1] = cnt
print(dp[n])

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

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

N, M = map(int, input().split())
A = list(map(int, input().split()))
Need = [-1, 2, 5, 5, 4, 5, 6, 3, 7, 6]
Usable = {}
for a in A:
    if Need[a] in Usable:
        for key, value in Usable.items():
            if Need[a] == key and a > value:
                Usable[key] = a
    else:
        Usable[Need[a]] = a
Num = [-1] * (N + 1)
Num[0] = 0
for i in range(1, N+1):
    for u, v in Usable.items():
        if i < u:
            continue
        if Num[i - u] >= 0:
            if Num[i - u] == 0:
                Num[i] = max(v, Num[i])
            elif Num[i] < Num[i - u] * 10 + v:
                Num[i] = Num[i - u] * 10 + v

print(Num[N])

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
#from functools import reduce
import copy

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

dic = {}
def dic_add(dic, key, val):
  if key in dic:
    dic[key] += adic
def dic_pop(dic, key):
  if key in dic:
    dic.pop(key)
  
for a in A:
  dic[cost[a]] = a
if 2 in dic:
  dic_pop(dic,4)
  dic_pop(dic,6)
  if 3 in dic:
    dic_pop(dic,5)
    dic_pop(dic,7)
  elif 5 in dic:
    dic_pop(dic,7)
elif 3 in dic:
  dic_pop(dic,6)
  if 4 in dic:
    dic_pop(dic,7)

dic_inv = [0 for _ in range(10)]
A = []
for c in dic:
  dic_inv[dic[c]] = c 
  A.append(dic[c])
A.sort(reverse = True)
label = [-1 for _ in range(10)]
for i in range(len(A)):
  label[A[i]] = i
  
def larger(a_lis, b_lis): # a > b の判定
  if sum(a_lis) > sum(b_lis):
    del b_lis
    return a_lis
  elif sum(a_lis) < sum(b_lis):
    del a_lis
    return b_lis
  else:
    if a_lis > b_lis:
      del b_lis
      return a_lis
    else:
      del a_lis
      return b_lis
INF = 10**20
DP = [[-INF for a in A] for _ in range(N+1)]
DP[0] = [0 for a in A]
for n in range(2,N+1):
  for a in A:
    if n - cost[a] >= 0:
      tmp = copy.copy(DP[n - cost[a]])
      tmp[label[a]] += 1
      DP[n] = larger(DP[n], tmp)
      
ans = 0
for a in A:
  num_a = DP[N][label[a]] 
  for i in range(num_a):
    ans *= 10
    ans += a 
    
print(ans)
"""
print(A)
print(label)
print(*DP, sep = "\n")
"""

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
A = list(map(int,input().split()))
C = [0,1,4,4,3,4,5,2,6,5]
dp = N*[0]+9*[-1]

for n in range(N):
  dp[n+1] = max(a+10*dp[n-C[a]] for a in A)

print(dp[N])

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, m = map(int, input().split())
    A = list(map(int, input().split()))

    L = [(1, 2), (2, 5), (3, 5), (4, 4), (5, 5), (6, 6), (7, 3), (8, 7), (9, 6)]
    B = []
    for num, cost in L:
        if num in A:
            B.append([num, cost])
    B.sort(key=lambda x: -x[0])
    dp = [-f_inf] * (n + 1)
    dp[0] = 0
    for i in range(n + 1):
        for _, cost in B:
            if i - cost == 0:
                dp[i] = max(dp[i], dp[0] + 1)
            elif i - cost > 0 and dp[i - cost] != 0:
                dp[i] = max(dp[i], dp[i - cost] + 1)
    j = 0
    k = n
    res = ""
    while k > 0 and j < m:
        num, cost = B[j]
        if k - cost >= 0 and dp[k] - dp[k - cost] == 1:
            res += str(num)
            k -= cost
        else:
            j += 1
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
import itertools
import heapq as hq
cnt = [-1,2,5,5,4,5,6,3,7,6]
n,m = ma()
A = lma()
use=[(cnt[a],a) for a in A]
use.sort(key=lambda x:x[1],reverse=True)
INF=10**9
dp = [0]+[-INF]*(n+10)
for i in range(n):
    if dp[i]==-INF:continue
    for c,a in use:
        dp[i+c]=max(dp[i+c],dp[i]+1)
l = dp[n]
ans = ["0"]*l
num = n
for i in range(l):
    for c,a in use:
        if dp[num-c]==dp[num]-1:
            ans[i]=str(a)
            num-=c
            break
print("".join(ans))

Submission status: Accepted

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N,M = IL()
A = IL()

dic = {1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}
usable = DD(int)
for a in A:
  usable[dic[a]] = max(usable[dic[a]],a)
  
dp = [-INF for i in range(N+1)]
dp[0] = 0

for i in range(N):
  for k in usable:
    if i+k<=N:
      dp[i+k] = max(dp[i+k],dp[i]*10+usable[k])
print(dp[-1])

Submission status: Accepted

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

# num[i] = iを作るために必要なマッチの本数
# 1-indexになるよう、形式的にnum[0] = 0とした
num = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]

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

for i in range(N + 1):
    for a in A:
        # 遷移元がないならスキップ
        if dp[i] == -1:
            continue
        # 遷移先がないならスキップ
        elif i + num[a] > N:
            continue
        # 末尾にaをつける = 今の数字を10倍してaを足す
        else:
            dp[i + num[a]] = max(dp[i + num[a]], dp[i] * 10 + a)

# ちょうどN本使って作れる最大の数
print(dp[N])

Submission status: Accepted

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

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

for i in range(1,N+1):
    for a in A:
        if i-cost[a]>=0 and dp[i-cost[a]]!=None:
            s=dp[i-cost[a]]+str(a)
            if dp[i]==None or len(dp[i])<len(s):
                dp[i]=s
            elif len(dp[i])>len(s):
                continue
            else:
                dp[i]=max(dp[i],s)
            
            
print(dp[N])

Submission status: Accepted

Solution code:
INF=float('inf')
cost=[-1,2,5,5,4,5,6,3,7,6]
N,M=map(int,input().split())
A=list(map(int,input().split()))

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

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

Submission status: Accepted

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

num_of_matches = [6, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = ['x'] * (n+8)
dp[0] = ''
for i in range(n+1):
    if dp[i] == 'x':
        continue
    for aa in a:
        x = dp[i + num_of_matches[aa]]
        y = dp[i] + str(aa)
        if x == 'x':
            dp[i + num_of_matches[aa]] = y
        elif len(x) < len(y):
            dp[i + num_of_matches[aa]] = y
        elif len(x) == len(y):
            if x < y:
                dp[i + num_of_matches[aa]] = y
print(dp[n])

Submission status: Accepted

Solution code:

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

X.sort(reverse=True)
num = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [-1] * (N + 1)
dp[0] = 0

for a in X:
    for i in range(N + 1):
        if dp[i] == -1 or i + num[a] > N:
            continue
        dp[i + num[a]] = max(dp[i + num[a]], dp[i] * 10 + a)

print(dp[-1])

Submission status: Accepted

Solution code:

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

X.sort(reverse=True)
count = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [-1] * (N + 1)
dp[0] = 0

for a in X:
    n = count[a]
    for i in range(N - n + 1):
        if dp[i] == -1:
            continue
        dp[i + n] = max(dp[i + n], dp[i] * 10 + a)

print(dp[-1])

Submission status: Accepted

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

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

inf = -10 * n
dp = [[inf] * (n+1) for _ in range(m+1)]
dp[0][0] = 0

for i,ai in enumerate(a,1):
    ci = cost[ai]
    for j in range(n+1):
        if(j >= ci):
            dp[i][j] = max(dp[i-1][j], dp[i][j-ci] + 1)
        else:
            dp[i][j] = dp[i-1][j]

cnt = [0] * 10
j = n
for i in range(m,0,-1):
    if(dp[i][j] < 0):
        continue

    ai = a[i-1]
    ci = cost[ai]
    while(j>=ci):
        if(dp[i][j] - dp[i][j-ci] == 1):
            j -= ci
            cnt[ai] += 1
        else:
            break

ans = ''
for i in range(9,0,-1):
    ans += str(i) * cnt[i]

print(ans)

Submission status: Accepted

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

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

for i in range(n, -1, -1):
    for j in range(m):
        x = b[a[j]]
        if dp[i] != -1 and i - x >= 0:
            dp[i - x] = max(dp[i - x], 10 * dp[i] + a[j])
            
print(dp[0])

Submission status: Accepted

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

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}

INF  =10**18
dp = [-INF]*(n+1)
dp[n] = 0
for i in reversed(range(1, n+1)):
    for a in A:
        j = i-d[a]
        if j >= 0:
            dp[j] = max(dp[j], dp[i]*10+a)
print(dp[0])

Submission status: Accepted

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



def main():
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    
    key = dict()
    if 1 in a:
        key[2] = 1
    for v in [5, 3, 2]:
        if v in a:
            key[5] = v
            break
    if 4 in a:
        key[4] = 4
    for v in [9, 6]:
        if v in a:
            key[6] = v
            break
    if 7 in a:
        key[3] = 7
    if 8 in a:
        key[7] = 8
 
    
    dp = [0]*(n+1)
   
    for i in range(n):
        if i != 0 and dp[i] == 0:
            continue
        for k, v in key.items():
            if i+k <= n:
                dp[i+k] = max(dp[i+k], 10*dp[i]+v)
    print(dp[n])
        
   
    
if __name__ == "__main__":
    main()

Submission status: Accepted

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

inf=float('inf')
#dp[i]=i本で最大何桁作れるか
dp=[-inf]*(n+1)
dp[0]=0
for i in range(1,n+1):
    for j in range(m):
        num=L[A[j]]
        if i>=num:
            dp[i]=max(dp[i],dp[i-num]+1)

sort_A=sorted(A,reverse=True)
ans=''
while True:
    if n==0:
        break
    for i in range(m):
        temp=sort_A[i]
        num=L[temp]
        if n>=num and dp[n-num]>=0:
            if dp[n-num]==dp[n]-1:
                ans+=str(temp)
                n-=num
                break
    

print(int(ans))

Submission status: Accepted

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

a.sort(reverse=True)
num_of_matches = [6, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [-1] * (n+1)
dp[0] = 0
for i in range(1, n+1):
    val = -1
    for aa in a:
        if i - num_of_matches[aa] < 0:
            continue
        if i - num_of_matches[aa] == 0:
            val = 1
        elif dp[i - num_of_matches[aa]] > 0:
            val = max(val, dp[i - num_of_matches[aa]] + 1)
    dp[i] = val

res = ''
remain = dp[n]
match = n
while match > 0:
    for i in range(m):
        if match - num_of_matches[a[i]] >= 0 and remain - 1 == dp[match-num_of_matches[a[i]]]:
            match -= num_of_matches[a[i]]
            remain -= 1
            res += str(a[i])
            break
print(res)

Submission status: Accepted

Solution code:
from collections import defaultdict

N, M = map(int, input().split())
A = list(map(int, input().split()))
L = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
D = defaultdict(int)

for i in A:
  if D[L[i]] < i:
    D[L[i]] = i

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

for i in range(1, N+1):
  for j in D.keys():
    if i-j >= 0:
      dp[i] = max(dp[i], dp[i-j] + 1)
    else:
      dp[i] = max(dp[i], -INF)

ans = ""
temp = N

#なるべく大きい数字から使う
for i, x in sorted(D.items(), key=lambda x: x[1], reverse=True):
  while temp - i >= 0 and dp[temp-i] == dp[temp] - 1:
    ans += str(x)
    temp -= i

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

N, M = map(int, input().split())
A = list(map(int, input().split()))
L = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
D = defaultdict(int)

for i in A:
  if D[L[i]] < i:
    D[L[i]] = i

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

for i in range(1, N+1):
  for j in D.keys():
    if i-j >= 0:
      dp[i] = max(dp[i], dp[i-j] + 1)
    else:
      dp[i] = max(dp[i], -INF)

ans = ""
temp = N

while temp > 0:
  for i, x in sorted(D.items(), key=lambda x: x[1], reverse=True):
    if temp - i >= 0 and dp[temp-i] == dp[temp] - 1:
      ans += str(x)
      temp -= i
      break

print(ans)

Submission status: Accepted

Solution code:
n,m=map(int, input().split())
lst=list(map(int,input().split()))
weight=[0,2,5,5,4,5,6,3,7,6]
DP=[-1]*(n+1)
DP[0]=0
for i in range(n+1):
  for x in lst:
    if i+weight[x]<n+1:
      DP[i+weight[x]]=max(DP[i+weight[x]], DP[i]*10+x)
print(DP[n])

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)
nums = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [-10**18]*(N+1)
dp[0] = 0

for i in range(N):
    for Ai in A:
        if i+nums[Ai]<=N:
            dp[i+nums[Ai]] = max(dp[i+nums[Ai]], dp[i]+1)

ans = []
now = N

for i in range(dp[N]):
    for Ai in A:
        if now-nums[Ai]>=0 and dp[now-nums[Ai]]==dp[N]-i-1:
            now -= nums[Ai]
            ans.append(str(Ai))
            break

print(''.join(ans))

Submission status: Accepted

Solution code:
import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


def main():
    N, M = NMI()
    A = NLI()

    match_dict = {i+1: m for i, m in enumerate([2,5,5,4,5,6,3,7,6])}
    usable_list = [[a, match_dict[a]] for a in A]
    usable_list.sort(key=lambda x: (x[1], -x[0]))

    # dp[i] はi本使った時の最大数
    dp = [-1]*(N+10)
    dp[0] = 0

    for i in range(N+1):
        for num, m in usable_list:
            dp[i+m] = max(dp[i+m], dp[i]*10+num)
    print(dp[N])



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
a=list(map(int,input().split()))
table={
  1:2,
  2:5,
  3:5,
  4:4,
  5:5,
  6:6,
  7:3,
  8:7,
  9:6,
}
dp=[-1]*(n+1)
dp[0]=0
for i in range(1,n+1):
  mx=-1
  for j in a:
    if not 0 <= i-table[j] < n+1:
      continue
    #print(i,i-table[j],dp[i-table[j]],j)
    if dp[i-table[j]]<0:
      continue
    if mx < dp[i-table[j]]*10+j:
      mx =dp[i-table[j]]*10+j
  dp[i]=mx
print(dp[n])

Submission status: Accepted

Solution code:
import math

n,_,*a=map(int,open(0).read().split())
match={1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}
a=sorted(a)

num=[0]*8

for d in a:
    num[match[d]]=d

dig=set(num)
dig.remove(0)
dig=sorted(list(dig),reverse=True)

dp=[-10**10]*(n+1)
dp[0]=0

for i in range(n+1):
    for d in dig:
        if i-match[d]<0:
            continue

        dp[i]=max(dp[i],dp[i-match[d]]+1)

ans=''

i=n
while i>0:
    for d in dig:
        if i-match[d]<0:
            continue
        if dp[i]==dp[i-match[d]]+1:
            ans=ans+str(d)
            break
    
    i-=match[d]

print(ans)

Submission status: Accepted

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

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

dp = [-1] * (n+10)
dp[0] = 0

for i in range(n):
    for j in range(m):
        nxt = match_num[a[j]]
        if dp[i]>=0:
            dp[i+nxt] = max(dp[i+nxt], dp[i]*10 + a[j])
print(dp[n])

Submission status: Accepted

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

def nax(a, b):
    if a == '-':
        return b
    if len(a) != len(b):
        return a if len(a)>len(b) else b
    return a if a>b else b


match = [2,5,5,4,5,6,3,7,6]
# dp[i]  : iほんのマッチを使ってできる数値の最大値
dp = ['-'] * 11000
dp[0] = ''

for i in range(N+1):
    if dp[i] == '-':
        continue
    for a in A:
        dp[i+match[a-1]] = nax(dp[i+match[a-1]], dp[i] + chr(ord('0') + a))

print(dp[N])

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,m = list(map(int, input().split()))
a = list(map(int, input().split()))
d = [None,2,5,5,4,5,6,3,7,6]
ds = [(i, d[i]) for i in a] # (数、本数)
ds.sort(reverse=True)

dp = [list(0 for _ in range(m+1)) for _ in range(n+1)]
for i in range(1, n+1):
    for j,(ii,num) in enumerate(ds):
        if i-num==0 or (i-num>0 and dp[i-num][0]>0):
            item = dp[i-num][:]
            item[0] += 1
            item[j+1] += 1
#             print(item)
            dp[i] = max(dp[i], item)
ans = ""
for i,item in enumerate(dp[n][1:]):
    ans += str(ds[i][0])*item
print(ans)

Submission status: Accepted

Solution code:
from math import log10
n,m = map(int,input().split())
a = list(map(int,input().split()))
l = [0,2,5,5,4,5,6,3,7,6]

dp = [0]*(n+1)
for i in range(n):
    for j in range(m):
        if dp[i] == 0 and i != 0:
            continue
        x = a[j]
        t = l[x]
        if i+t > n:
            continue
        if dp[i] == 0:
            s0 = x
            s1 = x
        else:
            k = int(log10(dp[i]))
            s0 = x*10**(k)+dp[i]
            s1 = 10*dp[i]+x
        dp[i+t] = max(dp[i+t],s0,s1)
print(dp[-1])

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
from collections import defaultdict
a=list(map(int,input().split()))
dic={i:[2,5,5,4,5,6,3,7,6][i-1]for i in range(1,10)}
s={}
for i in a:
    if dic[i] in s:
        s[dic[i]]=max(s[dic[i]],i)
    else:
        s[dic[i]]=i
ok=list(s.items())#hon,digit
dp=[-float('inf')]*(n+1)
dp[0]=0
for i in range(1,n+1):
    for h,d in ok:
        if h<=i:
            dp[i]=max(dp[i],dp[i-h]+1)
from operator import itemgetter as it 
ok.sort(reverse=1,key=it(1))
ans=''
now=n
keta=dp[n]
while keta>1:
    for h,d in ok:
        if now>h and dp[now]==dp[now-h]+1:
            ans+=str(d);now-=h;keta-=1;break
print(ans+str(s[now]))

Submission status: Accepted

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

if N % 2 == 0:
  if 1 in A:
    print(int('1'*(N//2)))
    exit()

need =(2,5,5,4,5,6,3,7,6)

if 2 in A and 3 in A:
  del A[A.index(2)]
if 3 in A and 5 in A:
  del A[A.index(3)]
if 6 in A and 9 in A:
  del A[A.index(6)]
if 1 in A and 4 in A:
  del A[A.index(4)]
if 6 in A and 7 in A:
  del A[A.index(6)] 
if 7 in A and 9 in A:
  del A[A.index(9)] 
if 1 in A and 6 in A:
  del A[A.index(6)] 
if 1 in A and 9 in A:
  del A[A.index(9)] 
  
A = tuple(A)
M = len(A)

dp = [[0]*(N+1) for _ in range(M)]
dpmax = [0]*(N+1)

def take_max():
  return max(A[i]*(10**len(str(tmp2)) + tmp2,tmp2*10+A[i]))

for j in range(2,N+1):
  tmpmax = 0
  for i in range(M):
    tmp = need[A[i]-1]
    if j == tmp:
      dp[i][j] = A[i]
    elif j > tmp:
      if dpmax[j-tmp] != 0:
        tmp2 = dpmax[j-tmp]
        dp[i][j] = take_max()
    if tmpmax < dp[i][j]:
      tmpmax = dp[i][j]
  dpmax[j] = tmpmax
  
print(dpmax[-1])

Submission status: Accepted

Solution code:
def examA():
    A, B = LI()
    if B%A==0:
        ans = A+B
    else:
        ans = B-A
    print(ans)
    return

def examB():
    N, M = LI()
    Flag = [0]*M
    for i in range(N):
        K = LI()
        for j in range(1,K[0]+1):
            Flag[K[j]-1] +=1
    ans = 0
    for i in Flag:
        if i==N:
            ans +=1
    print(ans)
    return

def gcd(x,y):
    if y==0:
        return x
    while(y!=0):
        x, y = y,x%y
    return x
def examC():
    N = I()
    A = LI()
    cur = A[0]
    for i in range(N-1):
        cur = gcd(cur,A[i+1])
    ans = cur
    print(ans)
    return

def examD():
    N, M = LI()
    A = LI(); A.sort()
    Matti = [2,5,5,4,5,6,3,7,6]
    D = {}
    for a in A:
        D[Matti[a-1]] = a
    D = sorted(D.items())
    #print(D)
    dp = [-inf]*(N+10)
    dp[0] = 0
    for i in range(N):
        for matti,num in D:
            dp[i+matti] = max(dp[i+matti],dp[i]+1)
    #print(dp[:N+1])
    D = sorted(D, key=lambda x: x[1], reverse=True)
    #print(D)
    used = []
    i = N
    for matti,num in D:
        while (i > 0):
            # print(i)
            # input()
            #print(i,matti,used)
            if i-matti<0:
                break
            if dp[i-matti]==dp[i]-1:
                used.append(num)
                i -= matti
            else:
                break
    #print(used)
    used.sort(reverse=True)
    ans = "".join(map(str,used))
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examD()


"""
31 2
5 8
"""

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
from math import sqrt, pi
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

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

N, M = getNM()
A = getList()

digit = []
for i in A:
    digit.append([i, num[i - 1]])
digit.sort(key = lambda i: i[1])

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

# 桁数を調べる
for i in range(1, N + 1):
    for j in range(M):
        if i >= digit[j][1]:
            dp[i] = max(dp[i], dp[i - digit[j][1]] + 1)

# 数字を組み上げる
ans = ''
now = N
digit.sort(reverse = True)
while now > 0:
    for j in range(M):
        if now - digit[j][1] >= 0 and dp[now] == dp[now - digit[j][1]] + 1:
            now -= digit[j][1]
            ans += str(digit[j][0])
            break
print(ans)