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())
lst = list(map(int,input().split()))
lst = [[lst[i]] for i in range(M)]

import numpy as np
import copy 

lst_weight = copy.deepcopy(lst)
weight_lst = copy.deepcopy(lst)
weight = [2,5,5,4,5,6,3,7,6]

for i in range(M):
    lst_weight[i].append(weight[lst[i][0]-1])
    weight_lst[i].insert(0,weight[lst[i][0]-1])

lst_weight.sort()
weight_lst.sort()

memo = []
ans = -1
index = 0
tmp = N % weight_lst[0][0]
memo = [0 for i in range(M)]
memo[0] = N // weight_lst[0][0]

while(True):
    if tmp == 0:#マッチ棒を使い切ったら終了
        break
    else:
        if min(weight_lst[index+1:])[0] <= tmp:
            for i in range(1,M):#見送ったインデックス以降から最適な数字がないか探索
                if tmp % weight_lst[i][0] == 0:
                    while(True):#重みが同じ数字の最大値をとる
                        if weight_lst[i][0] == weight_lst[i+1][0]:
                            i += 1
                        else:
                            break
                    memo[i] = tmp // weight_lst[i][0]
                    tmp -= weight_lst[i][0] * memo[i]
                    break
            else:
                memo[index+1] += 1
                tmp -= weight_lst[index+1][0]
        else:
            for j in range(M-1,-1,-1):#memoを逆順に探索
                if memo[j] != 0:#1以上の値を見つけたら，その数字の採用を見送って（-1），最適解を探索し直す
                    index = j#見送ったインデックス
                    memo[j] -= 1
                    tmp += weight_lst[j][0]

weight_memo = [[weight_lst[i][1]] for i in range(M)]
for i in range(M):
    weight_memo[i].append(memo[i])            

weight_memo.sort()
ans = 0
scope = 1
while(True):
    for i in range(M):
        for j in range(weight_memo[i][1]):
            ans += scope * weight_memo[i][0]
            scope *= 10
    else:
        break

print(ans)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
a = list(map(int, input().split()))
inf = float("inf")
dp = [-inf] * (n+1)
dp[0] = 0
for i in range(1, n+1):
    for j in a:
        cost_j = int("0255456376"[j])
        if i- cost_j >= 0:
            dp[i] = max(dp[i], j+dp[i-cost_j]*10)
        print(dp)
ans = dp[n]
if ans == -inf:
    ans = 0
print(ans)

Submission status: Runtime Error

Solution code:
# dpに最大桁数を持たせる
N,M = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)
f = [-1, 2,5,5,4,5,6,3,7,6] # 1-indexed

# dp[i]: マッチi本数で作れる最大の桁数(int)
dp = [-float('inf')]*(N+1)
dp[0] = 0
for i in range(N+1):
    nxt = dp[i]
    for aj in A:
        nxt = max(nxt, 
                  dp[i-f[aj]] + 1)
    dp[i] = nxt
    #print(dp)
#print(dp[N])
keta = dp[N]
ans = ""
matchs = N
# 上位の桁から貪欲に
while keta>0:
    for aj in A:
        if dp[matchs-f[aj]] == keta-1:
            ans += str(aj)
            matchs -= f[aj]
            keta -= 1
            break
print(ans)

Submission status: Runtime Error

Solution code:
# dpに最大桁数を持たせる
N,M = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)
f = [-1, 2,5,5,4,5,6,3,7,6] # 1-indexed

# dp[i]: マッチi本数で作れる最大の桁数(int)
dp = [-float('inf')]*(N+1)
dp[0] = 0
for i in range(2,N+1):
    nxt = dp[i]
    for aj in A:
        nxt = max(nxt, 
                  dp[i-f[aj]] + 1)
    dp[i] = nxt
    #print(dp)
#print(dp[N])
keta = dp[N]
ans = ""
matchs = N
# 上位の桁から貪欲に
while keta>0:
    for aj in A:
        if dp[matchs-f[aj]] == keta-1:
            ans += str(aj)
            matchs -= f[aj]
            keta -= 1
            break
print(ans)

Submission status: Runtime Error

Solution code:
# コンテスト中の考えは悪くなかったがN本に固執して貪欲的に考えていた。
# 敗因は動的計画法が思い浮かばず書けなかったこと。
# 提出4298627を参考にした


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

A.sort(reverse=True)  # 大きい方から探索したいため

# 各数字を作るのに必要なマッチの本数
num = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]

# dpをするための配列を用意
# pd[i]としたときに、i本のマッチで実現できる最大桁数を格納するものとする
# shapeは(N+1,) ∵ i=0~N本のときも考える
dp = [-1 * float("inf")] * (N + 1)

# 各数字を一つずつ使う場合は1桁だとわかりきっているので、初期化ができる
dp[0] = 0
for a in A:
    if num[a] <= N:  # ここは念のための処理、指定されたNがマッチで使う数字より少ないかもしれない。
        dp[num[a]] = 1

# dpのmain
for i in range(1, N + 1):  # dpに格納されているすべての要素をなめていく。
    for a in A:  # i本使うときの最大桁数を決定するためにはaを全探索して下式を最大となるものが取得できればよい
        if i - num[a] >= 0:  # 念の為の条件
            # この式については解説を参照のこと
            dp[i] = max(dp[i], dp[i - num[a]] + 1)

# 探索が終わったので答えを出す。
# 大きい桁にはなるべく大きな数字を割り振る
ans = ""
for i in range(dp[N]):  # dpによって得た桁数について上位桁から決定していく
    for a in A:  # すでに大きい順にソートしたので決定次第break
        # 1つ目の条件は探索中に配列外アクセスをするのを防ぐため。2つ目の条件についても解説を参照のこと
        if N - num[a]　> -1 and dp[N - num[a]] == dp[N] - 1:
            ans += str(a)
            N -= num[a]  # マッチの本数から引くのを忘れずにね
            break

print(ans)

Submission status: Runtime Error

Solution code:
# コンテスト中の考えは悪くなかったがN本に固執して貪欲的に考えていた。
# 敗因は動的計画法が思い浮かばず書けなかったこと。
# 提出4298627を参考にした


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

A.sort(reverse=True)  # 大きい方から探索したいため

# 各数字を作るのに必要なマッチの本数
num = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]

# dpをするための配列を用意
# pd[i]としたときに、i本のマッチで実現できる最大桁数を格納するものとする
# shapeは(N+1,) ∵ i=0~N本のときも考える
dp = [-1 * float("inf")] * (N + 1)

# 各数字を一つずつ使う場合は1桁だとわかりきっているので、初期化ができる
dp[0] = 0
for a in A:
    if num[a] <= N:  # ここは念のための処理、指定されたNがマッチで使う数字より少ないかもしれない。
        dp[num[a]] = 1

# dpのmain
for i in range(1, N + 1):  # dpに格納されているすべての要素をなめていく。
    for a in A:  # i本使うときの最大桁数を決定するためにはaを全探索して下式を最大となるものが取得できればよい
        if i - num[a] >= 0:  # 念の為の条件
            # この式については解説を参照のこと
            dp[i] = max(dp[i], dp[i - num[a]] + 1)

# 探索が終わったので答えを出す。
# 大きい桁にはなるべく大きな数字を割り振る
ans = ""
for i in range(dp[N]):  # dpによって得た桁数について上位桁から決定していく
    for a in A:  # すでに大きい順にソートしたので決定次第break
        if dp[N - num[a]] == dp[N] - 1:  # この条件についても解説を参照のこと
            ans += str(a)
            N -= num[a]  # マッチの本数から引くのを忘れずにね
            break

print(ans)

Submission status: Runtime Error

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

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

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

use_cost = []
for i in a:
    use_cost.append(cost[i])

if n < min(use_cost):
    print(0)
    exit()

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

a.sort(reverse=True)
ans = ""
while n > 0:
    for i in a:
        if dp[n-cost[i]] == dp[n]-1:
            ans += str(i)
            n -= cost[i]
            break
print(ans)

Submission status: Runtime Error

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

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

cost = {1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6}
use_cost = []
for i in a:
    use_cost.append(cost[i])
    for j in range(1, n+1):
        if j - cost[i] >= 0:
            dp[j] = max(dp[j], dp[j-cost[i]]+1)

if n < min(use_cost):
    print(0)
    exit()

a.sort(reverse=True)
ans = ""
while n > 0:
    for i in a:
        if dp[n-cost[i]] == dp[n]-1:
            ans += str(i)
            n -= cost[i]
            break
print(ans)

Submission status: Runtime Error

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

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

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

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

a.sort(reverse=True)
ans = ""
while n > 0:
    for i in a:
        if dp[n-cost[i]] == dp[n]-1:
            ans += str(i)
            n -= cost[i]
            break
print(ans)

Submission status: Runtime Error

Solution code:
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, OrderedDict
from copy import deepcopy
from functools import lru_cache, reduce
from math import ceil, floor, inf
from sys import setrecursionlimit

import heapq
import itertools
import operator


def get_int():
    return int(input())


def get_str():
    return input().strip()


def get_int_list():
    return [int(i) for i in input().split()]


def get_char_list():
    return list(input().strip())


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


# inputs
N, M = 0, 0
A = [0]


def hoge():
    d = dict()
    def labeler(label, iter):
        enumerate()


def set_inputs():
    global N, M, A
    N, M = get_int_list()
    A = get_int_list()


@lru_cache(maxsize=None)
def dp(i):
    if i < 0:
        return -inf
    elif i == 0:
        return 0
    return max(dp(i - COST[a]) + 1 for a in A)


def main():
    setrecursionlimit(100000)
    set_inputs()

    candidates = sorted(A, reverse=True)
    ret = []
    n = N
    for i in range(dp(N)):
        for a in candidates:
            cond = True
            if i == dp(N) - 1:
                cond = COST[a] == n
            if dp(n - COST[a]) == dp(n) - 1 and cond:
                ret.append(a)
                n -= COST[a]
                break
    print(''.join(str(r) for r in ret))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

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

H = {}
for x in X:
  b = P[x]
  s = {'num':str(x), 'score':x, 'bar':b}
  H[b] = s
  
GA = []
GF = None
ff = 10

while True:
  G = {}
  for k,v in H.items():
    for x in X:
      ss = v['bar'] + P[x]
      nv = v.copy()
      nv['num'] = str(x) + nv['num']
      nv['score'] += ff*x
      nv['bar'] += P[x]
      #nv['prev'] = v
      
      if ss == N:
        if GF is None:
          GF = nv
        else:
          if GF['score'] < nv['score']:
            GF = nv
        #print(nv)
        #print("HIT-----------------------------")
        continue
      if ss > N:
        continue

      if ss not in G:
        G[ss] = nv
      else:
        if G[ss]['score'] < nv['score']:
          G[ss] = nv

  if len(G) == 0:
    break
    
  #GA.append(G.copy())
  H = G
  ff *= 10
  
 
print(GF['num'])

Submission status: Runtime Error

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

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

H = {}
for x in X:
  b = P[x]
  s = {'num':str(x), 'score':x, 'bar':b}
  H[b] = s
  
GA = []
GF = []
ff = 10

while True:
  G = {}
  for k,v in H.items():
    for x in X:
      ss = v['bar'] + P[x]
      nv = v.copy()
      nv['num'] = str(x) + nv['num']
      nv['score'] += ff*x
      nv['bar'] += P[x]
      #nv['prev'] = v
      
      if ss == N:
        GF.append(nv)
        #print(nv)
        #print("HIT-----------------------------")
        continue
      if ss > N:
        continue

      if ss not in G:
        G[ss] = nv
      else:
        if G[ss]['score'] < nv['score']:
          G[ss] = nv

  if len(G) == 0:
    break
    
  #GA.append(G.copy())
  H = G
  ff *= 10
  
mval = 0
MM = None
for g in GF:
  if mval < g['score']:
    mval = g['score']
    MM = g
  #print(g['num'],g['score'])
  
print(MM['num'])

Submission status: Runtime Error

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

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

H = {}
for x in X:
  b = P[x]
  s = {'num':str(x), 'score':x, 'bar':b}
  H[b] = s
  
GA = []
GF = []
ff = 10

while True:
  G = {}
  for k,v in H.items():
    for x in X:
      ss = v['bar'] + P[x]
      nv = v.copy()
      nv['num'] = str(x) + nv['num']
      nv['score'] += ff*x
      nv['bar'] += P[x]
      nv['prev'] = v
      
      if ss == N:
        GF.append(nv)
        #print(nv)
        #print("HIT-----------------------------")
        continue
      if ss > N:
        continue

      if ss not in G:
        G[ss] = nv
      else:
        if G[ss]['score'] < nv['score']:
          G[ss] = nv

  if len(G) == 0:
    break
    
  GA.append(G.copy())
  H = G
  ff *= 10
  
mval = 0
MM = None
for g in GF:
  if mval < g['score']:
    mval = g['score']
    MM = g
  #print(g['num'],g['score'])
  
print(MM['num'])

Submission status: Runtime Error

Solution code:
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, OrderedDict
from copy import deepcopy
from functools import lru_cache, reduce
from math import ceil, floor

import heapq
import itertools
import operator


def get_int():
    return int(input())


def get_str():
    return input().strip()


def get_int_list():
    return [int(i) for i in input().split()]


def get_char_list():
    return list(input().strip())


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


# inputs
N, M = 0, 0
A = [0]


def hoge():
    d = dict()
    def labeler(label, iter):
        enumerate()


def set_inputs():
    global N, M, A
    N, M = get_int_list()
    A = get_int_list()


@lru_cache(maxsize=None)
def dp(i):
    if i < min(COST[a] for a in A):
        return 0
    return max(dp(i - COST[a]) + 1 for a in A)


def main():
    set_inputs()

    candidates = sorted(A, reverse=True)
    ret = []
    n = N
    for i in range(dp(N)):
        for a in candidates:
            cond = True
            if i == dp(N) - 1:
                cond = COST[a] == n
            if dp(n - COST[a]) == dp(n) - 1 and cond:
                ret.append(a)
                n -= COST[a]
                break
    print(''.join(str(r) for r in ret))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
# coding: utf-8
import sys

# import bisect
# import math
# import itertools

# import numpy as np


"""Template"""


class IP:
    """
    入力を取得するクラス
    """

    def __init__(self):
        self.input = sys.stdin.readline

    def I(self):
        """
        1文字の取得に使います
        :return: int
        """
        return int(self.input())

    def S(self):
        """
        1文字の取得(str
        :return: str
        """
        return self.input()

    def IL(self):
        """
        1行を空白で区切りリストにします(int
        :return: リスト
        """
        return list(map(int, self.input().split()))

    def SL(self):
        """
        1行の文字列を空白区切りでリストにします
        :return: リスト
        """
        return list(map(str, self.input().split()))

    def ILS(self, n):
        """
        1列丸々取得します(int
        :param n: 行数
        :return: リスト
        """
        return [int(self.input()) for _ in range(n)]

    def SLS(self, n):
        """
        1列丸々取得します（str
        :param n: 行数
        :return: リスト
        """
        return [self.input() for _ in range(n)]

    def SILS(self, n):
        """
        Some Int LineS
        横に複数、縦にも複数
        :param n: 行数
        :return: list
        """
        return [self.IL() for _ in range(n)]

    def SSLS(self, n):
        """
        Some String LineS
        :param n: 行数
        :return: list
        """
        return [self.SL() for _ in range(n)]


class Idea:
    def __init__(self):
        pass

    def HF(self, p):
        """
        Half enumeration
        半分全列挙です
        pの要素の和の組み合わせを作ります。
        ソート、重複削除行います
        :param p: list : 元となるリスト
        :return: list : 組み合わせられた和のリスト
        """
        return sorted(set(p[i] + p[j] for i in range(len(p)) for j in range(i, len(p))))

    def Bfs2(self, a):
        """
        bit_full_search2
        bit全探索の改良版
        全探索させたら2進数のリストと10進数のリストを返す
        :return: list２つ : １個目 2進数(16桁)  2個目 10進数
        """
        # 参考
        # https://blog.rossywhite.com/2018/08/06/bit-search/
        # https://atcoder.jp/contests/abc105/submissions/4088632
        value = []
        for i in range(1 << len(a)):
            output = []

            for j in range(len(a)):
                if self.bit_o(i, j):
                    """右からj+1番目のiが1かどうか判定"""
                    # output.append(a[j])
                    output.append(a[j])
            value.append([format(i, 'b').zfill(16), sum(output)])

        value.sort(key=lambda x: x[1])
        bin = [value[k][0] for k in range(len(value))]
        val = [value[k][1] for k in range(len(value))]
        return bin, val

    def S(self, s, r=0, m=-1):
        """
        ソート関係行います。色々な設定あります。
        :param s: 元となるリスト
        :param r: reversするかどうか 0=False 1=True
        :param m: （2次元配列）何番目のインデックスのソートなのか
        :return: None
        """
        r = bool(r)
        if m == -1:
            s.sort(reverse=r)
        else:
            s.sort(reverse=r, key=lambda x: x[m])

    def bit_n(self, a, b):
        """
        bit探索で使います。0以上のときにTrue出します
        自然数だからn
        :param a: int
        :param b: int
        :return: bool
        """
        return bool((a >> b & 1) > 0)

    def bit_o(self, a, b):
        """
        bit探索で使います。1のときにTrue出すよ
        oneで1
        :param a: int
        :param b: int
        :return: bool
        """
        return bool(((a >> b) & 1) == 1)

    def ceil(self, x, y):
        """
        Round up
        小数点切り上げ割り算
        :param x: int
        :param y: int
        :return: int
        """
        return -(-x // y)

    def ave(self, a):
        """
        平均を求めます
        :param a: list
        :return: int
        """
        return sum(a) / len(a)

    def gcd(self, x, y):
        if y == 0:
            return x
        else:
            return self.gcd(y, x % y)


"""ここからメインコード"""


def main():
    # 1文字に省略
    r, e = range, enumerate
    ip = IP()
    id = Idea()

    """この下から書いてね"""
    n, m = ip.IL()
    a = ip.IL()
    c = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
    f = [-1] * n
    f[0] = 0

    for i in r(n):
        i += 1
        for x in a:
            if i - c[x] >= 0:
                f[i] = max(f[i], f[i - c[x]] * 10 + x)

    print(f[n])


main()

Submission status: Runtime Error

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

A.sort(reverse=True)

# 各数字に必要なマッチの本数
num  = [0,2,5,5,4,5,6,3,7,6]
# dp : i本のマッチで実現できる最大の桁数
dp = [-1*float("inf")]*(N+1)
# dp初期化 (0本では0桁, 各数字を1つ作る場合は1桁)
dp[0] = 0
for a in A:
    if num[a] <= N:
        dp[num[a]] = 1

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

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

print(ans)

Submission status: Runtime Error

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

N, M = map(int, input().split())
A = list(map(int, input().split()))
neginf = -1 * 1e20
D = [neginf]*(N+1)

def dp(n_match):
    D[0] = 0
    for n in range(1,n_match+1):
        arr = [D[n-costs[a-1]] if n-costs[a-1]>=0 else neginf for a in A]
        if max(arr) < 0:
            continue
        D[n] = max(arr)+1
    # exit(0)

def main():
    dp(N)
    # print(D)
    # exit(0)
    n = N
    ans = ''
    while n>0:
        arr = [ a for a in A if D[n-costs[a-1]]==D[n]-1 ]
        if len(arr)>0:
            a = max(arr)
            ans += str(a)
            n -= costs[a-1]
        else:
            break
    print(ans)

main()

Submission status: Runtime Error

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

N, M = map(int, input().split())
A = list(map(int, input().split()))
neginf = -1 * 1e20
D = [neginf]*(N+1)

def dp(n_match):
    D[0] = 0
    for n in range(1,n_match+1):
        # if D[n] < 0:
        #     continue
        arr = [D[n-costs[a-1]] if n-costs[a-1]>=0 else neginf for a in A]
        D[n] = max(arr)+1
    # exit(0)

def main():
    dp(N)
    # print(D)
    # exit(0)
    n = N
    ans = ''
    while n>0:
        arr = [ a for a in A if D[n-costs[a-1]]==D[n]-1 ]
        if len(arr)>0:
            a = max(arr)
            ans += str(a)
            n -= costs[a-1]
        else:
            break
    print(ans)

main()

Submission status: Runtime Error

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

A.sort(reverse=True)

# 各数字に必要なマッチの本数
num  = [0,2,5,5,4,5,6,3,7,6]
# dp : i本のマッチで実現できる最大の桁数
dp = [-1*float("inf")]*(N+1)
# dp初期化 (0本では0桁, 各数字を1つ作る場合は1桁)
dp[0] = 0
for a in A:
    dp[num[a]] = 1

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

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

print(ans)

Submission status: Runtime Error

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

N, M = map(int, input().split())
A = list(map(int, input().split()))
neginf = -1 * 1e20
D = [neginf]*(N+1)

def dp(n_match):
    D[0] = 0
    for n in range(1,n_match+1):
        arr = [D[n-costs[a-1]] if n-costs[a-1]>=0 else neginf for a in A]
        D[n] = max(arr)+1

def main():
    dp(N)
    n = N
    ans = ''
    while n>1:
        arr = [ a for a in A if D[n-costs[a-1]]==D[n]-1 ]
        if len(arr)>0:
            a = max(arr)
            ans += str(a)
            n -= costs[a-1]
        else:
            break
    print(ans)

main()

Submission status: Runtime Error

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

N, M = map(int, input().split())
A = list(map(int, input().split()))
neginf = -1 * 1e20
D = [neginf]*(N+1)

def dp(n_match):
    D[0] = 0
    for n in range(1,n_match+1):
        arr = [D[n-costs[a-1]] if n-costs[a-1]>=0 else neginf for a in A]
        D[n] = max(arr)+1

def main():
    dp(N)
    n = N
    ans = ''
    while n>1:
        for a in A:
            arr = [ a for a in A if D[n-costs[a-1]]==D[n]-1 ]
        a = max(arr)
        ans += str(a)
        n -= costs[a-1]
    print(ans)

main()

Submission status: Runtime Error

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

N, M = map(int, input().split())
A = list(map(int, input().split()))
neginf = -1 * 1e20
D = [neginf]*(N+1)

def dp(n_match):
    D[0] = 0
    for n in range(1,n_match+1):
        arr = [D[n-costs[a-1]] if n-costs[a-1]>=0 else neginf for a in A]
        D[n] = max(arr)+1

def main():
    if N==0:
        print('0')
        return
    dp(N)
    n = N
    ans = ''
    while n>0:
        for a in A:
            arr = [a for a in A if D[n-costs[a-1]]==D[n]-1]
        a = max(arr)
        ans += str(a)
        n -= costs[a-1]
    print(ans)
    return

main()

Submission status: Runtime Error

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

N, M = map(int, input().split())
A = list(map(int, input().split()))
neginf = -1 * 1e20
D = [neginf]*(N+1)

def dp(n_match):
    D[0] = 0
    for n in range(1,n_match+1):
        arr = [D[n-costs[a-1]] if n-costs[a-1]>=0 else neginf for a in A]
        D[n] = max(arr)+1

def main():
    dp(N)
    n = N
    ans = ''
    while n>0:
        for a in A:
            arr = [a for a in A if D[n-costs[a-1]]==D[n]-1]
        a = max(arr)
        ans += str(a)
        n -= costs[a-1]
    print(ans)

main()

Submission status: Runtime Error

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

N, M = map(int, input().split())
A = list(map(int, input().split()))
neginf = -1 * 1e10
D = [neginf]*(N+1)

def dp(n_match):
    D[0] = 0
    for n in range(1,n_match+1):
        arr = [D[n-costs[a-1]] if n-costs[a-1]>=0 else neginf for a in A]
        D[n] = max(arr)+1

def main():
    dp(N)
    n = N
    ans = ''
    while n>0:
        for a in A:
            arr = [a for a in A if D[n-costs[a-1]]==D[n]-1]
        a = max(arr)
        ans += str(a)
        n -= costs[a-1]
    print(ans)

main()

Submission status: Runtime Error

Solution code:
import math
costs = [2,5,5,4,5,6,3,7,6]

N, M = map(int, input().split())
A = list(map(int, input().split()))
neginf = -1 * math.inf
D = [neginf]*(N+1)

def dp(n_match):
    D[0] = 0
    for n in range(1,n_match+1):
        arr = [D[n-costs[a-1]] if n-costs[a-1]>=0 else neginf for a in A]
        D[n] = max(arr)+1

def main():
    dp(N)
    n = N
    ans = ''
    while n>0:
        for a in A:
            arr = [a for a in A if D[n-costs[a-1]]==D[n]-1]
        a = max(arr)
        ans += str(a)
        n -= costs[a-1]
    print(ans)

main()

Submission status: Runtime Error

Solution code:
import numpy as np

#initialization
nmatch = np.array([0,2,5,5,4,5,6,3,7,6])
N,M = map(int,input().split())
dp = [-1]*(N+1) # contains the number of digits it can make
dp[0] = 0
ff = np.array(list(map(int,input().split()))).reshape(-1,1)
fg = nmatch[ff].reshape(-1,1)
Atemp = np.concatenate([ff,fg],axis=1)
index0 = np.argsort(Atemp[:,0])
index1 = np.argsort(Atemp[:,1])
A = Atemp[index1] #sorted by the number of matches: ascending
B = Atemp[index0]
B = B[::-1] #sorted by the number: descending
for i in range(1,N+1):
    for k in range(M):
        j = A[k,1]
        i_old = i - j #available matches
        if (i-j) < 0:
            break
        if (i-j) == 0 and dp[i] == -1:
            dp[i] = 1
        if dp[i_old] != -1 and dp[i_old]+1 > dp[i]:
            dp[i] = dp[i_old] + 1
#print(dp)
ndigits = dp[N]
j = N
final_number = ''
for l in range(ndigits,0,-1):
    index = 0
    while True:
        temp_j = j - B[index,1]
        if dp[temp_j] + 1 == dp[j]:
            final_number += str(B[index,0])
            j = temp_j
            break
        else:
            index += 1
        if index > M:
            break
print(int(final_number))

Submission status: Runtime Error

Solution code:
import collections
from time import sleep
def main():
	match = {1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6}
	count = collections.defaultdict(int)
	n, m = map(int, input().split())
	ms = list(map(int, input().split()))
	ms.sort()
	ms.reverse()
	use_match = []
	for i in range(m):
		if count[match[ms[i]]] == 0:
			use_match.append([match[ms[i]], ms[i]])
		count[match[ms[i]]] += 1
	sorted(use_match, key = lambda x: x[0])
	dp = [-1]*(n+1)
	dp[0] = 0
	for i in range(n+1):
		maximum = -1
		for k in use_match:
			if i - k[0] >= 0:
				current = dp[i-k[0]] + 1
				if maximum < current:
					maximum = current
		if maximum != -1:
			dp[i] = maximum
	num = n
	ans = ""
	while num > 0:
		for k in use_match:
			if dp[num] - dp[num - k[0]] == 1:
				ans += str(k[1])
				num -= k[0]
				break
	print(ans)


if __name__ == '__main__':
	main()

Submission status: Runtime Error

Solution code:
from collections import defaultdict
from copy import copy

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

ms = [2,5,5,4,5,6,3,7,6]
dic = defaultdict(lambda: 0)
for a in A:
    dic[ms[a-1]] = max(dic[ms[a-1]], a)

sd = sorted(dic.items())

dp = [None] * (N+1)
dp[0] = defaultdict(lambda: 0)

for i in range(sd[0][0], N+1):
    cands = []
    for l,a in sd:
        if i-l < 0: break
        if dp[i-l] is None: continue
        cands.append(copy(dp[i-l]))
        cands[-1][a] += 1
    if not cands: continue
    max_v = 0
    max_i = -1
    for i,cand_dic in enumerate(cands):
        tmp_s = ''
        for a,n in sorted(cand_dic.items(), reverse=True):
            tmp_s += str(a) * n
        tmp_v = int(tmp_s)
        if tmp_v > max_v:
            max_v = tmp_v
            max_i = i
    dp[i] = cands[i]

ans = ''
for a,n in sorted(dp[-1].items(), reverse=True):
    ans += str(a) * n
print(ans)

Submission status: Runtime Error

Solution code:
import collections
from time import sleep
def main():
	match = {1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6}
	count = collections.defaultdict(int)
	n, m = map(int, input().split())
	ms = list(map(int, input().split()))
	ms.sort()
	ms.reverse()
	use_match = []
	for i in range(m):
		if count[match[ms[i]]] == 0:
			use_match.append([match[ms[i]], ms[i]])
		count[match[ms[i]]] += 1
	sorted(use_match, key = lambda x: x[0])
	dp = [-1]*(n+1)
	dp[0] = 0
	for i in range(n+1):
		maximum = 0
		for k in use_match:
			if i - k[0] >= 0:
				current = dp[i-k[0]] + 1
				if maximum < current:
					maximum = current
		if maximum != 0:
			dp[i] = maximum
	num = n
	ans = ""
	while num > 0:
		for k in use_match:
			if dp[num] - dp[num - k[0]] == 1:
				ans += str(k[1])
				num -= k[0]
				break
	print(ans)


if __name__ == '__main__':
	main()

Submission status: Runtime Error

Solution code:
import numpy as np

#initialization
nmatch = np.array([0,2,5,5,4,5,6,3,7,6])
N,M = map(int,input().split())
dp = [-1]*(N+1) # contains the number of digits it can make
dp[0] = 0
ff = np.array(list(map(int,input().split()))).reshape(-1,1)
fg = nmatch[ff].reshape(-1,1)
Atemp = np.concatenate([ff,fg],axis=1)
print(Atemp)
index0 = np.argsort(Atemp[:,0])
index1 = np.argsort(Atemp[:,1])
A = Atemp[index1] #sorted by the number of matches: ascending
print(A)
B = Atemp[index0]
B = B[::-1] #sorted by the number: descending
print(B)
for i in range(1,N+1):
    #dp(i)を求める
    for k in range(M):
        j = A[k,1]
        i_old = i - j #available matches
        if (i-j) < 0:
            break
        if (i-j) == 0 and dp[i] == -1:
            dp[i] = 1
        if dp[i_old] != -1 and dp[i_old]+1 > dp[i]:
            dp[i] = dp[i_old] + 1
print(dp)
ndigits = dp[N]
j = N
final_number = ''
for l in range(ndigits,0,-1):
    #桁を求めていく
    index = 0
    while True:
        temp_j = j - B[index,1]
        if dp[temp_j] + 1 == dp[j]:
            final_number += str(B[index,0])
            j = temp_j
            break
        else:
            index += 1
        if index > M:
            print('smth is wrong')
            break
print(int(final_number))

Submission status: Runtime Error

Solution code:
import collections
from time import sleep
def main():
	match = {1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6}
	count = collections.defaultdict(int)
	n, m = map(int, input().split())
	ms = list(map(int, input().split()))
	ms.sort()
	ms.reverse()
	use_match = []
	for i in range(m):
		if count[match[ms[i]]] == 0:
			use_match.append([match[ms[i]], ms[i]])
		count[match[ms[i]]] += 1
	sorted(use_match, key = lambda x: x[0])
	dp = [-1]*(n+1)
	dp[0] = 0
	for i in range(n+1):
		maximum = 0
		for j in range(i):
			for k in use_match:
				if i - k[0] >= 0:
					current = dp[i-k[0]] + 1
					if maximum < current:
						maximum = current
		if maximum != 0:
			dp[i] = maximum
	num = n
	ans = ""
	while num > 0:
		for k in use_match:
			if dp[num] - dp[num - k[0]] == 1:
				ans += str(k[1])
				num -= k[0]
				break
	print(ans)


if __name__ == '__main__':
	main()