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=[int(i) for i in input().split()]
Match=[0,2,5,5,4,5,6,3,7,6]
A.sort(reverse=True)
dp=[0]*(N+1)
dp[0]=1
for i in range(1,N+1):
  for a in A:
    if i>=Match[a]:
      dp[i]|=dp[i-Match[a]]<<1

for k in range(N)[::-1]:
  if dp[N]&(1<<k):
    S=k
    break
ans=[]
m=0
for k in range(S):
  if N-Match[A[m]]>=0:
    if dp[N-Match[A[m]]]&(1<<(S-k-1)):
      ans.append(str(A[m]))
      N-=Match[A[m]]
    else:
      for l in range(m+1,len(A)):
        if N-Match[A[l]]>=0:
          if dp[N-Match[A[l]]]&(1<<(S-k-1)):
            m=l
            ans.append(str(A[m]))
            N-=Match[A[m]]
            break
  else:
    for l in range(m+1,len(A)):
      if N-Match[A[l]]>=0:
        if dp[N-Match[A[l]]]&(1<<(S-k-1)):
          m=l
          ans.append(str(A[m]))
          N-=Match[A[m]]
          break
print("".join(ans))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from sys import stdin

N, M, *A = map(int, stdin.read().split())
req = {1: 2,
       2: 5,
       3: 5,
       4: 4,
       5: 5,
       6: 6,
       7: 3,
       8: 7,
       9: 6}

B = sorted([(a, req[a]) for a in A], key=lambda x: x[0], reverse=True)
a_min, n_min = min(B, key=lambda x: x[1])
g = [(a, n-n_min) for a, n in B if a > a_min and n > n_min]
l = [(a, n-n_min) for a, n in B if a < a_min and n > n_min]
l.sort(key=lambda x: x[1], reverse=True)
C = g + l

def dp(rem, C):
    ret = None
    if rem == 0:
        ret = []
    elif rem > 0:
        for i in range(len(C)):
            a, m = C[i]
            nxt = dp(rem-m, C[i:])
            if nxt is not None:
                ret = [a] + nxt
                break
    return ret


i = 0
while True:
    quo = N // n_min - i
    rem = N % n_min + i * n_min
    lst = dp(rem, C)
    if lst is not None:
        lst = sorted(lst + [a_min] * (quo-len(lst)), reverse=True)
        print(''.join(map(str, lst)))
        break
    i += 1

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]+[-1]*n*9
for i in range(n):
 for j in a:
  if d[i]+1:d[i+c[j]]=max(d[i+c[j]],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]+[-1]*n*9
for i in range(n):
 for j in a:
  if d[i]>=0:d[i+c[j]]=max(d[i+c[j]],d[i]*10+j)
print(d[n])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
from collections import deque
import copy
import math
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, M] = [int(input_raw[0]), int(input_raw[1])]
    input_raw = read_func().strip().split()
    A = []
    A_num = {}
    A_num[1] = 2
    A_num[2] = 5
    A_num[3] = 5
    A_num[4] = 4
    A_num[5] = 5
    A_num[6] = 6
    A_num[7] = 3
    A_num[8] = 7
    A_num[9] = 6
    for i in range(M):
        A.append(int(input_raw[i]))

    dp = [0] * (N + 1)
    A.sort(reverse = True)

    for i in range(1, N + 1):
        max_num = -sys.maxint
        for a in A:
            if i - A_num[a] >= 0 and dp[i - A_num[a]] >= 0:
                max_num = max(max_num, dp[i - A_num[a]] + 1)
        dp[i] = max_num

    remain = N
    s = ""
    for i in range(dp[N]):
        for a in A:
            if remain - A_num[a] >= 0:
                if dp[remain - A_num[a]] == dp[remain] - 1:
                    s += str(a)
                    remain = remain - A_num[a]
                    break
    print s



if __name__ == '__main__':
    main()

Submission status: Accepted

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

costp = sorted([ (cost[a] ,a) for a in A], key=lambda x:x[1], reverse=True)
costX = [ z[0] for z in costp]
A = [ z[1] for z in costp]
# print(A,costX)

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

for i in range(N, 1, -1):
    if (dp[i]) == -1:
        continue

    for c,a in zip(costX,A):
        if i-c >= 0:
            dp[i-c] = dp[i] + 1


ans = ""

i = 0
while i<N:
    # print(i)
    for c,a in zip(costX,A):
        # print(c,a,i)
        # if i+c <= N:
        #     print("i: {}, dp[i]=".format(i), dp[i], ", dp[i+c]: ", dp[i+c], "c=",c, "a=",a)
        # else: print("i: {}, dp[i]=".format(i), dp[i], ",c=",c, "a=",a)
        
        if i+c <= N:
            if dp[i]-1 == dp[i+c]:
                ans += str(a)
                i = i+c
                break

print(ans)
# print(dp)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
needs = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
usable = {}
for a in map(int, input().split()):
    na = needs[a]
    if na in usable:
        usable[na] = max(usable[na], a)
    else:
        usable[na] = a
use_keys = sorted(usable.keys())

dp = [-9] * (n + 1)
dp[0] = 0
for d in range(2, min(8, n + 1)):
    for u in use_keys:
        du = d - u
        if du < 0:
            break
        dp[d] = max(dp[d], dp[du] + 1)
for d in range(8, n + 1):
    for u in use_keys:
        dp[d] = max(dp[d], dp[d - u] + 1)

ans = ''
remain = n
rk = [(str(a), needs[a]) for a in sorted(usable.values(), reverse=True)]
for d in range(dp[n] - 1, -1, -1):
    for a, na in rk:
        ra = remain - na
        if ra < 0:
            continue
        if dp[ra] == d:
            ans += a
            remain = ra
            break

print(ans)

Submission status: Accepted

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

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

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

mtoa = {}
for a in sorted(A):
    mtoa[ntom[a]] = a

ms = sorted(mtoa.keys(), key=lambda x: mtoa[x], reverse=True)
dp = [0] + [float('-inf')] * N
for i in range(min(ms), N+1):
    dp[i] = max(dp[i-x] for x in ms if i >= x) + 1

ans = []
left = N
while left:
    for m in ms:
        if left >= m and dp[left] == dp[left - m] + 1:
            left -= m
            ans.append(mtoa[m])
            break
        
print(*ans, sep='')

Submission status: Accepted

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

cost={1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}
dp=[-1]*(n+1)
v=[0]*(n+1)

dp[0]=0
for i in range(1,n+1):
    for j in range(10)[::-1]:
        if not j in a or i<cost[j]:continue
        if dp[i]<dp[i-cost[j]]+1:
            dp[i]=dp[i-cost[j]]+1
            v[i]=j

p=n
while p!=0:
    print(v[p],end="")
    p-=cost[v[p]]
print()

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
A = list(map(int,input().split()))
A.sort(reverse=True)
cost = [2,5,5,4,5,6,3,7,6]
# dp[i]: ちょうどi本のマッチを使うときの最大の桁数
dp = [-float('inf')]*(N+1)
dp[0] = 0
for i in range(1,N+1):
    for a in A:
        if i - cost[a-1] >= 0:
            dp[i] = max(dp[i],dp[i-cost[a-1]] + 1)
ans = ""
# dp[N]桁は確定,あとは大きいものを上に持ってくる
remain = dp[N]
match = N
while match > 0:
    # 降順にソートしたAで大きいものから見る
    for a in A:
        # (左辺)： 仮にaを選ぶとcost[a-1]本のマッチを消費する
        # 今持っているマッチの本数はmatchなので操作後のマッチの本数はmatch-cost[a-1]
        # (右辺)： 仮にaを選んだとして,残り作らなければならない桁数
        # match < cost[a-1]: 今持っているマッチの本数 < 作るのに必要な本数
        # (左辺) == (右辺): aを選んでも残りの下の桁に影響がない
        if match - cost[a-1] < 0:
            continue
        if dp[match-cost[a-1]] == remain - 1:
            ans += str(a)
            remain -= 1
            match -= cost[a-1]
            break
print(ans)

Submission status: Accepted

Solution code:
r=raw_input;N,M=r().split();c,A=[0,2,5,5,4,5,6,3,7,6],sorted(r().split());N=int(N);D,a=[0]+[-1]*N*9,[0,0]*N
for i in range(1,N+1):
 for j in A:
  p=i-c[int(j)]
  if min(p,D[p],D[p]+1-D[i])>=0:D[i],a[i]=D[p]+1,j
S=""
while N:S+=a[N];N-=c[int(a[N])]
print S

Submission status: Accepted

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

c = list(map(int,input().split()))

c.sort()
cc = [[c[i],k[c[i]-1]] for i in range(b)]
ccc = [[c[i],k[c[i]-1]] for i in range(b)]
dp = [-1 for i in range(a+1)]
dp[0] = 0
cc.sort(key = lambda x:x[1])
for j in range(b):
	for i in range(a+1):
		if i-cc[j][1] >= 0 and dp[i-cc[j][1]] >= 0:
			dp[i] = max(dp[i-cc[j][1]]+1,dp[i])
ccc.reverse()
k = a
co = ''
for i in range(dp[a]):
	for j in range(b):
		if k-ccc[j][1] >= 0 and dp[k-ccc[j][1]] == dp[k] - 1:
			co += str(ccc[j][0])
			k -= ccc[j][1]
			break
print(co)

Submission status: Accepted

Solution code:
mi = {"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 = input().split()
dpn = [0] + [-1] * 10010
dp = [""] * 10010
for a in A:
    for i in range(n - mi[a] + 1):
        if dpn[i] != -1:
            cnt = dpn[i] + 1
            if dpn[i + mi[a]] < cnt:
                dpn[i + mi[a]] = cnt
                dp[i + mi[a]] = max(a + dp[i], dp[i] + a)
            elif dpn[i + mi[a]] == cnt:
                dp[i + mi[a]] = max(dp[i + mi[a]], a + dp[i], dp[i] + a)
print(dp[n])

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
A_list = list(map(int, input().split()))
cost_Dict = {1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6}
A_Dict = {}
for x in A_list:
    A_Dict[x] = cost_Dict[x]
#def A_cost(x):
#    return A_Dict[x]
dp = [-float('inf')] * (N+1)
dp[0] = 0

A_list = list(A_Dict.keys())
A_list.sort(reverse=True)

for i in range(N+1):
    _list = []
    for x in A_list:
        if i - A_Dict[x] < 0:
            continue
        else:
            dp[i] = max(dp[i], dp[i-A_Dict[x]]+1)

ans = ""
cost = N
while cost > 0:
    for x in A_list:
        if cost - A_Dict[x] < 0:
            continue
        elif dp[cost - A_Dict[x]] == dp[cost] - 1:
            ans += str(x)
            cost -= A_Dict[x]
            break

print(ans)

Submission status: Accepted

Solution code:
def inpl(): return list(map(int, input().split()))

N, M = inpl()
A = inpl()
A.sort(reverse = True)

match = (0, 2, 5, 5, 4, 5, 6, 3, 7, 6)
dp = [0]+[-float('inf')]*N

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

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

Submission status: Accepted

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

num_base = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
num_set = set([0])
for i in range(m):
    num_set.add(num_base[a[i]])


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:
r=raw_input
N,M=r().split()
c=[0,2,5,5,4,5,6,3,7,6]
A=sorted(r().split())
N=int(N)
D,a=[0]+[-1]*N*9,[0,0]*N
for i in range(1, N + 1):
 for j in A:
  p=i-c[int(j)]
  if min(p,D[p],D[p]+1-D[i])>=0:D[i],a[i]=D[p]+1,j
S=""
while N:S,N=S+a[N],N-c[int(a[N])]
print S

Submission status: Accepted

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

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

#まず最高何桁の数にできるか考えよう.

SET_A=set(A)

ANSLIST=[0]
def dfs(i,NOW):
    if ANSLIST[0]!=0:
        return
    ANS=0
    if NOW==N:
        L=sorted(list(i),reverse=True)
        #print(L)
        
        ANSLIST[0]=int(("".join(L)))
        return

    elif NOW>N:
        return 
    else:
        for a in A:
            dfs(i+str(a),NOW+M[a])


A.sort(reverse=True)
A.sort(key=lambda x:M[x])
dfs("",0)

x=ANSLIST[0]
stx=str(x)
from collections import Counter
counter=Counter(stx)


import itertools
for i,j,k in list(itertools.combinations(range(1,10),3)):
    for l,m,n in list(itertools.combinations(range(1,10),3)):
        if i in SET_A and j in SET_A and k in SET_A and l in SET_A and m in SET_A and n in SET_A and M[i]+M[j]+M[k]==M[l]+M[m]+M[n] and \
           counter[str(i)]>0 and counter[str(j)]>0 and counter[str(k)]>0 and (n>k or (n==k and m>j) or (n==k and m==j and l>i)):
                    x=min(counter[str(i)],counter[str(j)],counter[str(k)])
                    counter[str(i)]-=x
                    counter[str(j)]-=x
                    counter[str(k)]-=x
                    counter[str(l)]+=x
                    counter[str(m)]+=x
                    counter[str(n)]+=x

for i,j in list(itertools.combinations(range(1,10),2)):
    for l,m in list(itertools.combinations(range(1,10),2)):
        if i in SET_A and j in SET_A and l in SET_A and m in SET_A and M[i]+M[j]==M[l]+M[m] and \
           counter[str(i)]>0 and counter[str(j)]>0 and (m>j or (m==j and l>i)):
                    x=min(counter[str(i)],counter[str(j)])
                    counter[str(i)]-=x
                    counter[str(j)]-=x

                    counter[str(l)]+=x
                    counter[str(m)]+=x

for i in range(1,10):
    for l in range(1,10):
        if i in SET_A and l in SET_A and l>i and M[i]==M[l] and counter[str(i)]>0:
            counter[str(l)]+=counter[str(i)]
            counter[str(i)]=0



ANS=""
for i in range(9,-1,-1):
    ANS+=str(i)*counter[str(i)]

print(ANS)

Submission status: Accepted

Solution code:
def inpl(): return list(map(int, input().split()))

N, M = inpl()
A = inpl()
A.sort(reverse = True)

inf = float('inf')
match = (inf, 2, 5, 5, 4, 5, 6, 3, 7, 6)
matnum = set([match[a] for a in A])
dp = [0]+[-inf]*N

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

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

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)
dp = [0]+[-1]*n
for i in range(1,n+1):
    for j in a:
        if l[j] <= i:
            dp[i] = max(dp[i], dp[i-l[j]]*10+j)
print(dp[-1])

Submission status: Accepted

Solution code:
def d_match_matching(N, M, A):
    # num_usedmatch[n]: 数字nを作るのに必要なマッチの本数
    num_usedmatch = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}

    # dp[i]: ちょうどi本のマッチ棒を使って作れる整数の最大値
    dp = [-1] * (N + 1)  # 解説では-∞で初期化しているが、最大値は負にならないので
    dp[0] = 0  # 0本のマッチ棒で作れる整数の桁数は0とする(作れない)
    for i in range(1, N + 1):
        for a in A:
            if i - num_usedmatch[a] >= 0:
                # 数字aは使用できるので、整数の末尾に付け足す
                dp[i] = max(dp[i], dp[i - num_usedmatch[a]] * 10 + a)
    return dp[N]

N, M = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
print(d_match_matching(N, M, A))

Submission status: Accepted

Solution code:
import numpy as np
import math

INF = 1000000

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

match = {a:match[a] for a in A}

dp = []

for i in range(N+1):
    if i == 0:
        dp.append(0)
    else:
        tmp = [dp[i-m] for m in match.values() if i-m >= 0]
        if tmp == []:
            dp.append(-float('inf'))
        else:
            dp.append(max(tmp)+1)
s = ''
nums = list(match.keys())
nums.sort(reverse=True)
while(True):
    for num in nums:
        if N - match[num] >= 0 and dp[N - match[num]] == dp[N] - 1:
            s = s + str(num)
            N-=match[num]
            break
    if N == 0:
        break

print(int(s))

Submission status: Accepted

Solution code:
def num(x):
	if x == 1:
		return 2
	elif x == 2:
		return 5
	elif x == 3:
		return 5
	elif x == 4:
		return 4
	elif x == 5:
		return 5
	elif x == 6:
		return 6
	elif x == 7:
		return 3
	elif x == 8:
		return 7
	elif x == 9:
		return 6

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

num_to_dig = [0 for _ in range(9)]
for i in a:
	num_to_dig[num(i)] = max(num_to_dig[num(i)], i)

dp = [-float("inf")] * (n+1)
dp[0] = 0
for i in range(1, n+1):
	for j in range(9):
		if num_to_dig[j] > 0 and i >= j:
			dp[i] = max(dp[i], dp[i-j] * 10 + num_to_dig[j])
print(dp[n])

Submission status: Accepted

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

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18

N, M = map(int, raw_input().split())
c = [0,2,5,5,4,5,6,3,7,6]
A = sorted(map(int, raw_input().split()))

D = [0] + [-1] * N * 9
a = [0, 0] * N

for i in range(1, N + 1):
 for j in A:p=i-c[j];D[i],a[i]=[[D[i],a[i]],[D[p]+1,j]][min(p,D[p],D[p]+1-D[i])>=0]

S, p = "", N
while p:S,p=S+str(a[p]),p-c[a[p]]
print S

Submission status: Accepted

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

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18

N, M = map(int, raw_input().split())
c = [0,2,5,5,4,5,6,3,7,6]
A = sorted(map(int, raw_input().split()))

D = [0] + [-1] * N * 9
a = [0, 0] * N

for i in range(1, N + 1):
 for j in A:
  p=i-c[j]
  if min(p,D[p],D[p]+1-D[i])>=0:D[i],a[i]=D[p]+1,j

S, p = "", N
while p:S,p=S+str(a[p]),p-c[a[p]]
print S

Submission status: Accepted

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

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18

N, M = map(int, raw_input().split())
c = [0,2,5,5,4,5,6,3,7,6]
A = sorted(map(int, raw_input().split()))

D = [0] + [-1] * N * 9
a = [0, 0] * N

for i in range(1, N + 1):
    for j in A:
        p = i - c[j]
        if min(p, D[p], D[p] + 1 - D[i]) >= 0:
            D[i], a[i] = D[p] + 1, j

S, p = "", N
while p:S,p=S+str(a[p]),p-c[a[p]]
print S

Submission status: Accepted

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

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18

N, M = map(int, raw_input().split())
c = [0,2,5,5,4,5,6,3,7,6]
A = sorted(map(int, raw_input().split()))

D = [0] + [-1] * N * 9
a = [0, 0] * N

for i in range(1, N + 1):
    for j in A:
        p = i - c[j]
        if min(p, D[p], D[p] + 1 - D[i]) >= 0:
            D[i], a[i] = D[p] + 1, j

S, p = "", N
while p:
 S+=str(a[p])
 p-=c[a[p]]
print S

Submission status: Accepted

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

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18

N, M = map(int, raw_input().split())
c = [0,2,5,5,4,5,6,3,7,6]
A = sorted(map(int, raw_input().split()))

D = [0] + [-1] * N * 9
a = [0, 0] * N

for i in range(1, N + 1):
    for j in A:
        p = i - c[j]
        if min(p, D[p], D[p] + 1 - D[i]) >= 0:
            D[i], a[i] = D[p] + 1, j

S, p = "", N
while p:
 S+=str(a[p])
 p-=c[a[p]]
###while p:S,p=S+str(a[p]),p-c[a[p]]
print S

Submission status: Accepted

Solution code:
N, M = map(int, raw_input().split())
c = [0,2,5,5,4,5,6,3,7,6]
A = sorted(map(int, raw_input().split()))

D = [0] + [-1] * N * 9
a = [0, 0] * N

for i in range(1, N + 1):
    for j in A:
        p = i - c[j]
        if min(p, D[p], D[p] + 1 - D[i]) >= 0:
            D[i], a[i] = D[p] + 1, j

S, p = "", N
while p:
    S += str(a[p])
    p -= c[a[p]]
print S

Submission status: Accepted

Solution code:
Q = {
    1: 2,
    2: 5,
    3: 5,
    4: 4,
    5: 5,
    6: 6,
    7: 3,
    8: 7,
    9: 6,
}

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

# 桁数の最大
dp = [-1] * (N + 1)
dp[0] = 0

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

# 整数の復元
ans = ''

# 大きな数から試す
A.sort(reverse=True)

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

print(ans)

Submission status: Accepted

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

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18

N, M = map(int, raw_input().split())
cost = [0,2,5,5,4,5,6,3,7,6]
A = sorted(map(int, raw_input().split()))

DP = [0] + [-1] * N * 9
ans = [0, 0] * N

for i in range(1, N + 1):
    for j in A:
        pos = i - cost[j]
        if min(pos, DP[pos], DP[pos] + 1 - DP[i]) >= 0:
            DP[i], ans[i] = DP[pos] + 1, j

S, pos = "", N
while pos:
    S += str(ans[pos])
    pos -= cost[ans[pos]]

print S

Submission status: Accepted

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

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18

N, M = map(int, raw_input().split())
cost = [0,2,5,5,4,5,6,3,7,6]
A = sorted(map(int, raw_input().split()))

DP = [0] + [-1] * N
ans = [0, 0] * N

for i in range(1, N + 1):
    for j in A:
        pos = i - cost[j]
        if pos >= 0 and DP[pos] >= 0 and DP[i] <= DP[pos] + 1:
            DP[i], ans[i] = DP[pos] + 1, j

S = ""
pos = N
while pos:
    S += str(ans[pos])
    pos -= cost[ans[pos]]

print S

Submission status: Accepted

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

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18

N, M = map(int, raw_input().split())
cost = [0,2,5,5,4,5,6,3,7,6]
A = sorted(map(int, raw_input().split()))

DP = [0] + [-1] * N
ans = [0, 0] * N

for i in range(1, N + 1):
    for j in A:
        pos = i - cost[j]
        if pos < 0 or DP[pos] < 0:
            continue
        if DP[i] <= DP[pos] + 1:
            DP[i] = DP[pos] + 1
            ans[i] = j

S = ""
pos = N
while pos:
    S += str(ans[pos])
    pos -= cost[ans[pos]]

print S

Submission status: Accepted

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

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18

N, M = map(int, raw_input().split())
cost = {1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6}
A = sorted(map(int, raw_input().split()))

DP = [0] + [-1] * N
ans = [0, 0] * N

for i in range(1, N + 1):
    for j in A:
        pos = i - cost[j]
        if pos < 0 or DP[pos] < 0:
            continue
        if DP[i] <= DP[pos] + 1:
            DP[i] = DP[pos] + 1
            ans[i] = j

S = ""
pos = N
while pos:
    S += str(ans[pos])
    pos -= cost[ans[pos]]

print S

Submission status: Accepted

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

MAX_N = 10005
MAX_M = 11
dp = [[-1 for j in range(MAX_N)] for i in range(MAX_M)]


def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()

    f = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
    dp[0][0] = 0
    for i in range(M):
        for j in range(N+1):
            if j < f[A[i]]:
                dp[i+1][j] = dp[i][j]
            else:
                dp[i+1][j] = max(dp[i][j], dp[i+1][j-f[A[i]]]+1)

    ans = []
    cj = N
    for i in range(M, 0, -1):
        for j in range(cj//f[A[i-1]], -1, -1):
            x = dp[i-1][cj-f[A[i-1]]*j]
            y = dp[i][cj]
            if dp[i-1][cj-f[A[i-1]]*j] == dp[i][cj] - j:
                for k in range(j):
                    ans.append(str(A[i-1]))
                cj -= f[A[i-1]] * j
                break

    print("".join(ans))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18

N, M = map(int, raw_input().split())
cost = {1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6}
A = map(int, raw_input().split())

DP = [0] + [-1] * N
ans = [0] * N + [0]

for i in range(1, N + 1):
    for j in range(10)[::-1]:
        if not j in A:
            continue
        if cost[j] > i:
            continue
        if DP[i - cost[j]] < 0:
            continue
        if DP[i] < DP[i - cost[j]] + 1:
            DP[i] = DP[i - cost[j]] + 1
            ans[i] = j

S = ""
pos = N
while pos != 0:
    S += str(ans[pos])
    pos -= cost[ans[pos]]

print S

Submission status: Accepted

Solution code:
n, m = list(map(int, input().split()))
li = list(map(int, input().split()))
di = {}
for i, d in enumerate([2,5,5,4,5,6,3,7,6], 1):
    di[i] = d
li.sort(reverse=True)
dd = {}
for a in li:
    hon = di[a]
    if hon not in dd:
        dd[hon] = a

h2d = [-float('inf')] * (n + 1)
h2d[0] = 0
pre = [None] * (n + 1)
for j in range(1, n + 1):
    for a in li:
        ho = di[a]
        if j < ho:
            continue
        dig = h2d[j - ho] + 1
        if dig > h2d[j]:
            h2d[j] = dig
            pre[j] = j - ho

ans = []
while n > 0:
    ans.append(dd[n - pre[n]])
    n = pre[n]
ans.sort(reverse=True)
print(*ans, sep='')

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
A=sorted([int(i) for i in input().split()],reverse=True)
num=[6,2,5,5,4,5,6,3,7,6]
INF=10**15
dp=[-INF for i in range(N+1)];dp[0]=0
for i in range(1,N+1):
    for j in range(M):
        if N>=i-num[A[j]]>=0:
            dp[i]=max(dp[i],dp[i-num[A[j]]]+1)
K=N
i=0
ans=""
while(K>0):
    if not(N>=K-num[A[i]]>=0):
        i+=1
        continue
    if dp[K-num[A[i]]]==dp[K]-1:
        ans=ans+str(A[i])
        K-=num[A[i]]
    else:
        i+=1
print(ans)

Submission status: Accepted

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


def solve(N, M, As):
    dp = [-1 for _ in range(N + 1)]
    dp[0] = 0
    for i in range(N + 1):
        for a in As:
            c = Matches[a]
            if dp[i] == -1:
                continue
            if i + c <= N:
                dp[i + c] = max(dp[i + c],
                                dp[i] * 10 + a)
    return dp[N]

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

Submission status: Accepted

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

M={1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}
M={a:M[a] for a in A}

dp=[]
for i in range(N+1):
  if i==0:
    dp.append(0)
  else:
    tmp=[dp[i-m] for m in M.values() if i-m>=0]
    if tmp==[]:
      dp.append(-float('inf'))
    else:
      dp.append(max(tmp)+1)
      
Ml=list(M.keys())
Ml.sort(reverse=True)
tmp=''
while 1:
  for ml in Ml:
    if N-M[ml]>=0 and dp[N-M[ml]]==dp[N]-1:
        tmp+=str(ml)
        N-=M[ml]
        break
  if N==0:
    break
    
print(tmp)

Submission status: Accepted

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


def solve(N, M, As):
    dp = [-1 for _ in range(N + 1)]
    dp[0] = 0
    for i in range(N):
        for a in sorted(As, reverse=True):
            c = Matches[a]
            if dp[i] == -1:
                continue
            if i + c <= N:
                dp[i + c] = max(dp[i+c],
                                dp[i] * 10 + a)
    return dp[N]

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

Submission status: Accepted

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


def solve(N, M, As):
    dp = [-1 for _ in range(N + 1)]
    dp[0] = 0
    for a in sorted(As, reverse=True):
        c = Matches[a]
        for i in range(N - c + 1):
            if dp[i] == -1:
                continue
            dp[i + c] = max(dp[i+c],
                            dp[i] * 10 + a)
    return dp[N]

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

Submission status: Accepted

Solution code:
#参照　https://atcoder.jp/contests/abc118/submissions/4292288
n,m = map(int, input().split())
b = [0,2,5,5,4,5,6,3,7,6]
a = [0]+list(map(int, input().split()))
f = [-1]*(n+1)
f[0]=0
for i in range(1,n+1):
    for j in range(1,m+1):
        x = a[j]
        if(i-b[x]<0):
            continue
        f[i] = max(f[i],f[i-b[x]]*10 + x)
        #print(i+1,"番目に,",str(f[i])+","+str(f[i-b[x]]*10 + x),"の最大値を入れると",f)
print(f[n])