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()))
a.sort(reverse=True)
cost=[0,2,5,5,4,5,6,3,7,6]
inf=10**9
dp=[-1*inf]*(n+1)
dp[0]=0
for i in range(1,n+1):
    for j in range(m):
        dp[i]=max(dp[i],dp[i-cost[a[j]]]+1)
ans=[]
for i in range(dp[n]):
    for j in range(m):
        if dp[n-cost[a[j]]]==dp[n]-1:
            ans.append(a[j])
            n-=cost[a[j]]
            break
print("".join(list(map(str,ans))))

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]
inf=float("inf")
dp=[-1*inf]*(n+1)
dp[0]=0
for i in range(1,n+1):
    for j in range(m):
        dp[i]=max(dp[i],dp[i-num[a[j]]]+1)
ans=[]
for i in range(dp[n]):
    if n<0:
        break
    for j in range(m):
        if dp[n-num[a[j]]]==dp[n]-1:
            ans.append(a[j])
            n-=num[a[j]]
            break
print("".join(list(map(str,ans))))

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]
inf=float("inf")
dp=[-1*inf]*(n+1)
dp[0]=0
for i in range(1,n+1):
    for j in range(m):
        dp[i]=max(dp[i],dp[i-num[a[j]]]+1)
ans=[]
x=dp[n]
for i in range(x):
    for j in range(m):
        if dp[n-num[a[j]]]==dp[n]-1:
            ans.append(a[j])
            n-=num[a[j]]
            break
print("".join(list(map(str,ans))))

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]
inf=float("inf")
dp=[-1*inf]*(n+1)
dp[0]=0
for i in range(1,n+1):
    for j in range(m):
        dp[i]=max(dp[i],dp[i-num[a[j]]]+1)
ans=[]
for i in range(dp[n]):
    for j in range(m):
        if dp[n-num[a[j]]]==dp[n]-1:
            ans.append(a[j])
            n-=num[a[j]]
            break
print("".join(list(map(str,ans))))

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.readline
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]
inf=float("inf")
dp=[-1*inf]*(n+1)
dp[0]=0
for i in range(1,n+1):
    for j in range(m):
        dp[i]=max(dp[i],dp[i-num[a[j]]]+1)
ans=[]
for i in range(dp[n]):
    for j in range(m):
        if dp[n-num[a[j]]]==dp[n]-1:
            ans.append(a[j])
            n-=num[a[j]]
            break
an=""
for i in range(len(ans)):
    an+=str(ans[i])
print(an)

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.readline
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]
inf=float("inf")
dp=[-1*inf]*(n+1)
dp[0]=0
for i in range(1,n+1):
    for j in range(m):
        dp[i]=max(dp[i],dp[i-num[a[j]]]+1)
ans=[]
for i in range(dp[n]):
    for j in range(m):
        if dp[n-num[a[j]]]==dp[n]-1:
            ans.append(a[j])
            n-=num[a[j]]
            break
print("".join(list(map(str,ans))))

Submission status: Runtime Error

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

dp = dict.fromkeys(range(n + 1))  # dp[n]: n本使うときの桁数
dp[0] = 0

num = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
anum = sorted(
    dict(filter(lambda e: e[0] in a, num.items())).items(), reverse=True
)  # 後の計算用にsortしておく

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

ans = ""
while dp[n] > 1:
    for e in anum:  # anum は降順sortされているので, 大きい順に確認
        if n - e[1] >= 0:
            if dp[n - e[1]] == dp[n] - 1:
                ans += str(e[0])
                n -= e[1]
                break

# 末尾桁は n =0(ちょうど使い切るように決定)
ans += str(list(filter(lambda e: e[1] == n, anum))[0][0])

print(ans)

Submission status: Runtime Error

Solution code:
import sys

# お約束
INF = float("inf")
MOD = int(1e9 + 7)
def int1(n):
    return int(n) - 1
def parse(args, *params):
    return tuple(p(v) for p, v in zip(params, next(args).split()))
def debug(*v):
    print(*v, file=sys.stderr)

# エントリーポイント
def main(args):
    N, M = parse(args, int, int)
    A = map(int, next(args).split())

    #       1  2  3  4  5  6  7  8  9
    nums = [2, 5, 5, 4, 5, 6, 3, 7, 6]
    dp = [[]] + [[] for _ in range(N)]
    for a in A:
        na = nums[a - 1]
        def chmax(c):
            nl = sorted(dp[c - na] + [a], reverse=True)
            if len(nl) < len(dp[c]):
                return dp[c]
            if len(dp[c]) < len(nl):
                return nl
            return max(nl, dp[c])
        dp[na] = chmax(na)
        for c in range(na + 1, N + 1):
            if dp[c - na]:
                dp[c] = chmax(c)
    # for i, v in enumerate(dp, start=0):
    #     debug(i, v)
    print(*dp[N], sep="")

if __name__ == '__main__':
    main(iter(sys.stdin.read().split("\n")))

Submission status: Runtime Error

Solution code:
import sys

# お約束
INF = float("inf")
MOD = int(1e9 + 7)
def int1(n):
    return int(n) - 1
def parse(args, *params):
    return tuple(p(v) for p, v in zip(params, next(args).split()))
def debug(*v):
    print(*v, file=sys.stderr)

# エントリーポイント
def main(args):
    N, M = parse(args, int, int)
    A = map(int, next(args).split())

    #       1  2  3  4  5  6  7  8  9
    nums = [2, 5, 5, 4, 5, 6, 3, 7, 6]
    dp = [[]] + [[] for _ in range(N)]
    for a in A:
        na = nums[a - 1]
        def chmax(c):
            nl = sorted(dp[c - na] + [a], reverse=True)
            if len(nl) < len(dp[c]):
                return dp[c]
            if len(dp[c]) < len(nl):
                return nl
            return max(nl, dp[c])
        dp[na] = chmax(na)
        for c in range(na + 1, N + 1):
            if dp[c - na]:
                dp[c] = chmax(c)
    for i, v in enumerate(dp, start=0):
        debug(i, v)
    print(*dp[N], sep="")

if __name__ == '__main__':
    main(iter(sys.stdin.read().split("\n")))

Submission status: Runtime Error

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

number = [0]*9
for i in range(9):
    for j in range(m):
        if a[j] == i+1:
            number[i] += 1

can_use = []
if number[0] > 0:
    can_use.append(2)

if number[6] > 0:
    can_use.append(3)

if number[3] > 0:
    can_use.append(4)

if number[1] + number[2] + number[4] > 0:
    can_use.append(5)

if number[5] + number[8] > 0:
    can_use.append(6)

if number[7] > 0:
    can_use.append(7)

digit = list(list(0 for _ in range(6)) for _ in range(n+1))
digit_num = list(0 for _ in range(n+1))
for i in range(1,n+1):
    for j in can_use:
        if i - j != 0 and digit_num[i-j] == 0:
            continue
        elif digit_num[i-j] + 1 > digit_num[i]:
            digit_num[i] = digit_num[i-j] + 1
            for k in range(6):
                digit[i][k] = digit[i-j][k]
            digit[i][j-2] += 1

can_use_digit = [0]*9
can_use_digit[0] = digit[n][0]
can_use_digit[6] = digit[n][1]
can_use_digit[3] = digit[n][2]
can_use_digit[max(number[1]*1,number[2]*2,number[4]*4)] = digit[n][3]
can_use_digit[max(number[5]*5,number[8]*8)] = digit[n][4]
can_use_digit[7] = digit[n][5]
answer = 0
for i in range(8,-1,-1):
    for j in range(can_use_digit[i]):
        answer *= 10
        answer += i+1

print(answer)

Submission status: Runtime Error

Solution code:
n , m = map(int, input().split(' '))
s = [0,2,5,5,4,5,6,3,7,6]
a = list(map(int, input().split(' ')))
r = []
for i in range(len(a)):
    r.append([s[a[i]],a[i]])
r.sort()
d = [-1]*(n+1)
d[0] = 0
for i in range(1,n+1):
    j = 0
    while j < len(a):
        if i-s[r[j][1]] < 0:
            j += 1
        elif d[i-s[r[j][1]]] >= 0:
            d[i] = d[i-s[r[j][1]]] +1
            break
        else:
            j+= 1
result = []
a.sort(reverse = True)
while n > 0:
    j = 0
    while j < len(a):
        if d[n-s[a[j]]] +1 == d[n]:
            result.append(a[j])
            n -= s[a[j]]
            break
        else:
            j += 1
print(''.join(list(map(str, result))))

Submission status: Runtime Error

Solution code:
n , m = map(int, input().split(' '))
s = [0,2,5,5,4,5,6,3,7,6]
a = list(map(int, input().split(' ')))
r = []
for i in range(len(a)):
    r.append([s[a[i]],a[i]])
r.sort()
d = [0]
for i in range(n):
    d.append(-1)
for i in range(n+1):
    j = 0
    while j < len(a):
        if i -s[r[j][1]] < 0:
            j += 1
        elif d[i-s[r[j][1]]] >= 0:
            d[i] = d[i-s[r[j][1]]] +1
            break
        else:
            j+= 1
result = []
a.sort(reverse = True)
while n > 0:
    j = 0
    while j < len(a):
        if d[n-s[a[j]]] +1 == d[n]:
            result.append(a[j])
            n -= s[a[j]]
        else:
            j += 1
            
print(''.join(list(map(str, result))))

Submission status: Runtime Error

Solution code:
n , m = map(int, input().split(' '))
s = [0,2,5,5,4,5,6,3,7,6]
a = list(map(int, input().split(' ')))
r = []
for i in range(len(a)):
    r.append([s[a[i]],a[i]])
r.sort()
d = [0]
for i in range(n):
    d.append(-1)
#i 本　マッチを使う
for i in range(n+1):
    j = 0
    while j < len(a):
        if d[i-s[r[j][1]]] >= 0:
            d[i] = d[i-s[r[j][1]]] +1
            break
        else:
            j+= 1
result = []
a.sort(reverse = True)
while n > 0:
    j = 0
    while j < len(a):
        if d[n-s[a[j]]] +1 == d[n]:
            result.append(a[j])
            n -= s[a[j]]
        else:
            j += 1
            
print(''.join(list(map(str, result))))

Submission status: Runtime Error

Solution code:
n , m = map(int, input().split(' '))
s = [0,2,5,5,4,5,6,3,7,6]
a = list(map(int, input().split(' ')))
a.sort()
d = [0]
for i in range(n):
    d.append(-1)
#i 本　マッチを使う
for i in range(n+1):
    j = 0
    while j < len(a):
        if d[i-s[a[j]]] >= 0:
            d[i] = d[i-s[a[j]]] +1
            break
        else:
            j+= 1
result = []
a.sort(reverse = True)
while n > 0:
    j = 0
    while j < len(a):
        if d[n-s[a[j]]] +1 == d[n]:
            result.append(a[j])
            n -= s[a[j]]
        else:
            j += 1        
print(''.join(list(map(str, result))))

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys, math, fractions, itertools

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

def solve(N: int, M: int, A: "List[int]"):
    dp = [-1e18] * (N+1)
    dp[0] = 0
    for i in range(1, N+1):
        m = 0
        for a in A:
            m = max(m, dp[i-num[a-1]]+1)
        dp[i] = m
    for i in range(1, N):
        if dp[i] == 0:
            dp[i] = -1
    dd = dp[N]
    ans = ''
    nn = N
    for i in range(dd):
        for a in reversed(sorted(A)):
            if dp[nn-num[a-1]] == dp[nn] - 1:
                ans += str(a)
                nn -= num[a-1]
                break
    print(ans)
    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: Runtime Error

Solution code:
dic = {
  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 = sorted(A, reverse=True)
dic2 = {}
for i in A:
    try:
      dic2[dic[i]]
    except:
      dic2[dic[i]] = i 
result_list = []
items = sorted(dic2.items())
while True:
  if len(items) == 0:
    break
  else:
    if N >= items[0]:
      result_list.append(items[1])
      N = N - items[0]
    else:
      items.pop(0)
return sorted(result_list, reverse=True)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
a = list(map(int, input().split()))
num = [[1,2], [2,5], [3,5], [4,4], [5,5], [6,6], [7,3], [8,7], [9,6]]
num2 = [num[a[i] - 1] for i in range(len(a))]
num2.sort(reverse = True)
num2.sort(key = lambda x: x[1])
x, y = n // num2[0][1], n % num2[0][1]
base = num2[0][0]
base2 = num2[0][1]
del num2[0]
num2.sort(reverse = True)
ans = ""
i = 0
while True:
    if i >= len(num2):
        break
    if num2[i][0] < base:
        break
    else:
        temp = y // (num2[i][1] - base2)
        y -= (num2[i][1] - base2) * temp
        ans += str(num2[i][0]) * temp
        x -= temp
        i += 1
j = -1
ans2 = ""
while y:
    temp = y // (num2[j][1] - base2)
    y -= (num2[j][1] - base2) * temp
    ans2 += str(num2[j][0]) * temp
    x -= temp
    j -= 1 
ans += str(base) * x
ans += ans2
print(ans)

Submission status: Runtime Error

Solution code:
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
# 一次元累積和
from itertools import accumulate
from bisect import bisect_left, bisect_right

import re
# import numpy as np
# from scipy.misc import comb

# 再帰がやばいとき
# import sys
# sys.setrecursionlimit(10**9)

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e50)
MOD = int(1e9)+7 # 10^9 + 7

# field[H][W]
def create_grid(H, W, value = 0):
    return [[ value for _ in range(W)] for _ in range(H)]

########

def main():
    H, M = l_inpl()
    A = l_inpl()
    d = {
        "1": 2,
        "2": 5,
        "3": 5,
        "4": 4,
        "5": 5,
        "6": 6,
        "7": 3,
        "8": 7,
        "9": 6
    }

    new_d = {}
    for Ai in A:
        new_d[Ai] = d[str(Ai)]

    dp = [-INF] * (H+1) # ちょうどi本のマッチ棒を使って，条件を満たす整数を作るときの最大桁数
    dp[0] = 0

    for i in range(1, H+1):
        tmp = []
        for k, v in new_d.items():
            if i-v < 0:
                tmp.append(-INF)
            else:
                tmp.append(dp[i-v]+1)
        dp[i] = max(tmp)

    s = sorted(new_d.items(), key=lambda x:-x[0])

    ans = ""
    remain = H

    while remain > 0:
        for k, v in s:
            if dp[remain-v] != -INF and dp[remain-v] == dp[remain] - 1: # 一桁だけ減少している
                if remain < v:
                    continue
                ans += str(k)
                remain -= v
                break
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
# 一次元累積和
from itertools import accumulate
from bisect import bisect_left, bisect_right

import re
# import numpy as np
# from scipy.misc import comb

# 再帰がやばいとき
# import sys
# sys.setrecursionlimit(10**9)

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e50)
MOD = int(1e9)+7 # 10^9 + 7

# field[H][W]
def create_grid(H, W, value = 0):
    return [[ value for _ in range(W)] for _ in range(H)]

########

def main():
    H, M = l_inpl()
    A = l_inpl()
    d = {
        "1": 2,
        "2": 5,
        "3": 5,
        "4": 4,
        "5": 5,
        "6": 6,
        "7": 3,
        "8": 7,
        "9": 6
    }

    new_d = {}
    for Ai in A:
        new_d[Ai] = d[str(Ai)]

    dp = [-INF] * (H+1) # ちょうどi本のマッチ棒を使って，条件を満たす整数を作るときの最大桁数
    dp[0] = 0

    for i in range(1, H+1):
        tmp = []
        for k, v in new_d.items():
            if i-v < 0:
                tmp.append(-INF)
            else:
                tmp.append(dp[i-v]+1)
        dp[i] = max(tmp)

    s = sorted(new_d.items(), key=lambda x:-x[0])

    ans = ""
    remain = H

    while remain > 0:
        for k, v in s:
            if dp[remain-v] != INF and dp[remain-v] == dp[remain] - 1: # 一桁だけ減少している
                if remain < v:
                    continue
                ans += str(k)
                remain -= v
                break
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
# 一次元累積和
from itertools import accumulate
from bisect import bisect_left, bisect_right

import re
# import numpy as np
# from scipy.misc import comb

# 再帰がやばいとき
# import sys
# sys.setrecursionlimit(10**9)

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e50)
MOD = int(1e9)+7 # 10^9 + 7

# field[H][W]
def create_grid(H, W, value = 0):
    return [[ value for _ in range(W)] for _ in range(H)]

########

def main():
    H, M = l_inpl()
    A = l_inpl()
    d = {
        "1": 2,
        "2": 5,
        "3": 5,
        "4": 4,
        "5": 5,
        "6": 6,
        "7": 3,
        "8": 7,
        "9": 6
    }

    new_d = {}
    for Ai in A:
        new_d[Ai] = d[str(Ai)]

    dp = [-INF] * (H+1) # ちょうどi本のマッチ棒を使って，条件を満たす整数を作るときの最大桁数
    dp[0] = 0

    for i in range(1, H+1):
        tmp = []
        for k, v in new_d.items():
            if i-v < 0:
                tmp.append(-INF)
            else:
                tmp.append(dp[i-v]+1)
        dp[i] = max(tmp)

    s = sorted(new_d.items(), key=lambda x:-x[0])

    ans = ""
    remain = H

    while remain > 0:
        for k, v in s:
            if dp[remain-v] == dp[remain] - 1: # 一桁だけ減少している
                if remain < v:
                    continue
                ans += str(k)
                remain -= v
                break
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
# 一次元累積和
from itertools import accumulate
from bisect import bisect_left, bisect_right

import re
# import numpy as np
# from scipy.misc import comb

# 再帰がやばいとき
# import sys
# sys.setrecursionlimit(10**9)

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e50)
MOD = int(1e9)+7 # 10^9 + 7

# field[H][W]
def create_grid(H, W, value = 0):
    return [[ value for _ in range(W)] for _ in range(H)]

########

def main():
    H, M = l_inpl()
    A = l_inpl()
    d = {
        "1": 2,
        "2": 5,
        "3": 5,
        "4": 4,
        "5": 5,
        "6": 6,
        "7": 3,
        "8": 7,
        "9": 6
    }

    new_d = {}
    for Ai in A:
        new_d[Ai] = d[str(Ai)]

    dp = [-INF] * (H+1) # ちょうどi本のマッチ棒を使って，条件を満たす整数を作るときの最大桁数
    dp[0] = 0

    for i in range(1, H+1):
        tmp = []
        for k, v in new_d.items():
            if i-v < 0:
                tmp.append(-INF)
            else:
                tmp.append(dp[i-v]+1)
        dp[i] = max(tmp)

    s = sorted(new_d.items(), key=lambda x:-x[0])

    ans = ""
    remain = H

    while remain != 0:
        for k, v in s:
            if dp[remain-v] == dp[remain] - 1: # 一桁だけ減少している
                if remain < v:
                    continue
                ans += str(k)
                remain -= v
                break
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
# 一次元累積和
from itertools import accumulate
from bisect import bisect_left, bisect_right

import re
# import numpy as np
# from scipy.misc import comb

# 再帰がやばいとき
# import sys
# sys.setrecursionlimit(10**9)

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e50)
MOD = int(1e9)+7 # 10^9 + 7

# field[H][W]
def create_grid(H, W, value = 0):
    return [[ value for _ in range(W)] for _ in range(H)]

########

def main():
    H, M = l_inpl()
    A = l_inpl()
    d = {
        "1": 2,
        "2": 5,
        "3": 5,
        "4": 4,
        "5": 5,
        "6": 6,
        "7": 3,
        "8": 7,
        "9": 6
    }

    new_d = {}
    for Ai in A:
        new_d[Ai] = d[str(Ai)]

    dp = [-INF] * (H+1) # ちょうどi本のマッチ棒を使って，条件を満たす整数を作るときの最大桁数
    dp[0] = 0

    for i in range(1, H+1):
        tmp = []
        for k, v in new_d.items():
            if i-v < 0:
                tmp.append(-INF)
            else:
                tmp.append(dp[i-v]+1)
        dp[i] = max(tmp)

    s = sorted(new_d.items(), key=lambda x:-x[0])

    ans = ""
    remain = H

    while remain != 0:
        for k, v in s:
            if dp[remain-v] == dp[remain] - 1: # 一桁だけ減少している
                if remain-v < 0:
                    continue
                ans += str(k)
                remain -= v
                break
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
# 一次元累積和
from itertools import accumulate
from bisect import bisect_left, bisect_right

import re
# import numpy as np
# from scipy.misc import comb

# 再帰がやばいとき
# import sys
# sys.setrecursionlimit(10**9)

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e50)
MOD = int(1e9)+7 # 10^9 + 7

# field[H][W]
def create_grid(H, W, value = 0):
    return [[ value for _ in range(W)] for _ in range(H)]

########

def main():
    H, M = l_inpl()
    A = l_inpl()
    d = {
        "1": 2,
        "2": 5,
        "3": 5,
        "4": 4,
        "5": 5,
        "6": 6,
        "7": 3,
        "8": 7,
        "9": 6
    }

    new_d = {}
    for Ai in A:
        new_d[Ai] = d[str(Ai)]

    dp = [-INF] * (H+1) # ちょうどi本のマッチ棒を使って，条件を満たす整数を作るときの最大桁数
    dp[0] = 0

    for i in range(1, H+1):
        tmp = []
        for k, v in new_d.items():
            if i-v < 0:
                tmp.append(-INF)
            else:
                tmp.append(dp[i-v]+1)
        dp[i] = max(tmp)

    s = sorted(new_d.items(), key=lambda x:-x[0])

    ans = ""
    remain = H

    while remain != 0:
        for k, v in s:
            if  dp[remain-v] == dp[remain] - 1: # 一桁だけ減少している
                if remain >= v:
                    continue
                ans += str(k)
                remain -= v
                break
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
# 一次元累積和
from itertools import accumulate
from bisect import bisect_left, bisect_right

import re
# import numpy as np
# from scipy.misc import comb

# 再帰がやばいとき
# import sys
# sys.setrecursionlimit(10**9)

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e50)
MOD = int(1e9)+7 # 10^9 + 7

# field[H][W]
def create_grid(H, W, value = 0):
    return [[ value for _ in range(W)] for _ in range(H)]

########

def main():
    H, M = l_inpl()
    A = l_inpl()
    d = {
        "1": 2,
        "2": 5,
        "3": 5,
        "4": 4,
        "5": 5,
        "6": 6,
        "7": 3,
        "8": 7,
        "9": 6
    }

    new_d = {}
    for Ai in A:
        new_d[Ai] = d[str(Ai)]

    dp = [-INF] * (H+1) # ちょうどi本のマッチ棒を使って，条件を満たす整数を作るときの最大桁数
    dp[0] = 0

    for i in range(1, H+1):
        tmp = []
        for k, v in new_d.items():
            if i-v < 0:
                tmp.append(-INF)
            else:
                tmp.append(dp[i-v]+1)
        dp[i] = max(tmp)

    s = sorted(new_d.items(), key=lambda x:-x[0])

    ans = ""
    remain = H

    while remain != 0:
        for k, v in s:
            if  dp[remain-v] == dp[remain] - 1: # 一桁だけ減少している
                if remain > v:
                    continue
                ans += str(k)
                remain -= v
                break
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
# 一次元累積和
from itertools import accumulate
from bisect import bisect_left, bisect_right

import re
# import numpy as np
# from scipy.misc import comb

# 再帰がやばいとき
# import sys
# sys.setrecursionlimit(10**9)

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e50)
MOD = int(1e9)+7 # 10^9 + 7

# field[H][W]
def create_grid(H, W, value = 0):
    return [[ value for _ in range(W)] for _ in range(H)]

########

def main():
    H, M = l_inpl()
    A = l_inpl()
    d = {
        "1": 2,
        "2": 5,
        "3": 5,
        "4": 4,
        "5": 5,
        "6": 6,
        "7": 3,
        "8": 7,
        "9": 6
    }

    new_d = {}
    for Ai in A:
        new_d[Ai] = d[str(Ai)]

    dp = [-INF] * (H+1) # ちょうどi本のマッチ棒を使って，条件を満たす整数を作るときの最大桁数
    dp[0] = 0

    for i in range(1, H+1):
        tmp = []
        for k, v in new_d.items():
            if i-v < 0:
                tmp.append(-INF)
            else:
                tmp.append(dp[i-v]+1)
        dp[i] = max(tmp)

    s = sorted(new_d.items(), key=lambda x:-x[0])

    ans = ""
    remain = H

    while remain != 0:
        for k, v in s:
            if dp[remain-v] == dp[remain] - 1: # 一桁だけ減少している
                ans += str(k)
                remain -= v
                break
    print(ans)
if __name__ == "__main__":
    main()