Problem:


Score : 400 points

Problem Statement

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

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

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

Constraints

All values in input are integers.

2 \leq N \leq 10^4

1 \leq M \leq 9

1 \leq A_i \leq 9

A_i are all different.

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

Input

Input is given from Standard Input in the following format:

N M
A_1 A_2 ... A_M

Output

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

Sample Input 1

20 4
3 7 8 4

Sample Output 1

777773

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

Sample Input 2

101 9
9 8 7 6 5 4 3 2 1

Sample Output 2

71111111111111111111111111111111111111111111111111

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

Sample Input 3

15 3
5 4 6

Sample Output 3

654



Sample input:
20 4
3 7 8 4


Sample output:
777773

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))
dict = dict(zip([i for i in range(1, 10)], [2, 5, 5, 4, 5, 6, 3, 7, 6]))
INF = 10 ** (N // 2 + 1)
dp = [-INF for i in range(N + 21)]
for a in A:
    dp[dict[a]] = max(dp[dict[a]], a)
for i in range(N + 1):
    for j in range(1, 10):
        dp[i] = max(dp[i], dp[i - j] * 10 + dp[j], dp[j] * 10 + dp[i - j])
print(dp[N])

Submission status: Accepted

Solution code:
N, M = map(int,input().split())
L = list(map(int,input().split()))
K = [0,2,5,5,4,5,6,3,7,6]
A = sorted([[L[k],K[L[k]]] for k in range(M)])[::-1]
dp = [0 for k in range(N+1)]

for k in range(1,N+1):
    t = -float("inf")
    for j in range(M):
        if k-A[j][1]>=0:
            t = max(t, dp[k-A[j][1]]+1)
    dp[k] = t

ans = ""
keta = dp[N]
match = N
while keta > 0:
    for k in range(M):
        if match-A[k][1] >= 0:
            if dp[match-A[k][1]] == keta-1:
                ans += str(A[k][0])
                match -= A[k][1]
                keta -= 1
                break
print(ans)

Submission status: Accepted

Solution code:
import copy


def compare_num(ans_tmp, candidate):
    sum_tmp = sum(ans_tmp)
    sum_candidate = sum(candidate)
    if sum_tmp == sum_candidate:
        for t, c in zip(ans_tmp, candidate):
            if t > c:
                return ans_tmp
            elif t < c:
                return candidate
        else:
            return ans_tmp

    else:
        return ans_tmp if sum_tmp > sum_candidate else candidate


N, M = map(int, input().split())
A_array = list(map(int, input().split()))
# print(A_array)
match_num_array = [2, 5, 5, 4, 5, 6, 3, 7, 6]
can_use_num_tmp = [-1, -1, -1, -1, -1, -1]
for A in A_array:
    can_use_num_tmp[match_num_array[A - 1] - 2] = max(
        A, can_use_num_tmp[match_num_array[A - 1] - 2])
can_use_num_tmp.sort()

can_use_num = []
can_use_num_match = []

for tmp in can_use_num_tmp[::-1]:
    if tmp == -1:
        break
    can_use_num.append(tmp)
    can_use_num_match.append(match_num_array[tmp - 1])

# print(can_use_num, can_use_num_match)
ans = []

ans.append([0] * len(can_use_num))

for n in range(1, N + 1):
    ans_tmp = -1

    for i, match_num in enumerate(can_use_num_match):
        if n - match_num >= 0 and ans[n - match_num] != -1:
            candidate = copy.deepcopy(ans[n - match_num])
            candidate[i] += 1
            ans_tmp = candidate if ans_tmp == -1 else compare_num(
                ans_tmp, candidate)
    ans.append(ans_tmp)

ans_str = ""
for ans_num, ans_count in zip(can_use_num, ans[N]):
    ans_str += (str(ans_num) * ans_count)

print(ans_str)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)
b = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [0 for _ in range(n + 1)]
INF = 10 ** 9
for i in range(1, n + 1):
    c = [dp[i - b[aj]] for aj in a if i >= b[aj]]
    if len(c) > 0:
        dp[i] = max(c) + 1
    else:
        dp[i] = -INF

x = n
i = 0
ans = ''
while(True):
    for aj in a:
        if x - b[aj] >= 0 and dp[x - b[aj]] == dp[n] - i - 1:
            i += 1
            x -= b[aj]
            ans += str(aj)
            break
    if i == dp[n]:
        break
print(ans)

Submission status: Accepted

Solution code:
# N = int(input())
# A = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]
# MOD = 10 ** 9 + 7
# メモ化再起
from functools import lru_cache
import sys

sys.setrecursionlimit(100000000)

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



@lru_cache(maxsize=1000000)
def f(n):
    maxval = -float('inf')
    for a in A:
        tmp = n - match[a]
        if tmp == 0:
            maxval = max(maxval, a)
        elif tmp > 0:
            # maxval = max(maxval, f2(f(n - match[a]) * 10 + a))
            maxval = max(maxval, f(n - match[a]) * 10 + a)
    return maxval

@lru_cache(maxsize=1000000)
def f2(n):
    if n < 0:
        return 0
    n = list(str(n))
    n.sort(reverse=True)
    return int("".join(n))

ans = f(N)
print(f2(ans))

Submission status: Accepted

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

import sys

input = sys.stdin.readline

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

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

    # N 本で作れる桁の数
    dp = [-1 for _ in range(N+1)]
    dp[0] = 0
    for i in range(N+1):
        for a in A:
            if i < MATCH_NUM[a]:
                continue
            dp[i] = max(dp[i], dp[i-MATCH_NUM[a]] + 1)

    max_digit_num = dp[N]

    res = ''
    for _ in range(max_digit_num):
        m = -1
        for a in A:
            if N < MATCH_NUM[a]:
                continue
            if dp[N-MATCH_NUM[a]] == dp[N]-1:
                if a > m:
                    m = a
        res += str(m)
        N -= MATCH_NUM[m]
    print(res)
main()

Submission status: Accepted

Solution code:
import sys
from operator import itemgetter
from collections import deque
input = sys.stdin.readline

N, M = map(int, input().split())
A = list(map(int, input().split()))
B = [i for i in range(1, 10)]
C = [2, 5, 5, 4, 5, 6, 3, 7, 6]
inf = float('inf')
costs = {m: C[m-1] for m in A}
dp = deque([0])

for i in range(1, N+1):
        dp.append(max([dp[i-c] if i - c >= 0 else -inf for c in costs.values()])+1)

digits = list(costs.keys())
digits.sort(reverse=True)
result = deque()
num = N
for _ in range(dp[N]):
        for i in digits:
                if num >= costs[i] and dp[num-costs[i]] != -inf and dp[num-costs[i]] == dp[num]-1:
                        result.append(str(i))
                        num -= costs[i]
                        break

print(''.join(result))

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]))

#print(list(zip([[2, 5, 5, 4, 5, 6, 3, 7, 6][a-1] for a in A], A)))
#print(cost)


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-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:
import itertools

N,M = map(int,input().split())
A = [int(x) for x in input().split()]
L = [100,2,5,5,4,5,6,3,7,6]

len_set = set(L[x] for x in A)

INF = 10**18
can_make = [-INF]*(N+1)
can_make[0] = 0 # 何桁で作れるか

for n in range(1,N+1):
  for x in len_set:
    if n-x >= 0 and can_make[n] < can_make[n-x] + 1:
        can_make[n] = can_make[n-x] + 1

answer = []

A.sort(reverse = True)
# なるべく大きいのを使いたい。作れる桁数が減らないようにする。
for a in A:
  x = L[a]
  while N-x >= 0 and can_make[N] == can_make[N-x]+1:
    answer.append(str(a))
    N -= x
      
answer = ''.join(answer)
print(answer)

Submission status: Accepted

Solution code:
def sub(N, M, As):

    d_cost = {
            "1": 2,
            "2": 5,
            "3": 5,
            "4": 4,
            "5": 5,
            "6": 6,
            "7": 3,
            "8": 7,
            "9": 6,
            }
    
    NINF = -10**6
    dp_table = [NINF for _ in range(N+1)]
    dp_table[0] = 0
    for i in range(N):
        if dp_table[i] < 0:
            continue
        for a in As:
            cost = i + d_cost[a]
            if cost <= N:
                dp_table[cost] = max(dp_table[cost], dp_table[i] + 1)

    Lmax = dp_table[N]

    life = N
    buf = []
    for i in range(Lmax):
        oks = []
        for a in As:
            if life - d_cost[a] < 0:
                continue
            if dp_table[life - d_cost[a]] == dp_table[life] - 1:
                oks.append(a)
        # oks = [a for a in As if dp_table[life - d_cost[a]] == dp_table[life] - 1 and life - d_cost[a] >= 0]
        a_selected = max(oks)
        buf.append(a_selected)
        life = life - d_cost[a_selected]
    print("".join(buf))
            

if __name__ == "__main__":
    N, M = [int(e) for e in input().split()]
    As = [e for e in input().split()]
    sub(N, M, As)

Submission status: Accepted

Solution code:
n, m = list(map(int, input().split()))
s = {e for e in list(map(int, input().split()))}
d = {1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6}
dp = [-1 for i in range(n+1)]
dp[0] = 0
for i in range(1, n+1):
  for e in s:
    if i-d[e]>=0 and dp[i-d[e]]>=0:
      dp[i] = max(dp[i], dp[i-d[e]]+1)

ans = ""
j = n
for i in range(dp[n]):
  for e in sorted(s, reverse=True):
    if j-d[e]>=0 and dp[j]-1==dp[j-d[e]]:
      ans += str(e)
      j -= d[e]
      break
print(ans)

Submission status: Accepted

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

for i in range(2,n+1):
    for j in range(0,m):
        if i-cost[a[j]] <0:
            continue
        if dp[i-cost[a[j]]] == -1:
            continue
        else:
            dp[i] = max(dp[i],dp[i-cost[a[j]]]+1)

ans = list()
read = n
a.sort()
a.reverse()

while read > 0:
    for i in range(0,m):
        if read < cost[a[i]]:
            continue
        if dp[read-cost[a[i]]] == dp[read]-1:
            ans.append(str(a[i]))
            read -= cost[a[i]]
            break
    
print("".join(ans))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
A = tuple([int(s) for s in input().split()])
m = (0, 2, 5, 5, 4, 5, 6, 3, 7, 6)
dp = [None for _ in range(N+1)]
dp[0] = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
for n in range(2, N+1):
    for a in A:
        dn = m[a]
        if n - dn < 0 or dp[n - dn] is None:
            continue
        state = dp[n - dn][:]
        state[0] += 1
        state[10 - a] += 1
        if dp[n] is None:
            dp[n] = state
        else:
            dp[n] = max(dp[n], state)
for i in range(1, 10):
    print(str(10-i) * dp[N][i], end="")
print("")

Submission status: Accepted

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

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

for i in range(N):
    tmp = []
    for A in Alist:
        if (i+1 - dic[A-1]) < 0:
            tmp.append(-1)
        else:
            if dp[i+1 - dic[A-1]] != -1:
                tmp.append(dp[i+1 - dic[A-1]] + 1)
            else:
                tmp.append(-1)
        dp[i+1] = max(tmp)


output = []
output_dic = []
for i in range(dp[N]):
    for A in Alist[::-1]:
        if N - sum(output_dic) - dic[A-1] >= 0:
            if dp[N - sum(output_dic) - dic[A-1]] == (dp[N - sum(output_dic)] - 1):
                output.append(A)
                output_dic.append(dic[A-1])
                break

out = ''
for i in range(len(output)):
    out += str(output[i])

print(out)

Submission status: Accepted

Solution code:
import collections
N, M = [int(_) for _ in input().split()]
A = sorted([int(_) for _ in input().split()])
n_m = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
m_n = {}
for a in A:
    m_n[n_m[a]] = a
dp = collections.defaultdict(lambda: -float('inf'))
dp[0] = 0
for i in range(1, N + 1):
    dp[i] = max(dp[i - m] + 1 for m, n in m_n.items())
ans = ''
ms = sorted(m_n.keys(), key=lambda _: m_n[_], reverse=True)
d = dp[N]
while N:
    for m in ms:
        if dp[N - m] == dp[N] - 1:
            N -= m
            ans += str(m_n[m])
            break
print(ans)

Submission status: Accepted

Solution code:
if __name__ == "__main__":
  l = [0,2,5,5,4,5,6,3,7,6]
  n,m = list(map(int,input().split()))
  a = list(map(int,input().split()))
  res = ''
  INF = 10**4
  
  dp = [[0,0] for i in range(n+1)]
  for i in range(n):
    for j in range(m):
      if dp[i][1] + l[a[j]] != i + l[a[j]] or i + l[a[j]] > n:
        pass
      else:
        dp[i + l[a[j]]][0] = max(dp[i][0] + 1, dp[i + l[a[j]]][0])
        dp[i + l[a[j]]][1] = dp[i][1] + l[a[j]]
  for i in range(1,n): dp[i][0] = -INF if dp[i][0] == 0 else dp[i][0]
  
  a.sort(reverse = True)
  i = n
  while i > 0:
    for j in range(m):
      if i >= l[a[j]] and dp[i - l[a[j]]][0] + 1 == dp[i][0]:
        res += str(a[j])
        i -= l[a[j]]
        break
      else:
        pass
  print(res)

Submission status: Accepted

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

comall = [-1,2,5,5,4,5,6,3,7,6]
com = [ (i,comall[i]) for i in li ]
com.sort( key=lambda x:-x[0])

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

for i in range(N+1):
  for j,c in com:
    if (c==-1):
      continue
    if ( i-c < 0 ):
      continue
    if ( dp[i-c] == -1 ):
      continue
    dp[i] = max( dp[i] , dp[i-c] + 1 )

match = N
keta = dp[N]
st = ""


for i in range( 10000 ):
  for j,c in com:
    if (match-c<0):
      continue
    if (keta-1==dp[match-c]):
      keta-=1
      match-=c
      st+=str(j)
      break
  if (match==0):
    break
print ( st )

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:
n, _ = map(int, input().split())
L = 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 L:
        if i+weight[a] < n+1:
            dp[i+weight[a]] = max(dp[i+weight[a]], dp[i]*10+a)

print(dp[n])

Submission status: Accepted

Solution code:
## DP問題
 
N,M = map(int,input().split())
As = list(map(str,input().split()))
match = {"1":2, "2":5, "3":5,
         "4":4, "5":5, "6":6,
         "7":3, "8":7, "9":6}
 
# test
# N, M = 10000, 9
# As = [str(i) for i in range(1,10)]
 
 
ws = {} #マッチの数に対しての、作れる数字の最大値を算出
for a in As:
    w = match[a] #数aに使うマッチの数
    try: 
        ws[str(w)] = max(a,ws[str(w)])
    except:
        ws[str(w)] = a
ks = list(map(int,ws.keys()))
ns = list(ws.values())
 
dp = ["0" for _ in range(N+1)]
for i in range(1,min(ks)):#最小
    dp[i] = "-1"
 
for i in range(N+1):
    # print(i)
    for a,k in zip(ns,ks):
        if i+k <= N:
            if dp[i] == "-1":
                dp[i+k] = str(max(int(dp[i]+a),int(dp[i+k])))
            elif dp[i] == "0":
                dp[i+k] = str(max(int(a),int(dp[i+k])))
            elif len(dp[i+k]) < len(dp[i])+1:
                    dp[i+k] = dp[i]+a
            elif len(dp[i+k]) == len(dp[i])+1:
                dp[i+k] = max(dp[i+k],dp[i]+a)
            # else:
            #     dp[i+k] = str(max(int(dp[i+k]),int(dp[i]+a)))

        else:
            continue
print(dp[N])

Submission status: Accepted

Solution code:
## DP問題
 
N,M = map(int,input().split())
As = list(map(str,input().split()))
match = {"1":2, "2":5, "3":5,
         "4":4, "5":5, "6":6,
         "7":3, "8":7, "9":6}
 
# test
# N, M = 10000, 9
# As = [str(i) for i in range(1,10)]
 
 
ws = {} #マッチの数に対しての、作れる数字の最大値を算出
for a in As:
    w = match[a] #数aに使うマッチの数
    try: 
        ws[str(w)] = max(a,ws[str(w)])
    except:
        ws[str(w)] = a
ks = list(map(int,ws.keys()))
ns = list(ws.values())
 
dp = ["0" for _ in range(N+1)]
for i in range(1,min(ks)):#最小
    dp[i] = "-1"
 
for i in range(N+1):
    # print(i)
    for a,k in zip(ns,ks):
        if i+k <= N:
            if dp[i] == "-1":
                dp[i+k] = str(max(int(dp[i]+a),int(dp[i+k])))
            elif dp[i] == "0":
                dp[i+k] = str(max(int(a),int(dp[i+k])))
            elif len(dp[i+k]) < len(dp[i])+1:
                    dp[i+k] = dp[i]+a
            elif len(dp[i+k]) == len(dp[i])+1:
                dp[i+k] = max(dp[i+k],dp[i]+a)
            else:
                dp[i+k] = str(max(int(dp[i+k]),int(dp[i]+a)))

        else:
            continue
print(dp[N])

Submission status: Accepted

Solution code:
N, M = [int(a) for a in input().split(" ")]
ctab = {"1":2,"2":5,"3":5,"4":4,"5":5,"6":6,"7":3,"8":7,"9":6}
A = sorted([(a, ctab[a]) for a in input().split(" ")], key=lambda t:t[0])
prev, curr = ([""]*(N+1), [""]*(N+1))

def maxs(s1, s2):
    return max(s1, s2, key=lambda s:len(s)) if len(s1)!=len(s2) else max(s1,s2)

char, cost = A[0]
for i in range(1, N+1):
    d, r = divmod(i, cost)
    prev[i] = char*d if r==0 else None
for char, cost in A[1:]:
    for i in range(1, N+1):
        if i-cost >= 0 and curr[i-cost] is not None:
            tmp = char+curr[i-cost]
            curr[i] = maxs(tmp, prev[i]) if prev[i] else tmp
        else:
            curr[i] = prev[i]
    curr, prev = prev, curr
print(prev[-1])

Submission status: Accepted

Solution code:
from functools import lru_cache

N, _ = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]

costs = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]  # (0), 1...9


@lru_cache(None)
def f(n):
    if n == 0:
        return 0
    values = [f(n-costs[a]) * 10 + a for a in A if n >= costs[a]]
    if len(values) > 0:
        return max(values)
    return -1


[f(i) for i in range(N)]
print(f(N))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


def solve(N: int, M: int, A: "List[int]"):
    A.sort(reverse=True)
    cs = [0, 2 , 5 , 5 , 4 , 5 , 6 , 3 , 7 , 6 ]
    dp = [-float('inf')] * (N + 1)

    dp[0] = 0
    for i in range(1, len(dp)):
        for a in A:
            c = cs[a]
            if 0 <= i - c:
                dp[i] = max(dp[i], dp[i-c] + 1)
    i = N
    ret = 0
    while 0 < dp[i]:
        for a in A:
            c = cs[a]
            if (0 <= i - c) and (dp[i] == (dp[i - c] + 1)):
                i -= c
                ret = 10 * ret + a
                break
    return ret


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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,m=map(int, input().split())
a=list(map(int, input().split()))
num=[2,5,5,4,5,6,3,7,6]
for i in range(9):
    if i+1 not in a:
        num[i]=0
dp=[[0]*10 for i in range(n+1)]
from copy import deepcopy
for i in range(2,n+1):
    for j in range(9):
        if num[j]>0 and num[j]<=i and dp[i][0]<=dp[i-num[j]][0]+1:
            if dp[i-num[j]][0]==0 and i-num[j]!=0:
                continue
            else:
                dp[i]=deepcopy(dp[i-num[j]])
                dp[i][0]+=1
                dp[i][j+1]+=1
ans=dp[n]
for i in range(9,0,-1):
    while ans[i]!=0:
        print(i,end='')
        ans[i]-=1
print()

Submission status: Accepted

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


def solve(N: int, M: int, A: "List[int]"):
    cost = [2, 5, 5, 4, 5, 6, 3, 7, 6]
    A.sort()
    D = {cost[i-1]: i for i in A}
    cost = sorted(D.keys())
    dp = [-1] * (N+1)
    dp[0] = 0
    for i in range(N+1):
        if dp[i] == -1:
            continue
        for c, d in D.items():
            if i + c <= N:
                dp[i+c] = max(dp[i+c], dp[i] * 10 + d)
    print(dp[N])
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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:
input_int = lambda:int(input())
input_ints = lambda:map(int,input().split())
input_ints_list = lambda:list(input_ints())
input_str = lambda:input()
input_strs = lambda:input().split()
input_lines = lambda n,f:[f() for _ in range(n)]

import functools,fractions
import numpy as np
gcd = lambda a:functools.reduce(fractions.gcd,a) # 最大公約数（リスト）
lcm_base = lambda a,b:(a*b)//fractions.gcd(a,b) # 最小公倍数(2値)
lcm = lambda a:functools.reduce(lcm_base,a,1) # 最小公倍数(リスト)

init_dp = lambda v,n:[v]*(n)

import math
# 四捨五入はround
ceil = lambda a:math.ceil(a) # 切り上げ
floor = lambda a:math.floor(a) # 切り捨て

def solution():
    N,M = input_ints()
    As = input_ints_list()
    w = [0,2,5,5,4,5,6,3,7,6]

    dp = init_dp(-1,N+1)
    dp[0] = 0
    for i in range(N+1):
        for v in As:
            if i+w[v] < N+1:
                dp[i+w[v]] = max(dp[i+w[v]],dp[i]*10+v)
    print(dp[N])
    
if __name__ == '__main__':
    solution()

Submission status: Accepted

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

f = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
A = sorted(A, reverse=True)

dp = [float('-inf')] * (N + 1)
dp[0] = 0
for i in range(N + 1):
    for a in A:
        if i - f[a] >= 0:
            dp[i] = max(dp[i], dp[i - f[a]] + 1)

ans = ''
num, digit = N, dp[N]
while num > 0:
    for a in A:
        i = num - f[a]
        if i >= 0 and dp[i] == digit - 1:
            ans += str(a)
            num -= f[a]
            digit -= 1
            break
print(ans)

Submission status: Accepted

Solution code:
input_int = lambda:int(input())
input_ints = lambda:map(int,input().split())
input_ints_list = lambda:list(input_ints())
input_str = lambda:input()
input_strs = lambda:input().split()
input_lines = lambda n,f:[f() for _ in range(n)]

import functools,fractions
import numpy as np
gcd = lambda a:functools.reduce(fractions.gcd,a) # 最大公約数（リスト）
lcm_base = lambda a,b:(a*b)//fractions.gcd(a,b) # 最小公倍数(2値)
lcm = lambda a:functools.reduce(lcm_base,a,1) # 最小公倍数(リスト)

init_dp = lambda v,n:[v]*(n+1)

import math
# 四捨五入はround
ceil = lambda a:math.ceil(a) # 切り上げ
floor = lambda a:math.floor(a) # 切り捨て

def solution():
    N,M = input_ints()
    As = input_ints_list()
    w = [0,2,5,5,4,5,6,3,7,6]

    dp = init_dp(-1,N)
    dp[0] = 0
    for i in range(N+1):
        for v in As:
            if i+w[v] < N+1:
                dp[i+w[v]] = max(dp[i+w[v]],dp[i]*10+v)
    print(dp[N])




if __name__ == '__main__':
    solution()

Submission status: Accepted

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

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


dp = [-1*inf]*(N+1)
dp[0] = 0
for i in range(1,N+1):
  dp_new = 0
  for j in A:
    if i - number[j] >= 0:
      if dp[i-number[j]] +1 > dp_new:
        dp[i] = dp[i-number[j]] +1
        dp_new = dp[i]

A.sort(reverse=True)
ans = ""
while N > 0:
  for j in A:
    if N - number[j] >= 0:
      if dp[N] == dp[N-number[j]] + 1:
        ans += str(j)
        N -= number[j]
        break

print(int(ans))

Submission status: Accepted

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

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

dp=[ None for i in range(N+1) ] 
dp[0]=""


for i in range(N):
	if dp[i] is not None:
		for a in A:
			match_cnt=match[a]
			if 0<=i+match_cnt<=N:
				if dp[i+match_cnt] is None:
					dp[i+match_cnt]=dp[i]+str(a)
				else:
					if len(dp[i+match_cnt]) < len( dp[i]+str(a) ):
						dp[i+match_cnt]=dp[i]+str(a)
					else:
						dp[i+match_cnt]=max( dp[i+match_cnt], dp[i]+str(a) )
									

print dp[N]

Submission status: Accepted

Solution code:
T=[(1,2),(2,5),(3,5),(4,4),(5,5),(6,6),(7,3),(8,7),(9,6)]
 
N,M=map(int, raw_input().split())
A=map(int, raw_input().split())
 
 
P=[]
for i in A:
	P.append(T[i-1])
 
 
dp=[ None for i in range(N+1) ]
dp[0]=""
 
 
for i in range(N):
	#print "i :::: ",i,dp
	if dp[i] is not None:
		for num, match in P:
			if i+match<=N:
 
				if dp[i+match] is None:
					dp[i+match]=dp[i]+str(num)
				else:
					l1=len(dp[i+match])
					l2=len(dp[i]+str(num))
					if l1>l2:
						pass
					elif l1<l2:
						dp[i+match]=dp[i]+str(num)
					else:
						dp[i+match]=max( dp[i+match] , dp[i]+str(num) )
 
 
print dp[N]

Submission status: Accepted

Solution code:
nm = input().split()
n = int(nm[0])
m = int(nm[1])
alist = set([int(i) for i in input().split()])

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


def print_count(num_count_list):
    to_print = ''
    num_count_list.sort(reverse=True)
    for num, count in num_count_list:
        to_print += str(num) * count
    print(to_print)


def safe_max(nset):
    try:
        return max(nset)
    except:
        return -1


if piece_num[2] & alist:
    max_2 = max(piece_num[2] & alist)
    if n & 1 == 0:
        print(str(max_2) * (n // 2))
    else:
        if piece_num[3] & alist:
            print_count([(max(piece_num[3] & alist), 1), (max_2, max(0, n // 2 - 1))])
        elif piece_num[5] & alist:
            print_count([(max(piece_num[5] & alist), 1), (max_2, max(0, n // 2 - 2))])
        elif piece_num[7] & alist:
            print_count([(max(piece_num[7] & alist), 1), (max_2, max(0, n // 2 - 3))])

elif piece_num[3] & alist:
    max_3 = max(piece_num[3] & alist)
    if n % 3 == 0:
        print(str(max_3) * (n // 3))
    elif n % 3 == 1:
        if piece_num[4] & alist:
            print_count([(max(piece_num[4] & alist), 1), (max_3, max(0, n // 3 - 1))])
        elif piece_num[7] & alist:
            print_count([(max(piece_num[7] & alist), 1), (max_3, max(0, n // 3 - 2))])
        elif piece_num[5] & alist:
            print_count([(max(piece_num[5] & alist), 2), (max_3, max(0, n // 3 - 3))])
    elif n % 3 == 2:
        if piece_num[5] & alist:
            max_5 = max(piece_num[5] & alist)
            print_count([(max_5, 1), (max_3, max(0, n // 3 - 1))])
        elif piece_num[4] & alist:
            max_4 = max(piece_num[4] & alist)
            print_count([(max_4, 2), (max_3, max(0, n // 3 - 2))])
        else:
            print_count([(max(piece_num[7] & alist), 2), (max_3, max(0, n // 3 - 4))])

elif piece_num[4] & alist:
    max_4 = max(piece_num[4] & alist)
    if n % 4 == 0:
        print(str(max_4) * (n // 4))
    elif n % 4 == 1:
        if piece_num[5] & alist:
            print_count([(max(piece_num[5] & alist), 1), (max_4, max(0, n // 4 - 1))])
        elif (piece_num[6] & alist) and (piece_num[7] & alist):
            max_6 = max(piece_num[6] & alist)
            max_7 = max(piece_num[7] & alist)
            print_count([(max_6, 1), (max_7, 1), (max_4, max(0, n // 4 - 3))])
        elif piece_num[7] & alist:
            max_7 = max(piece_num[7] & alist)
            print_count([(max_7, 3), (max_4, max(0, n // 4 - 5))])
    elif n % 4 == 2:
        if (piece_num[5] & alist) and (piece_num[6] & alist):
            max_5 = max(piece_num[5] & alist)
            max_6 = max(piece_num[6] & alist)
            if max_5 < max_6:
                print_count([(max_6, 1), (max_4, max(0, n // 4 - 1))])
            else:
                print_count([(max_5, 2), (max_4, max(0, n // 4 - 2))])
        elif piece_num[5] & alist:
            max_5 = max(piece_num[5] & alist)
            print_count([(max_5, 2), (max_4, max(0, n // 4 - 2))])
        elif piece_num[6] & alist:
            max_6 = max(piece_num[6] & alist)
            print_count([(max_6, 1), (max_4, max(0, n // 4 - 1))])
        else:
            max_7 = max(piece_num[7] & alist)
            print_count([(max_7, 2), (max_4, max(0, n // 4 - 3))])
    elif n % 4 == 3:
        max_5 = safe_max(piece_num[5] & alist)
        max_6 = safe_max(piece_num[6] & alist)
        max_7 = safe_max(piece_num[7] & alist)
        if max_7 == max(max_5, max_6, max_7):
            print_count([(max_7, 1), (max_4, max(0, n // 4 - 1))])
        elif max_5 == max(max_5, max_6, max_7):
            print_count([(max_5, 3), (max_4, max(0, n // 4 - 3))])
        else:
            if piece_num[5] & alist:
                print_count([(max_6, 1), (max_5, 1), (max_4, max(0, n // 4 - 2))])
            else:
                print_count([(max_7, 1), (max_4, max(0, n // 4 - 1))])

elif piece_num[5] & alist:
    max_5 = max(piece_num[5] & alist)
    if n % 5 == 0:
        print(str(max_5) * (n // 5))
    elif n % 5 == 1:
        if piece_num[6] & alist:
            max_6 = safe_max(piece_num[6] & alist)
            print_count([(max_6, 1), (max_5, max(0, n // 5 - 1))])
        else:
            max_7 = safe_max(piece_num[7] & alist)
            print_count([(max_7, 3), (max_5, max(0, n // 5 - 4))])
    elif n % 5 == 2:
        max_6 = safe_max(piece_num[6] & alist)
        max_7 = safe_max(piece_num[7] & alist)
        if max_7 == max(max_6, max_7):
            print_count([(max_7, 1), (max_5, max(0, n // 5 - 1))])
        else:
            print_count([(max_6, 2), (max_5, max(0, n // 5 - 2))])
    elif n % 5 == 3:
        max_6 = safe_max(piece_num[6] & alist)
        max_7 = safe_max(piece_num[7] & alist)
        if max_7 == max(max_6, max_7):
            if piece_num[6] & alist:
                print_count([(max_7, 1), (max_6, 1), (max_5, max(0, n // 5 - 2))])
            else:
                print_count([(max_7, 4), (max_5, max(0, n // 5 - 5))])
        else:
            print_count([(max_6, 3), (max_5, max(0, n // 5 - 3))])
    elif n % 5 == 4:
        max_6 = safe_max(piece_num[6] & alist)
        max_7 = safe_max(piece_num[7] & alist)
        if max_7 == max(max_6, max_7):
            print_count([(max_7, 2), (max_5, max(0, n // 5 - 2))])
        else:
            print_count([(max_6, 4), (max_5, max(0, n // 5 - 4))])

elif piece_num[6] & alist:
    max_6 = max(piece_num[6] & alist)
    if n % 6 == 0:
        print(str(max_6) * (n // 6))
    else:
        count_7 = n % 6
        max_7 = max(piece_num[7] & alist)
        print_count([(max_7, count_7), (max_6, max(0, n // 6 - count_7))])

else:
    max_7 = max(piece_num[7] & alist)
    print(str(max_7) * (n // 7))