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: Runtime Error

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

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

B = {}
for a in A:
    ind = seg[a]
    if not ind in B.keys():
        B[ind] = a
    else:
        if B[ind] < a:
            B[ind] = a

I = sorted(list(B.keys()))
#print(I)
def search(ind, remain, ret):
    if ind >= len(I):
        return False, ret
    #print(I[ind], remain, ret)
    a = I[ind]
    p = remain // a
    r = remain % a 
    if p == 0:
        return False, ret
    if r == 0:
        ret.append((a, p))
        return True, ret
    for q in range(p-1, -1, -1):
        r += a
        oldr = ret[:]
        ok, newr = search(ind+1, r, oldr)
        if ok:
            newr.append((a, q))
            if ind == 0:
                Ap.append(newr)
                continue
            return True, newr
    if ind == 0:
        return Ap
    return False, ret

Ap = []
Ls = search(0, N, [])
#print(Ls)
anss = []
for L in Ls:
    Q = []
    for k, v in L:
        Q.extend([B[k]]*v)
    Q.sort(reverse=True)
    num = int(''.join([str(q) for q in Q]))
    anss.append(num)

print(max(anss))

Submission status: Runtime Error

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

import sys
import math
import bisect
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
mod = 10**9 + 7

M = [0,2,5,5,4,5,6,3,7,6]
n,m = map(int,input().split())
a = list(map(int,input().split()))
A = [[i,M[i]] for i in a]
A.sort(key = itemgetter(1))

#dp[i] := ちょうどマッチi本を使ってできる最大桁数
dp = [-float('inf')]*(n+1)
dp[0] = 0
for i in range(n):
    for j,k in A:
        if i + k < n+1:
            if dp[i] < 0:
                continue
            dp[i+k] = dp[i] + 1
A.sort(key = itemgetter(0),reverse = True)
ans = ''
k = n
while 1:
    for i,j in A:
        if dp[k-j] == dp[k]-1:
            ans += str(i)
            k -= j
            break
    else:
        break
print(ans)

Submission status: Runtime Error

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

Aset = {}
for a in A:
    c = cost[a]
    Aset[c] = max(Aset[c], a) if c in Aset else a
A = sorted([v for k,v in Aset.items()])

dp = [None]*(N+1)
dp[0] = (0,[0]*len(A))

for ia, a in enumerate(A):
    c = cost[a]
    for i in range(c, N+1):
        t = dp[i-c]
        if t and (dp[i]==None or t[0]+1>=dp[i][0]):
            dp[i] = (t[0]+1, t[1].copy())
            dp[i][1][ia] += 1
      	
l=[]
for i in range(len(A)):
    l += [A[len(A)-1-i]]*dp[N][1][len(A)-1-i]

print(*l, sep='')

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
*A, = map(int,input().split())
B = sorted((([2,5,5,4,5,6,3,7,6][a-1],a) for a in A),key = lambda x:(x[0],-x[1]))
i = 1
while i<len(B):
    if B[i][0]==B[i-1][0]:
        B.pop(i)
    else:
        i+=1
i = [0]*(len(B)-1)
ans = []
while i[-1]<B[0][0]:
    tmp = N - sum(j*b[0] for j,b in zip(i,B[1:]))
    if tmp>=0 and tmp%B[0][0] == 0:
        num = ""
        for k,n in sorted(zip([b for _,b in B],[tmp//B[0][0]]+i),key = lambda x:-x[0]):
            num += str(k)*n
        ans.append(int(num))
    i[0]+=1
    for j in range(len(i)-1):
        if i[j]==B[0][0]:
            i[j+1]+=1
            i[j]=0
print(max(ans))

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
*A, = map(int,input().split())
B = sorted((([2,5,5,4,5,6,3,7,6][a-1],a) for a in A),key = lambda x:(x[0],-x[1]))
i = 1
while i<len(B):
    if B[i][0]==B[i-1][0]:
        B.pop(i)
    else:
        i+=1
i = [0]*(len(B)-1)
ans_tmp = (0,[])
while i[-1]<B[0][0]:
    tmp = N - sum(j*b[0] for j,b in zip(i,B[1:]))
    if tmp%B[0][0] == 0:
        tmp2 = tmp//B[0][0] + sum(j for j in i)
        if ans_tmp[0] < tmp2:
            ans_tmp = (tmp2,[tmp//B[0][0]]+i)
    i[0]+=1
    for j in range(len(i)-1):
        if i[j]==B[0][0]:
            i[j+1]+=1
            i[j]=0
ans = ""
for i,n in sorted(zip([b for _,b in B],ans_tmp[1]),key=lambda x:-x[0]):
    ans += str(i)*n
print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

def solve():
  N, M = LI()
  num_list = LI()
  mapping = [-1,2,5,5,4,5,6,3,7,6]

  a_list = [mapping[num] for num in num_list]
  
  rmap = {}
  for a, num in zip(a_list, num_list):
    if a not in rmap:
      rmap[a] = num
    else:
      if rmap[a] < num:
        rmap[a] = num

  # もっとも効率のいい数字を探す
  eff_num = -1
  eff_a = 10**9
  for a, num in zip(a_list, num_list):
    if a < eff_a or (a == eff_a and num >= eff_num):
      eff_a = a
      eff_num = num

  def search(r, cur, res):
    for a in list(set(a_list)):
      next_cur = [c for c in cur]
      next_cur.append(a)
      if a == r:
        res.append(next_cur)
        return res
      elif a > r:
        return res
      else:
        search(r-a, next_cur, res)
    return res

  k = N // eff_a # 効率のいい数字が作れる数の最大値
  rest =  N - k*eff_a
  if rest == 0:
    print(''.join([eff_num]*k))
    return

  # 答えが出る+10ぐらいまで探索
  first_ans_i = None
  ans_str_cand = []
  for i in range(1, k):
    rest_a = rest + i* eff_a # あまりの数字
    candidates = search(rest_a, [], [])
    if len(candidates) == 0:
      continue
    ans_cand = None
    ans_cand_len = -1
    ans_cand_mx = -1
    for cand in candidates:
      cand_num = [rmap[c] for c in cand]
      cand_mx = max(cand_num)
      if (ans_cand_len < len(cand)) or (ans_cand_len == len(cand) and ans_cand_mx <= cand_mx):
          ans_cand = cand
          ans_cand_len = len(cand)
          ans_cand_mx = cand_mx
    eff = [eff_num]*(k-i)
    num_cand = [rmap[c] for c in ans_cand]
    num_cand.extend(eff)
    num_cand = sorted(num_cand, reverse=True)
    ans_str_cand.append(''.join([str(n) for n in num_cand]))
    if first_ans_i is None:
      first_ans_i = i
    if i >= first_ans_i + 10:
      break
  print(max(ans_str_cand))
solve()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

def solve():
  N, M = LI()
  num_list = LI()
  mapping = [-1,2,5,5,4,5,6,3,7,6]

  a_list = [mapping[num] for num in num_list]
  
  rmap = {}
  for a, num in zip(a_list, num_list):
    if a not in rmap:
      rmap[a] = num
    else:
      if rmap[a] < num:
        rmap[a] = num

  # もっとも効率のいい数字を探す
  eff_num = -1
  eff_a = 10**9
  for a, num in zip(a_list, num_list):
    if a < eff_a or (a == eff_a and num >= eff_num):
      eff_a = a
      eff_num = num

  def search(r, cur, res):
    for a in list(set(a_list)):
      next_cur = [c for c in cur]
      next_cur.append(a)
      if a == r:
        res.append(next_cur)
        return res
      elif a > r:
        return res
      else:
        search(r-a, next_cur, res)
    return res

  k = N // eff_a # 効率のいい数字が作れる数の最大値
  rest =  N - k*eff_a
  if rest == 0:
    print(''.join([eff_num]*k))
    return

  # 答えが出る+10ぐらいまで探索
  first_ans_i = None
  ans_str_cand = []
  for i in range(1, k):
    rest_a = rest + i* eff_a # あまりの数字
    candidates = search(rest_a, [], [])
    if len(candidates) == 0:
      continue
    ans_cand = None
    ans_cand_len = -1
    ans_cand_mx = -1
    for cand in candidates:
      cand_num = [rmap[c] for c in cand]
      cand_mx = max(cand_num)
      if (ans_cand_len < len(cand)) or (ans_cand_len == len(cand) and ans_cand_mx <= cand_mx):
          ans_cand = cand
          ans_cand_len = len(cand)
          ans_cand_mx = cand_mx
    eff = [eff_num]*(k-i)
    num_cand = [rmap[c] for c in ans_cand]
    num_cand.extend(eff)
    num_cand = sorted(num_cand, reverse=True)
    ans_str_cand.append(''.join([str(n) for n in num_cand]))
    if first_ans_i is None:
      first_ans_i = i
    if i >= first_ans_i + 10:
      break

    print(max(ans_str_cand))
solve()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

def solve():
  N, M = LI()
  num_list = LI()
  mapping = [-1,2,5,5,4,5,6,3,7,6]

  a_list = [mapping[num] for num in num_list]
  
  rmap = {}
  for a, num in zip(a_list, num_list):
    if a not in rmap:
      rmap[a] = num
    else:
      if rmap[a] < num:
        rmap[a] = num

  # もっとも効率のいい数字を探す
  eff_num = -1
  eff_a = 10**9
  for a, num in zip(a_list, num_list):
    if a < eff_a or (a == eff_a and num >= eff_num):
      eff_a = a
      eff_num = num

  def search(r, cur, res):
    for a in list(set(a_list)):
      next_cur = [c for c in cur]
      next_cur.append(a)
      if a == r:
        res.append(next_cur)
        return res
      elif a > r:
        return res
      else:
        search(r-a, next_cur, res)
    return res

  k = N // eff_a # 効率のいい数字が作れる数の最大値
  rest =  N - k*eff_a
  if rest == 0:
    print(''.join([eff_num]*k))
    return

  # 答えが出るまで探索
  for i in range(1, k):
    rest_a = rest + i* eff_a # あまりの数字
    candidates = search(rest_a, [], [])
    if len(candidates) == 0:
      continue
    ans_cand = None
    ans_cand_len = -1
    ans_cand_mx = -1
    for cand in candidates:
      cand_num = [rmap[c] for c in cand]
      cand_mx = max(cand_num)
      if (ans_cand_len < len(cand)) or (ans_cand_len == len(cand) and ans_cand_mx <= cand_mx):
          ans_cand = cand
          ans_cand_len = len(cand)
          ans_cand_mx = cand_mx
    eff = [eff_num]*(k-i)
    num_cand = [rmap[c] for c in ans_cand]
    num_cand.extend(eff)
    num_cand = sorted(num_cand, reverse=True)
    print(''.join([str(n) for n in num_cand]))
    break

solve()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

def solve():
  N, M = LI()
  num_list = LI()
  mapping = [-1,2,5,5,4,5,6,3,7,6]

  a_list = [mapping[num] for num in num_list]
  
  rmap = {}
  for a, num in zip(a_list, num_list):
    if a not in rmap:
      rmap[a] = num
    else:
      if rmap[a] < num:
        rmap[a] = num

  # もっとも効率のいい数字を探す
  eff_num = -1
  eff_a = 10**9
  for a, num in zip(a_list, num_list):
    if a < eff_a or (a == eff_a and num >= eff_num):
      eff_a = a
      eff_num = num

  def search(r, cur, res):
    for a in list(set(a_list)):
      next_cur = [c for c in cur]
      next_cur.append(a)
      if a == r:
        res.append(next_cur)
        return res
      elif a > r:
        return res
      else:
        search(r-a, next_cur, res)
    return res

  k = N // eff_a # 効率のいい数字が作れる数の最大値
  rest =  N - k*eff_a
  if rest == 0:
    print(''.join([eff_num]*k))
    return

  # 答えが出るまで探索
  for i in range(1, k):
    rest_a = rest + i* eff_a # あまりの数字
    candidates = search(rest_a, [], [])
    if len(candidates) == 0:
      continue
    ans_cand = None
    ans_cand_len = -1
    ans_cand_mx = -1
    for cand in candidates:
      cand_num = [rmap[c] for c in cand]
      cand_mx = max(cand_num)
      if (ans_cand_len < len(cand)) or (ans_cand_len == len(cand) and ans_cand_mx <= cand_mx):
          ans_cand = cand
          ans_cand_len = len(cand)
          ans_cand_mx = cand_mx
    eff = [eff_num]*(k-i)
    num_cand = [rmap[c] for c in ans_cand]
    num_cand.extend(eff)
    num_cand = sorted(num_cand, reverse=True)
    print(''.join([str(n) for n in num_cand]))
    break
  print(num_list, a_list, rmap)
  print(eff_a, eff_num)
  print(k)

solve()

Submission status: Runtime Error

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

k = [0] * (M + 1)
for i in range(N):
    a = [int(x) for x in input().split()]
    del a[0]
    for j in a:
        k[j] += 1
print(k.count(N))

Submission status: Runtime Error

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

n,m = map(int,input().split())
a = list(map(int,input().split()))
a.sort(reverse=True)
match = []
for num in a:
    match.append(all_match[num-1])

dp = [-10**7 for i in range(n+1)] #桁数
dp[0] = 0

for i in range(1,n+1):
    possible = []
    for honsu in match:
        if i >= honsu:
            possible.append(dp[i-honsu] + 1)
    if len(possible)>0:
        dp[i] = max(possible)

length = dp[n]
ans = 0
now = n
for i in range(length):
    for j in range(m):
        if dp[now-match[j]] == dp[now]-1:
            ans += a[j]*10**(length-i-1)
            now -= match[j]
            break

print(ans)

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)

inf = 10 ** 4


def larger(x, y):
    lx, ly = len(x), len(y)
    if lx > ly:
        return x
    elif lx < ly:
        return y
    else:
        x.sort(reverse=True)
        y.sort(reverse=True)
        for xx, yy in zip(x, y):
            if xx > yy:
                return x
            elif xx < yy:
                return y
        return x


def dfs(rest):
    if memo[rest] is not None:
        return memo[rest]

    res = []
    for use, number in d.items():
        if dp[rest - use] == dp[rest] - 1:
            res = larger(res, [number] + dfs(rest - use))

    memo[rest] = res
    return res


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

needs = [inf, 2, 5, 5, 4, 5, 6, 3, 7, 6]
# needs[i] : 数字iを作るのに必要なマッチの本数

for i in range(1, 10):
    if i not in a:
        needs[i] = inf

d = {needs[i]: i for i in range(1, 10) if needs[i] != inf}
# d[本数] = その本数で作れる最大の数値

dp = [-inf] * (n + 1)
dp[0] = 0
# dp[j] : j本から構成できる桁数の最大値

for j in range(2, n + 1):
    for use, number in d.items():
        if j - use >= 0:
            dp[j] = max(dp[j], dp[j - use] + 1)

# print(dp)

memo = [None] * (n + 1)

ans = dfs(n)
ans.sort(reverse=True)
print(*ans, sep='')

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)

inf = float('inf')


def larger(x, y):
    lx, ly = len(x), len(y)
    if lx > ly:
        return x
    elif lx < ly:
        return y
    else:
        x.sort(reverse=True)
        y.sort(reverse=True)
        for xx, yy in zip(x, y):
            if xx > yy:
                return x
            elif xx < yy:
                return y
        return x


def dfs(rest):
    res = []
    for use, number in d.items():
        if dp[rest - use] == dp[rest] - 1:
            res = larger(res, [number] + dfs(rest - use))
    return res


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

needs = [inf, 2, 5, 5, 4, 5, 6, 3, 7, 6]
# needs[i] : 数字iを作るのに必要なマッチの本数

for i in range(1, 10):
    if i not in a:
        needs[i] = inf

d = {needs[i]: i for i in range(1, 10) if needs[i] != inf}
# d[本数] = その本数で作れる最大の数値

dp = [0] * (n + 1)
# dp[j] : j本から構成できる桁数の最大値

for j in range(2, n + 1):
    for use, number in d.items():
        if j - use >= 0:
            dp[j] = max(dp[j], dp[j - use] + 1)

for j in range(1, n + 1):
    if dp[j] == 0:
        dp[j] = -10
    else:
        break
# dp[j] == 0 となる点をdp[0]だけにすることで、
# if dp[now - use] == dp[now] - 1:
# で、最後0本にたどり着くようになる

ans = dfs(n)
ans.sort(reverse=True)
print(*ans, sep='')

Submission status: Runtime Error

Solution code:
from math import inf
from sys import setrecursionlimit

setrecursionlimit(10 ** 6)


def larger(x, y):
    lx, ly = len(x), len(y)
    if lx > ly:
        return x
    elif lx < ly:
        return y
    else:
        x.sort(reverse=True)
        y.sort(reverse=True)
        for xx, yy in zip(x, y):
            if xx > yy:
                return x
            elif xx < yy:
                return y
        return x


def dfs(rest):
    res = []
    for use, number in d.items():
        if dp[rest - use] == dp[rest] - 1:
            res = larger(res, [number] + dfs(rest - use))
    return res


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

needs = [inf, 2, 5, 5, 4, 5, 6, 3, 7, 6]
# needs[i] : 数字iを作るのに必要なマッチの本数

for i in range(1, 10):
    if i not in a:
        needs[i] = inf

d = {needs[i]: i for i in range(1, 10) if needs[i] != inf}
# d[本数] = その本数で作れる最大の数値

dp = [0] * (n + 1)
# dp[j] : j本から構成できる桁数の最大値

for j in range(2, n + 1):
    for use, number in d.items():
        if j - use >= 0:
            dp[j] = max(dp[j], dp[j - use] + 1)

for j in range(1, n + 1):
    if dp[j] == 0:
        dp[j] = -10
    else:
        break
# dp[j] == 0 となる点をdp[0]だけにすることで、
# if dp[now - use] == dp[now] - 1:
# で、最後0本にたどり着くようになる

ans = dfs(n)
ans.sort(reverse=True)
print(*ans, sep='')

Submission status: Runtime Error

Solution code:
from operator import itemgetter

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

needs = [2, 5, 5, 4, 5, 6, 3, 7, 6]
lst_use = tuple(needs[aa - 1] for aa in a)
num_use = tuple(sorted(tuple(zip(a, lst_use)), key=itemgetter(0), reverse=True))
# print(num_use)
dp = [0] * (n + 1)
# dp[j] : j本から構成できる桁数の最大値

for j in range(2, n + 1):
    for use in lst_use:
        if j - use >= 0:
            dp[j] = max(dp[j], dp[j - use] + 1)

for j in range(1, n + 1):
    if dp[j] == 0:
        dp[j] = -10
    else:
        break
# dp[j] == 0 となる点をdp[0]だけにすることで、
# if dp[now - use] == dp[now] - 1:
# で、最後0本にたどり着くようになる

# print(dp)
now = n
ans = ''

# dp[1] = -10
# dp[2] = -10
while now > 0:
    for number, use in num_use:
        if dp[now - use] == dp[now] - 1:
            ans += str(number)
            now -= use
            # print(ans)
            break
    else:
        break

assert now == 0, now

print(ans)

Submission status: Runtime Error

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

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

# 最大何桁作れるか

# dp[i] := ちょうど i 本のマッチ棒を使って、条件を満たす整数を作るときの最大桁数
# dp[i + 1] = max(dp[i - m[j]] + 1) for all j in A

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

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

matches = N
ans = ''
for _ in range(dp[N]):
    for a in A:
        if dp[matches - m[a]] == dp[matches] - 1:
            matches -= m[a]
            ans += str(a)
            break

print(ans)

Submission status: Runtime Error

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

A.sort(reverse=True)

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

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

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

maxDigit = dp[-1]

r = N

for _ in range(maxDigit) :
    for a in A :
        if dp[r - match[a - 1]] == dp[r] - 1 :
            print(a, end='')
            r -= match[a - 1]
            break

print('')

Submission status: Runtime Error

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

C = [2, 5, 5, 4, 5, 6, 3, 7, 6]
costs = [C[i-1] for i in A]
INF = float('inf')
dp = [-INF]*(N+1)
dp[0] = 0

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

A.sort(reverse=True)

ans = []
for _ in range(dp[N]):
    for i in A:
        if N != C[i-1]:
            if dp[N-C[i-1]] == dp[N]-1 and N >= C[i-1]:
                ans.append(str(i))
                N -= C[i-1]
                break
        else:
            if dp[N-C[i-1]] == 0 and N >= C[i-1]:
                ans.append(str(i))
                N -= C[i-1]
                break

print(''.join(ans))

Submission status: Runtime Error

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

C = [2, 5, 5, 4, 5, 6, 3, 7, 6]
costs = [C[i-1] for i in A]

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

for i in range(1, N+1):
    dp[i] = max([dp[i-j] if i-j >= 0 else -10 for j in costs]) + 1

A.sort(reverse=True)

ans = []
for _ in range(dp[N]):
    for i in A:
        if N != C[i-1]:
            if dp[N-C[i-1]] == dp[N]-1 and N >= C[i-1]:
                ans.append(str(i))
                N -= C[i-1]
                break
        else:
            if dp[N-C[i-1]] == 0 and N >= C[i-1]:
                ans.append(str(i))
                N -= C[i-1]
                break

print(''.join(ans))

Submission status: Runtime Error

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

C = [2, 5, 5, 4, 5, 6, 3, 7, 6]
costs = [C[i-1] for i in A]

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

for i in range(1, N+1):
    dp[i] = max([dp[i-j] if i-j >= 0 else -10 for j in costs]) + 1

A.sort(reverse=True)

ans = []
for _ in range(dp[N]):
    for i in A:
        if dp[N-C[i-1]] == dp[N]-1 and N >= C[i]:
            ans.append(str(i))
            N -= C[i-1]
            break

print(''.join(ans))

Submission status: Runtime Error

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

C = [2, 5, 5, 4, 5, 6, 3, 7, 6]
costs = [C[i-1] for i in A]

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

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

A.sort(reverse=True)

ans = []
for _ in range(dp[N]):
    for i in A:
        if dp[N-C[i-1]] == dp[N]-1 and N >= C[i]:
            ans.append(str(i))
            N -= C[i-1]
            break

print(''.join(ans))

Submission status: Runtime Error

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

C = [2, 5, 5, 4, 5, 6, 3, 7, 6]
costs = [C[i-1] for i in A]

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

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

A.sort(reverse=True)

print(dp)
ans = []
for _ in range(dp[N]):
    for i in A:
        if dp[N-C[i-1]] == dp[N]-1 and N >= C[i]:
            ans.append(str(i))
            N -= C[i-1]
            break

print(''.join(ans))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100001)
def input():
    return sys.stdin.readline()[:-1]

N, M = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse = True)
x = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [0 for i in range(N+1)]
for i in range(2, N+1):
    for a in A:
        if i >= x[a] and dp[i-x[a]] + 1 > dp[i]:
            dp[i] = dp[i-x[a]] + 1
K = N
ans = ''
while K > 0:
    for a in A:
        if dp[K] == dp[K-x[a]] + 1:
            if dp[K] == 1 and K != x[a]:
                continue
            ans += str(a)
            K -= x[a]
            break
print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100001)
def input():
    return sys.stdin.readline()[:-1]
    
N, M = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse = True)
x = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [0 for i in range(N+1)]
for i in range(2, N+1):
    for a in A:
        if i >= x[a] and dp[i-x[a]] + 1 > dp[i]:
            dp[i] = dp[i-x[a]] + 1
K = N
ans = ''
while K > 0:
    for a in A:
        if dp[K] == dp[K-x[a]] + 1:
            ans += str(a)
            K -= x[a]
            break
print(ans)

Submission status: Runtime Error

Solution code:
a = [2, 5, 5, 4, 5, 6, 3, 7, 6]
N, M = list(map(int, input().split()))
A = sorted(set(list(map(int, input().split()))), reverse=True)
B = sorted([a[i-1] for i in A])

dp = [-1] * (N+1)
for b in B:
    dp[b] = 1

for i in range(1, N+1):
    for b in B:
        if i < b:
            break
        else:
            dp[i] = max(dp[i], dp[i-b]+1)
digit = dp[-1]

for n in A:
    x = a[n-1]
    while dp[N-x] == digit-1:
        print(n, end='')
        N -= x
        digit -= 1
    if N == x:
        print(n, end='')
        N -= x

Submission status: Runtime Error

Solution code:
a = [2, 5, 5, 4, 5, 6, 3, 7, 6]
N, M = list(map(int, input().split()))
A = sorted(list(map(int, input().split())), reverse=True)
B = sorted([a[i-1] for i in A])

dp = [-1] * (N+1)
for b in B:
    dp[b] = 1

for i in range(1, N+1):
    for b in B:
        if i < b:
            break
        else:
            dp[i] = max(dp[i], dp[i-b]+1)
digit = dp[-1]

for n in A:
    x = a[n-1]
    while dp[N-x] == digit-1:
        print(n, end='')
        N -= x
        digit -= 1
    if N == x:
        print(n, end='')
        N -= x

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(2 * (10 ** 9))
lst = [[1,2], [2, 5], [3, 5], [4, 4], [5, 5], [6, 6], [7, 3], [8, 7], [9, 6]]
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse = True)
# print (A)

def num(k):
    return lst[k-1][1]

# for i in A:
    # print (num(i), end = ', ')
# print ()

INF = 10 ** 5
dp_lst = [-INF] * (N + 1)
dp_lst[0] = 0
def dp(i):
    if dp_lst[i] != -INF:
        return dp_lst[i]
    tmp = -INF
    for j in A:
        if i >= num(j):
            tmp = max(tmp, dp(i - num(j)) + 1)
    dp_lst[i] = tmp
    return dp_lst[i]

a = dp(N)
# print (a)
# print (dp_lst)   
# print ([0] * 10 +[i+1 for i in range(20)])

# print (len(str(71111111111111111111111111111111111111111111111111)))

def check(A):
    if dp_lst[N-num(A)] == dp_lst[N] - 1:
        return True
    else:
        return False

# print (a)
while a > 0:
    for i in A:
        if check(i):
            print (i, end = '')
            N -= num(i)
            a -= 1
            break
        else:
            pass
            # print ('B')
print ()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(4 * (10 ** 9))
lst = [[1,2], [2, 5], [3, 5], [4, 4], [5, 5], [6, 6], [7, 3], [8, 7], [9, 6]]
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse = True)
# print (A)

def num(k):
    return lst[k-1][1]

# for i in A:
    # print (num(i), end = ', ')
# print ()

INF = 10 ** 5
dp_lst = [-INF] * (N + 1)
dp_lst[0] = 0
def dp(i):
    if dp_lst[i] != -INF:
        return dp_lst[i]
    tmp = -INF
    for j in A:
        if i >= num(j):
            tmp = max(tmp, dp(i - num(j)) + 1)
    dp_lst[i] = tmp
    return dp_lst[i]

a = dp(N)
# print (a)
# print (dp_lst)   
# print ([0] * 10 +[i+1 for i in range(20)])

# print (len(str(71111111111111111111111111111111111111111111111111)))

def check(A):
    if dp_lst[N-num(A)] == dp_lst[N] - 1:
        return True
    else:
        return False

# print (a)
while a > 0:
    for i in A:
        if check(i):
            print (i, end = '')
            N -= num(i)
            a -= 1
            break
        else:
            pass
            # print ('B')
print ()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
lst = [[1,2], [2, 5], [3, 5], [4, 4], [5, 5], [6, 6], [7, 3], [8, 7], [9, 6]]
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse = True)
# print (A)

def num(k):
    return lst[k-1][1]

# for i in A:
    # print (num(i), end = ', ')
# print ()

INF = 10 ** 5
dp_lst = [-INF] * (N + 1)
dp_lst[0] = 0
def dp(i):
    if dp_lst[i] != -INF:
        return dp_lst[i]
    tmp = -INF
    for j in A:
        if i >= num(j):
            tmp = max(tmp, dp(i - num(j)) + 1)
    dp_lst[i] = tmp
    return dp_lst[i]

a = dp(N)
# print (a)
# print (dp_lst)   
# print ([0] * 10 +[i+1 for i in range(20)])

# print (len(str(71111111111111111111111111111111111111111111111111)))

def check(A):
    if dp_lst[N-num(A)] == dp_lst[N] - 1:
        return True
    else:
        return False

# print (a)
while a > 0:
    for i in A:
        if check(i):
            print (i, end = '')
            N -= num(i)
            a -= 1
            break
        else:
            pass
            # print ('B')
print ()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
lst = [[1,2], [2, 5], [3, 5], [4, 4], [5, 5], [6, 6], [7, 3], [8, 7], [9, 6]]
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse = True)
# print (A)

def num(k):
    return lst[k-1][1]

# for i in A:
    # print (num(i), end = ', ')
# print ()

INF = 10 ** 9
dp_lst = [-INF] * (N + 1)
dp_lst[0] = 0
def dp(i):
    if dp_lst[i] != -INF:
        return dp_lst[i]
    tmp = -INF
    for j in A:
        if i >= num(j):
            tmp = max(tmp, dp(i - num(j)) + 1)
    dp_lst[i] = tmp
    return dp_lst[i]

a = dp(N)
# print (a)
# print (dp_lst)   
# print ([0] * 10 +[i+1 for i in range(20)])

# print (len(str(71111111111111111111111111111111111111111111111111)))

def check(A):
    if dp_lst[N-num(A)] == dp_lst[N] - 1:
        return True
    else:
        return False

# print (a)
while a > 0:
    for i in A:
        if check(i):
            print (i, end = '')
            N -= num(i)
            a -= 1
            break
        else:
            pass
            # print ('B')
print ()