Problem:


Score : 400 points

Problem Statement

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

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

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

Constraints

All values in input are integers.

2 \leq N \leq 10^4

1 \leq M \leq 9

1 \leq A_i \leq 9

A_i are all different.

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

Input

Input is given from Standard Input in the following format:

N M
A_1 A_2 ... A_M

Output

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

Sample Input 1

20 4
3 7 8 4

Sample Output 1

777773

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

Sample Input 2

101 9
9 8 7 6 5 4 3 2 1

Sample Output 2

71111111111111111111111111111111111111111111111111

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

Sample Input 3

15 3
5 4 6

Sample Output 3

654



Sample input:
20 4
3 7 8 4


Sample output:
777773

Submission status: Accepted

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

numbers = [None, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [-1] * (N+1)
dp[0] = 0
for i in range(N+1):
    for a in A:
        j = i + numbers[a]
        if j <= N:
            dp[j] = max(dp[j], dp[i]*10 + a)
print(dp[N])

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(10000)


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

num_dict = {
    1: 2,
    2: 5,
    3: 5,
    4: 4,
    5: 5,
    6: 6,
    7: 3,
    8: 7,
    9: 6
}
A.sort(reverse=True)

# dpを計算
dp = defaultdict(lambda: -1e18)
dp[0] = 0

for i in range(2, N+1):
    dp[i] = max([dp[i-num_dict[a]]+1 for a in A])

num_count = dp[N]

out_list = []
res_N = N
for _ in range(num_count):
    for a in A:
        if dp[res_N]-1 == dp[res_N-num_dict[a]]:
            out_list.append(str(a))
            res_N = res_N - num_dict[a]
            break

print(''.join(out_list))

Submission status: Accepted

Solution code:
v=[-1,2,5,5,4,5,6,3,7,6]

N,M=map(int, input().split())
A=sorted(map(int, input().split()), reverse=True)

dp=[0]*(N+999)
mp=[[] for _ in range(N+999)]

for a in reversed(A):
	dp[v[a]] = 1
	mp[v[a]] = [a]

for i in range(N+1):
	for a in A:
		if i-v[a] >= 0 and dp[i-v[a]] > 0 and dp[i] < 1 + dp[i-v[a]]:
			dp[i] = 1 + dp[i-v[a]]
			mp[i] = [a] + mp[i-v[a]]

print("".join(map(str, mp[N])))

Submission status: Accepted

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

numbers = [None, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = {i: -1 for i in range(N+1)}
dp[0] = 0
for i in range(N+1):
    for a in A:
        j = i + numbers[a]
        if j <= N:
            dp[j] = max(dp[j], dp[i]*10 + a)
print(dp[N])

Submission status: Accepted

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


def matchnum(n):
    table = [2, 5, 5, 4, 5, 6, 3, 7, 6]
    return table[n - 1]


# dp[n] : n本使った時の桁数
dp = [0] + [-INF for _ in range(N)]
for i in range(N + 1):
    for j, a_j in enumerate(A):
        if i - matchnum(a_j) >= 0:
            dp[i] = max(dp[i], dp[i - matchnum(a_j)] + 1)

l = dp[N]
m = N
ans = []
A = sorted(A, reverse=True)
while m > 0:
    for i, a_i in enumerate(A):
        if m - matchnum(a_i) >= 0 and dp[m - matchnum(a_i)] == l - 1:
            ans.append(str(a_i))
            m -= matchnum(a_i)
            l -= 1
            break
print(''.join(ans))

Submission status: Accepted

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

INF= 10 ** 9
d_t = {
    1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6
}


# 使う候補の数字を選ぶ
# A1, ..., AMのうち、本数が同じものは大きな方だけを採用する
d = dict()
for a in A:
    d[a] = d_t[a]

if 2 in A and (3 in A or 5 in A):
    d.pop(2)

if 3 in A and 5 in A:
    d.pop(3)

if 6 in A and 9 in A:
    d.pop(6)


# N本で何桁作れるか求める
# dp[n]: n本で作れる最大の桁数
# dp[n]は dp[n-k] + 1 で作ることができる(dp[n-k]>0のときのみ、どのkが最適かは分からない)
dp = [-INF] * (N + 1)
dp[0] = 0
for i in range(1, N+1):
    for m in d.values():
        if i-m >=0 and dp[i-m] >= 0:
            dp[i] = max(dp[i], dp[i-m] + 1) 


# 最大の数値を求める
# 大きい桁から考える
# dp[n] = dp[n-k] + 1 なら、本数kの数値を残りの桁の最大桁として使える
desc_d = sorted(d.items(), key = lambda x: x[0], reverse=True)
s = ''
r = N
for i in range(dp[N]):
    for k, v in desc_d:
        # 残りの本数が足りるか
        if r < v:
            continue

        # この数値を使うことができるか
        if dp[r] == dp[r-v] + 1:
            s += str(k)
            r -= v
            break

print(s)

Submission status: Accepted

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

A = list(map(int,input().split()))
sorted(A)
B =[0,2,5,5,4,5,6,3,7,6]
C =[]
for i in A:
    C.append(B[i])
dp = [-1]*(N+1)
dp[0] = 0
for i in range(N+1):
    for a in range(len(C)):
        if i+C[a]<=N and 0<=dp[i]:
            dp[i+C[a]] = max(dp[i]*10+A[a],dp[i+C[a]])
print(dp[-1])

Submission status: Accepted

Solution code:
import sys

def chk(i,j):
    tmp=[p[i][k] for k in range(M)]
    tmp[j]=p[i][j]+1
    for k in range(M-1,-1,-1):
        if tmp[k] > p[i+x[j]][k] :
            p[i+x[j]]=[tmp[k] for k in range(M)]

N,M=map(int,input().split())
x=[0,2,5,5,4,5,6,3,7,6]
a=list(map(int,input().split()))
a.sort()
b=[]
for i in range(M):
    for j in range(M):
        if x[a[j]]==x[a[i]]: tmp=j
    b.append(a[tmp]) 

a=list(set(b))
a.sort()
M=len(a)
x=[ x[a[i]] for i in range(M) ]

p=[-100 for i in range(N+10)]
p[0]=0
for i in range(N):
    if p[i]>-1:
        for j in range(M):
            p[i+x[j]]=max(p[i+x[j]],p[i]+1)

ans=""
while N>0:
    for j in range(M-1,-1,-1):
        if p[N]==p[N-x[j]]+1:
            ans+=str(a[j])
            N-=x[j]
            break
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
from copy import deepcopy

from bisect import bisect_left as bl

N,M=map(int,input().split())
n=N
A=list(map(int,input().split()))
dic={1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}
dict=defaultdict(int)
list=[]
L=[]
for key in range(9,0,-1):
    if key in A:
        if dic[key] in dict.values():
            continue
        dict[key]=dic[key]
        list.append([key,dic[key]])
        L.append(key)
list.sort(key=lambda x:x[0],reverse=True)
cost=[]
for i in list:
    cost.append(i[1])
num=len(dict.keys())

dp=[[-1 for i in range(num+1)] for j in range(N+1)]
dp[0]=[0]*(num+1)
#dp[i] N=iでの最大値
Non=[-1]*(num+1)
for i in range(N):
    ini=[]
    for j in range(num):
        if i+1-cost[j]>=0 and dp[i+1-cost[j]]!=Non:
            a=dp[i+1-cost[j]][:]
            a[j+1]+=1
            a[0]+=1
            ini.append(a)
    if ini:
        dp[i+1]=max(ini)
s=""


for l in L:
    for i in range(num):
        key,cost=list[i]
        if l==key:
            s+=str(key)*dp[N][i+1]

print(s)

Submission status: Accepted

Solution code:
n,m = [int(i) for i in input().split()]
a = list(map(int,input().split()))

import sys
sys.setrecursionlimit(50000)

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

dig = [0] * (n+1)

inf = 10**9


for i in range(1, n + 1):
    lst = []
    for j in range(len(a)):
        num = a[j]
        mat = match[num]
        bef = i - mat
        if bef >= 0:
            if bef == 0:
                lst.append(dig[bef])
            else:
                if dig[bef] > 0:
                    lst.append(dig[bef])
        if lst:
            dig[i] = max(lst) + 1


ans = ""


def dp(i):
    k = -1
    if i == 0:
        return
    global ans
    maxi = 0
    for j in range(len(a)):
        num = a[j]
        mat = match[num]
        bef = i - mat
        if dig[i] == 1:
            if bef == 0:
                maxi = max(maxi, num)
                k = 0
        else:
            if bef >= 0:
                if dig[bef] == dig[i] - 1:
                    if num > maxi:
                        maxi = num
                        k = bef
    ans += str(maxi)
    if k >= 0:
        dp(k)


dp(n)
print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
a = sorted(list(map(int,input().split())), reverse=True)
match = [[0,0], [1,2], [2,5], [3,5], [4,4], [5,5], [6,6], [7,3], [8,7], [9,6]]

value = []
cost = []
for i in range(len(a)):
        value.append(a[i])
        cost.append(match[a[i]][1])

dp = ["0"]*(n+1)
dp[0] = ""
for i in range(1,n+1):
    for j in range(len(value)):
        tmp_dp_i = 0
        if i - cost[j] >= 0:
            if i - cost[j] >= 0 and dp[i - cost[j]] != "0":
                tmp_dp_i = str(value[j]) + dp[i-cost[j]]
                if len(dp[i]) < len(tmp_dp_i):
                    dp[i] = tmp_dp_i
                elif dp[i] < tmp_dp_i:
                    dp[i] = tmp_dp_i
print(dp[n])

Submission status: Accepted

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

Matches = {num: c for num, c in zip([1, 2, 3, 4, 5, 6, 7, 8, 9], [2, 5, 5, 4, 5, 6, 3, 7, 6])}
dp = [-1 for _ in range(N + 1)]
dp[0] = 0
for a in sorted(A, reverse=True):
    c = Matches[a]
    for i in range(N - c + 1):
        if dp[i] == -1:
            continue
        dp[i+c] = max(dp[i+c], dp[i] * 10 + a)

print(dp[N])

Submission status: Accepted

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

import sys
INT_MIN = sys.maxsize * -1
match = [-100,2,5,5,4,5,6,3,7,6]
CHOICES = []
for i in A:
    if (i == 6) and (9 in A):
        continue
    if (i == 3) and (5 in A):
        continue
    if (i == 2) and (3 in A or 5 in A):
        continue
    CHOICES.append([i, match[i]])
CHOICES.sort(reverse=True)

ans = [0]
#print(CHOICES)
for i in range(1,N+1):
    ans.append(INT_MIN)
    for c in CHOICES:
        #if  i - c[1] == 0:
        #    ans[i] = max(ans[i], int(str(c[0])))
        #elif i - c[1] >= 0 and ans[i - c[1]] != INT_MIN:
        #    ans[i] = max(ans[i], int(str(c[0]) + str(ans[i - c[1]])))

        if i - c[1] >= 0 and ans[i - c[1]] != INT_MIN:
            ans[i] = max(ans[i], c[0] + ans[i - c[1]] * 10)

print(ans[N])

Submission status: Accepted

Solution code:
INF = 2**50
def solve(n, m, a):
    c = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
    dp = [-INF] * (n+10)
    dp[0] = 0
    for d in range(n+1):
        for i in range(m):
            nd = d + c[a[i]]
            dp[nd] = max(dp[nd], 10*dp[d] + a[i])
    return dp[n]

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

Submission status: Accepted

Solution code:
import sys 
RESOURCE_DICT = dict([(k,v) for k,v in zip(range(1,10),[2,5,5,4,5,6,3,7,6])])

def get_input():
    N,M = [ int(_) for _ in input().split()]
    A = [int(_) for _ in input().split()]
    return N,M,A


def solve(N,M,A):
    sorted_A = sorted(A)[::-1]
    dp = fill_dp(N,sorted_A)
    array = find_array(dp,N,sorted_A)
    return "".join(map(str,array))

def fill_dp(N,A):
    dp = [ -100*N for _ in range(N+1)]
    dp[0] = 0
    for i in range(1,N+1):
        fill(A,dp,i,N)
    return dp

def fill(A,dp,n,N):
    cand = [ dp[n-RESOURCE_DICT[num]]+1 for num in A if n - RESOURCE_DICT[num] >= 0 ]
    dp[n] = max(cand) if len(cand) > 0  else -100*N

def find_array(dp,N,sorted_A):
    array = []
    current_n = N
    for _ in range(dp[N]):
        for number in sorted_A:
            if current_n-RESOURCE_DICT[number] >= 0  and dp[current_n-RESOURCE_DICT[number]] == dp[current_n]-1:
                array.append(number)
                current_n -= RESOURCE_DICT[number]
                break
    return array


if __name__ =="__main__":
    N,M,A = get_input()
    ans = solve(N,M,A)
    print(ans)

Submission status: Accepted

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

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

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

for i in range(1, N + 1):
    # i 本で表せる最大の桁数を dp に求める
    l = [dp[i - V[j]] + 1 for j in A if i - V[j] >= 0]
    if l:
        dp[i] = max(l)
# 各桁の最大値を求めていく
n = N
while n > 0:
    for j in A:
        if n - V[j] < 0: continue
        if dp[n] == dp[n - V[j]] + 1:
            print(j, end='')
            n = n - V[j]
            break
print()

Submission status: Accepted

Solution code:
def solve(n, a_list):
    numbers_map = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
    usable_map = {}
    for a in a_list:
        usable_map[a] = numbers_map[a]

    # 1-origin 桁数を保存 -infで初期化
    inf = 1000
    dp = [0] + [-inf for _ in range(n)]
    for value in usable_map.values():
        if value <= n:
            dp[value] = 1

    # time O(NM)
    for cost in range(1, n + 1):
        for value in usable_map.values():
            if cost - value < 0 or dp[cost - value] == 0:
                continue
            dp[cost] = max(
                dp[cost],
                dp[cost - value] + 1
            )

    # time O(M log(M))
    buff = []
    digit = n
    reverse_usable_list = sorted(usable_map.items(), reverse=True)
    while True:
        for num, value in reverse_usable_list:
            if digit - value < 0 or dp[digit] - 1 != dp[digit - value]:
                continue
            buff.append(str(num))
            digit -= value
            break
        if digit <= 0:
            break

    return "".join(buff)


def main():
    n, m = map(int, input().split())
    a_list = list(map(int, input().split()))

    ans = solve(n, a_list)
    print(ans)


main()

Submission status: Accepted

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

# 数字kに対するマッチ必要本数を返す
def num(k):
    costs = [2, 5, 5, 4, 5, 6, 3, 7, 6]
    return costs[k-1]

# 動的計画法
# dp(i) := i本の最大桁数(i = 0,1,...,N)
# constructor
inf = 1000
# -infに設定しないと数字の選択時にミスる
dp = [-inf for _ in range(N+1)]
dp[0] = 0

cost_list = [num(k) for k in A]
for i in range(1, N+1):
    for cost in cost_list:
        if i - cost < 0:
            pass
        else:
            temp = dp[i - cost] + 1
            dp[i] = max(dp[i], temp)

ans = ''
many = N
for d in range(dp[N]): # 各桁
    for k in sorted(A, reverse=True):
        if many - num(k) < 0:
            pass
        else:
            if dp[many - num(k)] == dp[many] - 1:
                ans += str(k)
                many -= num(k)
                break
            else:
                pass

print(int(ans))

Submission status: Accepted

Solution code:
def solve(string):
    n, m, *a = map(int, string.split())
    needs = {i + 1: n for i, n in enumerate(map(int, "2 5 5 4 5 6 3 7 6".split()))}
    if 2 in a and 5 in a or 2 in a and 3 in a:
        a.remove(2)
    if 3 in a and 5 in a:
        a.remove(3)
    if 6 in a and 9 in a:
        a.remove(6)
    a = sorted(a, key=lambda x: needs[x])
    index = 0
    base = str(a[0]) * (n // needs[a[0]])
    n %= needs[a[0]]
    while n > 0:
        use = [_b for _b in a if needs[_b] <= needs[a[0]] + n]
        if len(use) == 1:
            base = base[:-1]
            n += needs[a[0]]
            continue
        flag = max(use) == a[0]
        tmp_n = use[-1] if flag else max(use)
        tmp_c = n // (needs[tmp_n] - needs[a[0]])
        if flag:
            base = base[:-tmp_c] + str(tmp_n) * tmp_c
        else:
            base = base[:index] + str(tmp_n) * tmp_c + base[index + tmp_c:]
            index += tmp_c
        n -= (needs[tmp_n] - needs[a[0]]) * tmp_c
    return base


if __name__ == '__main__':
    print(solve('\n'.join([input(), input()])))

Submission status: Accepted

Solution code:
def solve(string):
    n, m, *a = map(int, string.split())
    needs = {i + 1: n for i, n in enumerate(map(int, "2 5 5 4 5 6 3 7 6".split()))}
    if 2 in a and 5 in a or 2 in a and 3 in a:
        a.remove(2)
    if 3 in a and 5 in a:
        a.remove(3)
    if 6 in a and 9 in a:
        a.remove(6)
    a = sorted(a, key=lambda x: needs[x])
    index = 0
    base = str(a[0]) * (n // needs[a[0]])
    n %= needs[a[0]]
    while n > 0:
        use = [_b for _b in a if needs[_b] <= needs[a[0]] + n]
        if len(use) == 1:
            base = base[:-1]
            n += needs[a[0]]
            continue
        flag = max(use) == a[0]
        tmp_n = use[-1] if flag else max(use)
        diff = needs[tmp_n] - needs[a[0]]
        tmp_c = n // diff
        if flag:
            base = base[:-tmp_c] + str(tmp_n) * tmp_c
        else:
            base = base[:index] + str(tmp_n) * tmp_c + base[index + tmp_c:]
            index += tmp_c
        n -= diff * tmp_c
    return base


if __name__ == '__main__':
    print(solve('\n'.join([input(), input()])))

Submission status: Accepted

Solution code:
def solve(string):
    n, m, *a = map(int, string.split())
    needs = {i + 1: n for i, n in enumerate(map(int, "2 5 5 4 5 6 3 7 6".split()))}
    if 2 in a and (3 in a or 5 in a):
        a.remove(2)
    if 3 in a and 5 in a:
        a.remove(3)
    if 6 in a and 9 in a:
        a.remove(6)
    b = sorted(a, key=lambda x: needs[x])
    index = 0
    base = str(b[0]) * (n // needs[b[0]])
    n %= needs[b[0]]
    while n > 0:
        use = [_b for _b in b if needs[_b] <= needs[b[0]] + n]
        if len(use) == 1:
            base = base[:-1]
            n += needs[b[0]]
            continue
        flag = max(use) == b[0]
        tmp_n = use[-1] if flag else max(use)
        tmp_c = n // (needs[tmp_n] - needs[b[0]])
        if flag:
            base = base[:-tmp_c] + str(tmp_n) * tmp_c
        else:
            base = base[:index] + str(tmp_n) * tmp_c + base[index + tmp_c:]
            index += tmp_c
        n -= (needs[tmp_n] - needs[b[0]]) * tmp_c
    return base


if __name__ == '__main__':
    print(solve('\n'.join([input(), input()])))

Submission status: Accepted

Solution code:
def solve(string):
    n, m, *a = map(int, string.split())
    needs = {i + 1: n for i, n in enumerate(map(int, "2 5 5 4 5 6 3 7 6".split()))}
    if 2 in a and 5 in a or 2 in a and 3 in a:
        a.remove(2)
    if 3 in a and 5 in a:
        a.remove(3)
    if 6 in a and 9 in a:
        a.remove(6)
    b = sorted(a, key=lambda x: needs[x])
    index = 0
    base = str(b[0]) * (n // needs[b[0]])
    n %= needs[b[0]]
    while n > 0:
        use = [_b for _b in b if needs[_b] <= needs[b[0]] + n]
        if len(use) == 1:
            base = base[:-1]
            n += needs[b[0]]
            continue
        flag = max(use) == b[0]
        tmp_n = use[-1] if flag else max(use)
        tmp_c = n // (needs[tmp_n] - needs[b[0]])
        if flag:
            base = base[:-tmp_c] + str(tmp_n) * tmp_c
        else:
            base = base[:index] + str(tmp_n) * tmp_c + base[index + tmp_c:]
            index += tmp_c
        n -= (needs[tmp_n] - needs[b[0]]) * tmp_c
    return base


if __name__ == '__main__':
    print(solve('\n'.join([input(), input()])))

Submission status: Accepted

Solution code:
def solve(string):
    n, m, *a = map(int, string.split())
    needs = {i + 1: n for i, n in enumerate(map(int, "2 5 5 4 5 6 3 7 6".split()))}
    if 2 in a and 5 in a:
        a.remove(2)
    if 3 in a and 5 in a:
        a.remove(3)
    if 2 in a and 3 in a:
        a.remove(2)
    if 6 in a and 9 in a:
        a.remove(6)
    b = sorted(a, key=lambda x: needs[x])
    index = 0
    base = str(b[0]) * (n // needs[b[0]])
    n %= needs[b[0]]
    while n > 0:
        use = [_b for _b in b if needs[_b] <= needs[b[0]] + n]
        if len(use) == 1:
            base = base[:-1]
            n += needs[b[0]]
        elif max(use) == b[0]:
            tmp_n = use[-1]
            tmp_c = n // (needs[tmp_n] - needs[b[0]])
            base = base[:-tmp_c] + str(tmp_n) * tmp_c
            n -= (needs[tmp_n] - needs[b[0]]) * tmp_c
        else:
            tmp_n = max(use)
            tmp_c = n // (needs[tmp_n] - needs[b[0]])
            base = base[:index] + str(tmp_n) * tmp_c + base[index + tmp_c:]
            n -= (needs[tmp_n] - needs[b[0]]) * tmp_c
            index += tmp_c
    return base


if __name__ == '__main__':
    print(solve('\n'.join([input(), input()])))

Submission status: Accepted

Solution code:
n, _ = map(int, input().split())
numbers = list(map(int, input().split()))
reqs = {
    1: 2,
    2: 5,
    3: 5,
    4: 4,
    5: 5,
    6: 6,
    7: 3,
    8: 7,
    9: 6,
}

memo = {}


def max_counts(a, b):
    """
    a と b 大きい方を返す
    :param a: solve() の返り値
    :param b: solve() の返り値
    :return:
    """
    if a is None:
        return b
    if b is None:
        return a
    # 桁数は大きいほうが大きい
    if sum(a) > sum(b):
        return a
    if sum(a) < sum(b):
        return b
    # 桁数が同じなら、大きい数字の多いほうが大きい
    for a_c, b_c in zip(reversed(a), reversed(b)):
        if a_c > b_c:
            return a
        if a_c < b_c:
            return b
    return a


# https://atcoder.jp/contests/abc118/submissions/4911280
# DP 版
memo[0] = [0 for _ in range(10)]
for i in range(n):
    if i in memo:
        for num in numbers:
            next_n = i + reqs[num]
            next_counts = memo[next_n] if next_n in memo else None
            if next_n <= n:
                memo[next_n] = max_counts(
                    next_counts,
                    memo[i][:num] + [memo[i][num] + 1] + memo[i][num + 1:]
                )

ans = ''
for num in range(9, 0, -1):
    for _ in range(memo[n][num]):
        ans += str(num)
print(ans)

Submission status: Accepted

Solution code:
#coding:utf-8
N,M=map(int,raw_input().split())
A=map(int,raw_input().split())
dp=[-1 for i in range(10**4 + 1)]
Cost={(i+1):v for i,v in enumerate([2,5,5,4,5,6,3,7,6])}

for a in A:
    dp[Cost[a]] = max(dp[Cost[a]], a)

for n in range(2, N+1):
    for a in A:
        if n-Cost[a]>=0 and dp[n-Cost[a]] != -1:
            dp[n] = max(dp[n], dp[n-Cost[a]] * 10 + a)
print(dp[n])

Submission status: Accepted

Solution code:
#coding:utf-8
N,M=map(int,raw_input().split())
A=map(int,raw_input().split())
dp=[-1 for i in range(10**4 + 1)]
Cost={(i+1):v for i,v in enumerate([2,5,5,4,5,6,3,7,6])}

for a in A:
    dp[Cost[a]]=1
for n in range(2,N+1):
    for a in A:
        if n-Cost[a]>=0 and dp[n-Cost[a]] != -1:
            dp[n]=max(dp[n], dp[n-Cost[a]]+1)
k=dp[N]
n=N
buf=[]
for i in range(dp[N]-1):
    b=-1
    for a in A:
        if n-Cost[a]>=0 and dp[n-Cost[a]] == k-1:
            b=max(b,a)
    k-=1
    n-=Cost[b]
    buf.append(b)
b=-1
for a in A:
    if Cost[a] == n:
        b=max(b,a)
buf.append(b)   
print("".join(map(str,buf)))

Submission status: Accepted

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

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

for i in range(N+1):
    for a in A:
        if i-cost[a-1] < 0 or dp[i-cost[a-1]] < 0:
            continue
        if dp[i-cost[a-1]]*10 + a > dp[i]:
            dp[i] = dp[i-cost[a-1]]*10 + a
print(dp[N])

Submission status: Accepted

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


def solve(N: int, M: int, A: "List[int]"):
    costs = [10**18, 2, 5, 5, 4, 5, 6, 3, 7, 6]
    cand = [(i, costs[i]) for i in A]
    cand.sort(reverse=True)
    digits = [-1 * 10**16 for i in range(N+1)]
    digits[0] = 0
    for i in range(1, N+1):
        r = -1 * 10**16
        for c in cand:
            if i - c[1] >= 0:
                r = max(r, digits[i - c[1]] + 1)
        digits[i] = r
    digit = digits[N]
    lastCost = N
    result = 0
    # print(digits)
    for i in range(digit):
        for c in cand:
            if lastCost - c[1] >= 0 and digits[lastCost - c[1]] == digits[lastCost] - 1:
                result = result*10 + c[0]
                lastCost = lastCost - c[1]
                # print(f"lastCost:{lastCost} result:{c[0]} cost:{c[1]}")
                break
    print(result)
    return


# Generated by 1.1.3 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(M)]  # type: "List[int]"
    solve(N, M, A)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
matches = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
n, m = map(int, input().split())
alist = list(map(int, input().split()))
alist.sort(reverse = True)

dp = [-1 for _ in range(n+1)]
dp[0] = 0
for a in alist:
    match = matches[a]
    for i in range(n - match + 1):
        if dp[i] == -1:
            continue
        dp[i + match] = max(dp[i+match], dp[i] * 10 + a)
        
print(dp[-1])

Submission status: Accepted

Solution code:
import sys

ns = lambda: sys.stdin.readline().rstrip()
ni = lambda: int(ns())
nm = lambda: map(int, sys.stdin.readline().split())
nms = lambda: map(str, sys.stdin.readline().split())
nl = lambda: list(nm())

n, m = nm()
a = nl()
lis = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [-1 for _ in range(n + 1)]
dp[0] = 0
for i in range(1, n + 1):
    for j in a:
        if i - lis[j] >= 0:
            dp[i] = max(dp[i], dp[i - lis[j]] * 10 + j)
print(dp[n])

Submission status: Accepted

Solution code:
B = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
N, M = map(int, input().split())
A = list(map(int, input().split()))
dic = {i: B[i] for i in A}
dp = [0] * (N + 1)
for i in range(N + 1):
    for j in A:
        if i>0 and dp[i]==0:
            break
        if i + dic[j] <= N:
            dp[i + dic[j]] = max(dp[i] * 10 + j, dp[i + dic[j]])
print(dp[N])

Submission status: Accepted

Solution code:
import math

n,m = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]

#値と本数のセット（本数が少ない順かつ値が大きい順）
set = [[1,2],[7,3],[4,4],[5,5],[3,5],[2,5],[9,6],[6,6],[8,7]]

#同じ本数で値が小さい数字を使うことはない
if 2 in a:
  if 3 in a or 5 in a:
    a.remove(2)
    m -= 1

if 3 in a:
  if 5 in a:
    a.remove(3)
    m -= 1
  
if 6 in a:
  if 9 in a:
    a.remove(6)
    m -= 1

#上記の処理を施した上で与えられたaの数と本数の組み合わせを抽出
exist_set = [i for i in set if i[0] in a]

#本数の最大値。あとで使用
max_honsu = max([i[1] for i in exist_set])

#あとでexist_setからnumを除いた数字による探索を行うため
m -= 1

#最大桁数のうち値が大きいもの
max_keta = 0
ans_kouho = []

for exist_one in exist_set:
  keta_tmp = n//exist_one[1]
  num_tmp = exist_one[0]
  amari_tmp = n % exist_one[1]
  honsu_tmp = exist_one[1]
  
  ###print(keta_tmp,num_tmp)
  
  #余りが0出ない場合、aの本数の最大値は不採用（余りを調整できない）
  if amari_tmp != 0 and honsu_tmp == max_honsu:
    continue
  if keta_tmp >= max_keta:
    keta = keta_tmp
    num = num_tmp
    amari = amari_tmp
    honsu = honsu_tmp

    #余り0ならちょうどなので終了
    if amari == 0:
      ans_kouho.append(int(str(num)*keta))
      max_keta = keta
      continue
      
    #以下余りを調整

    #変更する値は必ずnum以外だからexist_setからnumを削除
    exist_yet = [inc for inc in exist_set if inc[0] != num]

    #1桁ずつ値を変更し、あまりを0にできるか調査
    for keta_num in range(1,min(max_honsu,keta+1)):
      
      kouho = []

      #bit全探索
      #候補に使用しないも追加
      bit = math.ceil(math.log2(m+1))
      for all_bit in range((2**m)*keta_num):
        change = []
        nokori = amari + honsu * keta_num
        for bit_conf in range(keta_num):
          bit_index =  (all_bit >> bit_conf*bit) & (2**m-1)

          #bit_indexは0~mだからm+1以上は終了
          if bit_index > m:
            break
            
          #使用しないに相当
          if bit_index == m:
            change.append(0)
            continue

          #bit_indexに従い数字を記録、残りの本数を減らす
          change.append(exist_yet[bit_index][0])
          nokori -= exist_yet[bit_index][1]

          if nokori < 0:
            break
            
        if bit_index > m or nokori < 0:
          continue

        #残りが0ならちょうど使い切る。数の組み合わせを候補に追加
        if nokori == 0:
          kouho.append(change)
      
      #候補から値の大きいものを抜き出す
      if len(kouho) != 0:

        #keta-del_lenがnumの数
        del_len = len(kouho[0])

        #0を削除
        kouho = [[inc_1 for inc_1 in inc_2 if inc_1 != 0] for inc_2 in kouho]

        #0を除いたときの最大桁が候補
        max_len = max([len(inc) for inc in kouho])
        kouho = [inc for inc in kouho if len(inc) == max_len]
        
        max_keta = keta - del_len + max_len

        #候補を降順に並び替え
        kouho = [sorted(kouho_one,reverse=True) for kouho_one in kouho]

        #同じパターンを削除
        kouho_tmp = []
        for kouho_one in kouho:
          if kouho_one not in kouho_tmp:
            kouho_tmp.append(kouho_one)
        kouho = kouho_tmp

        #最大候補の抽出
        if len(kouho) != 1:
          for kouho_one in range(len(kouho[0])):
            max_i = max([inc[kouho_one] for inc in kouho])
            kouho = [inc for inc in kouho if inc[kouho_one] == max_i]
        kouho = kouho[0]

        ans = [num]*(keta-del_len) + kouho
        ans.sort(reverse=True)
        ans_str = ''
        for ans_one in ans:
          ans_str += str(ans_one)
        ans_kouho.append(int(ans_str))

ans_kouho.sort()
###print(ans_kouho)
print(ans_kouho[-1])

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
a = [int(i) for i in input().split()]
a.sort(reverse=1)
num = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]

dp = [0] * (N+1)

for i in range(1, N+1):
    now = - 10 ** 9
    for aa in a:
        if i - num[aa] >= 0:
            now = max(now, dp[i-num[aa]]+1)
    dp[i] = now

answer = ''
for i in range(dp[-1]):
    for aa in a:
        if N >= num[aa]:
            if dp[N-num[aa]] == dp[N] - 1:
                answer += str(aa)
                N -= num[aa]
                break
print(answer)

Submission status: Accepted

Solution code:
n,m= map(int,input().split())
A = list(map(int,input().split()))
cost = [0,2,5,5,4,5,6,3,7,6]
dp =[-1]*10010
dp[0]=0
for i in range(1,n+1):
    for a in A:
        if i - cost[a] >= 0:
            dp[i] = max(dp[i],a+dp[i-cost[a]]*10)
print(dp[n])

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))
 
need = [0,2,5,5,4,5,6,3,7,6]
 
dp = [-1] * (N + 1)
dp[0] = 0
 
for i in range(N + 1):
        for a in A:
                if i + need[a] <= N:
                        dp[i + need[a]] = max(dp[i + need[a]], dp[i] * 10 + a)
 
print(dp[-1])

Submission status: Accepted

Solution code:
# coding: utf-8

import sys
input = sys.stdin.readline

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

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

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

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

print(dp[-1])

Submission status: Accepted

Solution code:
# coding: utf-8

import sys
input = sys.stdin.readline

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

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

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

for num in A:
        required = need[num]

        for i in range(N - required + 1):
                if dp[i] == -1:
                        continue
                
                dp[i + required] = max(dp[i + required], dp[i] * 10 + num)

print(dp[-1])

Submission status: Accepted

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

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

def solve(n: int, m: int, A: "List[int]"):
    dp = [-1] * (n + 1)
    dp[0] = 0
    A.sort(reverse=True)
    for c in A:
        for i in range(n + 1):
            if i - a[c] >= 0 and dp[i - a[c]] >= 0:
                dp[i] = max(dp[i], dp[i - a[c]] * 10 + c)
    print(dp[n])
    return



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