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:
import sys
sys.setrecursionlimit(10 ** 6)

N, M = map(int, input().split())
A = list(map(int, input().split()))
num = [2, 5, 5, 4, 5, 6, 3, 7, 6]
INF = 10 ** 8

for i in range(9):
    if i + 1 not in A:
        num[i] = INF

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

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

ans = ''
rest = N
for i in range(dp[N]):
    t = 0
    for j in range(8, -1, -1):
        k = rest - num[j]
        if k >= 0:
            if dp[rest - num[j]] == dp[rest] - 1:
                t = max(t, j + 1)
    ans += str(t)
    rest -= num[t - 1]

print(int(ans))

Submission status: Accepted

Solution code:
N,M=[int(x) for x in input().split()]
X=[0,2,5,5,4,5,6,3,7,6]
#    1,2,3,4,5,6,7,8,9

A=[int(x) for x in input().split()]



ANS=[0]
for i in range(1,N+1):
	ans=0
	for j in A:
		if i==X[j]:
			ans=max(j,ans)
		elif i>=X[j]:
			temp=ANS[i-X[j]]
			if temp!=0:

				ans=max(ans,10*temp+j)
		
		#print(ans)
	ANS.append(ans)
print(ANS[-1])

Submission status: Accepted

Solution code:
#coding: utf-8
import math
import heapq
import bisect
import numpy as np
#from scipy.misc import comb

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

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

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

print(dp[N])

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    N, M = LI()
    A = LI()
    num2match = {
        1: 2,
        2: 5,
        3: 5,
        4: 4,
        5: 5,
        6: 6,
        7: 3,
        8: 7,
        9: 6,
    }
    dp = ['' for _ in range(N+1)]
    for a in A:
        match_need = num2match[a]
        if 0 <= match_need <= N:
            dp[match_need] = max(str(dp[match_need]), str(a))
    for i in range(N+1):
        for a in A:
            match_need = num2match[a]
            if i - match_need > 0:
                if dp[i-match_need] == '':
                    continue
                old = dp[i]
                new = str(a) + dp[i-match_need]
                if len(old) > len(new):
                    dp[i] = old
                elif len(new) > len(old):
                    dp[i] = new
                else:
                    dp[i] = max(old, new)
    print(dp[N])
main()

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = float('INF')
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, m = LI()
A = LI()
L = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
match_set = {L[a] for a in A}
dp = [-INF] * (n + 1)
dp[0] = 0
for i in range(n + 1):
    for s in match_set:
        if i - s >= 0:
            dp[i] = max(dp[i - s] + 1, dp[i])

D = defaultdict(int)
for a in A:
    D[L[a]] = max(D[L[a]], a)

kv = sorted(D.items())
digit = dp[n]
ans = ''
while n:
    max_num = 0
    for cost, num in kv:
        if n - cost >= 0 and dp[n - cost] == digit - 1:
            if num > max_num:
                max_num = num
                c = cost
    ans += str(max_num)
    digit -= 1
    n -= c


print(ans)

Submission status: Accepted

Solution code:
n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
costs = [2, 5, 5, 4, 5, 6, 3, 7, 6]
cs = {m: costs[m - 1] for m in a}
INF = 10 ** 9
dp = [0]

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

digits = list(cs.keys())
digits.sort(reverse=True)
num = n
ans = []
for _ in range(dp[n]):
    for digit in digits:
        if num >= cs[digit] and dp[num - cs[digit]] != -INF and dp[num - cs[digit]] == dp[num] - 1:
            ans.append(str(digit))
            num -= cs[digit]
            break
print("".join(ans))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input():
    return sys.stdin.readline().rstrip()

def main():
    N,M=map(int,input().split())
    A=list(map(int,input().split()))
    A.sort()
    for a in A:
        if a==3:
            try:
                A.remove(2)
            except:
                pass
        elif a==5:
            try:
                A.remove(2)
            except:
                pass
            try:
                A.remove(3)
            except:
                pass
        elif a==9:
            try:
                A.remove(6)
            except:
                pass
    d={1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}
    l=[d[x] for x in A]
    dp=[[0]*(N+1) for _ in range(len(l)+1)]
    prev_w=[[0]*(N+1) for _ in range(len(l)+1)]
    real_w=[[0]*(N+1) for _ in range(len(l)+1)]
    for num in range(len(l)):
        for w in range(N+1):
            if w>=l[num]:
                if dp[num+1][w]<dp[num+1][w-l[num]]+1 and real_w[num+1][w-l[num]]+l[num]==w:
                    dp[num+1][w]=dp[num+1][w-l[num]]+1
                    prev_w[num+1][w]=w-l[num]
                    real_w[num+1][w]=w
            if dp[num+1][w]<dp[num][w]:
                dp[num+1][w]=dp[num][w]
                prev_w[num+1][w]=w
                real_w[num+1][w]=w
    l2=[]
    cur_w=N
    for num in range(len(l)-1,-1,-1):
        while True:
            if prev_w[num+1][cur_w]==cur_w-l[num]:
                l2.append(str(A[num]))
                cur_w=prev_w[num+1][cur_w]
            else:
                cur_w=prev_w[num+1][cur_w]
                break
    print(''.join(l2))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N,M = MI()
    A=sorted(LI(), reverse=True)
    num_cost = {
        1:2,
        2:5,
        3:5,
        4:4,
        5:5,
        6:6,
        7:3,
        8:7,
        9:6
    }


    dp = [-inf]*(N+1) #dp[i]:ちょうどi本使ったときの最大桁数
    dp[0] = 0

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

    ans = []
    while N:
        for a in A:
            cost = num_cost[a]
            if N-cost>=0 and dp[N-cost]==dp[N]-1: #aを使って最大桁数で作れる
                ans.append(a)
                N-=cost
                break
    print(*ans,sep="")



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def is_big(x = [0]*10, y = [0]*10):
    if sum(x) > sum(y):
        return True
    if sum(x) < sum(y):
        return False
    for i in range(0,10)[::-1]:
        if x[i] > y[i]:
            return True
        if y[i] > x[i]:
            return False
    return True
  
n,m = map(int,input().split())
a = sorted(list(map(int,input().split())))
#print(a)
d = [0]*8
b = []
L1 = [1,7,4,2,3,5,6,9,8]
L2 = [2,3,4,5,5,5,6,6,7]
for i in range(9):
  if L1[i] in a:
    d[L2[i]] = L1[i]
    if L2[i] not in b:
      b.append(L2[i])
#print(d)
#print(b)
p = []
for i in range(n+1):
  p.append([-1,0,0,0,0,0,0,0,0,0])
  
p[0][0] = 0
for i in range(1,n+1):
  for t in b:
    if i-t <0 or p[i-t][0] == -1: 
      continue
    q = p[i-t][:]
    q[d[t]] += 1
    if is_big(q,p[i]):
      p[i] = q

a = ""
for i in range(10)[::-1]:
  a += str(i)*p[n][i]
print(a)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))
d = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
D = {a: d[a] for a in A}
m = min(D.values())
E = {}
for k, v in D.items():
    v -= m
    if v in E:
        E[v] = max(E[v], k)
    else:
        E[v] = k
F = sorted(E.keys(), key=lambda f: (max(0, E[f]-E[0]), f), reverse=True)
F.remove(0)
K = N // m
for k in range(K, 0, -1):
    B = [E[0]] * k
    R = N - k * m
    if not R:
        print("".join(map(str, sorted(B, reverse=True))))
        break
    def rec(r, i, j):
        if i < 0:
            return
        for f in F[j:]:
            if r == f:
                B[i] = E[f]
                print("".join(map(str, sorted(B, reverse=True))))
                exit()
            elif r > f:
                B[i], tmp = E[f], B[i]
                rec(r - f, i - 1, j)
                B[i] = tmp
            j += 1
    rec(R, k-1, 0)

Submission status: Accepted

Solution code:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

N, M = list(map(int, sys.stdin.buffer.readline().split()))
A = list(map(int, sys.stdin.buffer.readline().split()))

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

# dp[i][0]: i 個のマッチ棒を使って作れる整数の最大の桁数
# dp[i][1][-j]: j を何個作るか
dp = [(0, [0] * 9) for _ in range(N + 10)]
for i in range(N):
    d, counts = dp[i]
    if i > 0 and d == 0:
        continue
    for a in A:
        cnts = counts[:]
        cnts[-a] += 1
        dp[i + requires[a]] = max(dp[i + requires[a]], (d + 1, cnts))
ans = ''
for i, cnt in enumerate(dp[N][1]):
    ans += str(9 - i) * cnt
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
A = map(int, input().split())
ok = [0] * 10
for a in A: ok[a] = 1

dp = [-1] * (N + 1)
dp[0] = 0
cost = [-1, 2, 5, 5, 4, 5, 6, 3, 7, 6]

for i in range(N):
    for num in range(1, 10):
        c = cost[num]
        if ok[num] == 0 or i + c > N: continue
        dp[i+c] = max(dp[i+c], dp[i] * 10 + num)

ans = dp[N]
print(ans)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
A = list(map(int,input().split()))
weight = [0,2,5,5,4,5,6,3,7,6]
dp=[-1]*(N+1)
dp[0] = 0

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

print(dp[-1])

Submission status: Accepted

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

C = [0,2,5,5,4,5,6,3,7,6]
dp = [-1]*(n+1)
dp[0] = 0

for n_i in range(n):
  for a_i in A:
    if n_i+C[a_i]<=n:
      dp[n_i+C[a_i]] = max(dp[n_i+C[a_i]], dp[n_i]*10+a_i)
      
print(dp.pop())

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))
W = [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 + W[a] < N + 1:
            dp[i + W[a]] = max(dp[i + W[a]], dp[i]*10 + a)
print(dp[N])

Submission status: Accepted

Solution code:
def p_d():
    n, m = map(int, input().split())
    a = map(int, input().split())
    c = [2, 5, 5, 4, 5, 6, 3, 7, 6]
    inf = 10 ** 9
    costs = {m: c[m - 1] for m in a}
    # dp(i) := ちょうど i 本のマッチ棒を使って、条件を満たす整数を作るときの最大桁数
    dp = [0]

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

    digits = list(costs.keys())
    digits.sort(reverse=True)
    num = n
    result = []
    for _ in range(dp[n]):
        for digit in digits:
            if num >= costs[digit] and dp[num - costs[digit]] != -inf and dp[num - costs[digit]] == dp[num] - 1:
                result.append(str(digit))
                num -= costs[digit]
                break
    print("".join(result))


if __name__ == '__main__':
    p_d()

Submission status: Accepted

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


if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
A=list(map(int,input().split()))
w=[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+w[a]<N+1:
      dp[i+w[a]]=max(dp[i+w[a]],dp[i]*10+a)
      
print(dp[-1])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

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

def compare(a, b):
    if a is None:
        return b
    if len(a) > len(b):
        return a
    if len(a) < len(b):
        return b
    return max(a, b)

N, M = MAP()
A = LIST()

# dp[i] := マッチをi本使った状態での最大値
dp = [None] * (N+1)
dp[0] = ''
for i in range(N):
    if dp[i] is None:
        continue
    for j in A:
        cnt = tocnt[j]
        if i+cnt <= N:
            dp[i+cnt] = compare(dp[i+cnt], dp[i] + str(j))
print(dp[N])

Submission status: Accepted

Solution code:
match = [0,2,5,5,4,5,6,3,7,6]
n,m=map(int,input().split())
a=list(map(int,input().split()))
dp=[-1]*(n+11451)
dp[0]=0
for i in range(n+1):
    if dp[i]==-1:
        continue
    else:
        for j in a:
            dp[i+match[j]]=max(dp[i+match[j]],dp[i]*10+j)

print(dp[n])

Submission status: Accepted

Solution code:
match = [0,2,5,5,4,5,6,3,7,6]
n,m = map(int,input().split())
a = [int(_) for _ in input().split()]
dp = [-1]*(n+100)
dp[0] = 0
for i in range(n+1):
    if dp[i]== -1:
        continue
    else:
        for j in a:
            dp[i+match[j]]= max(dp[i+match[j]],dp[i]*10+j)
print(dp[n])

Submission status: Accepted

Solution code:
import bisect
N, M = map(int, input().split())
A = list(map(int, input().split()))
num = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
num = [(i, num[i]) for i in range(10) if i in A]
num.sort(key=lambda x: x[0], reverse=True)
num.sort(key=lambda x: x[1])
dp = [0 for i in range(N+1)]
ans = 0
tmp = set()
tmp.add(0)
for i in range(1, N+1):
    for n, k in num:
        if i - k in tmp:
            dp[i] = 1 + dp[i-k]
            tmp.add(i)
            break


num.sort(reverse=True)
tmp = N
ans = []
for i in reversed(range(1, dp[N])):
    for n, k in num:
        if dp[tmp - k] == i:
            ans.append(n)
            tmp -= k
            break
for n, k in num:
    if k == tmp:
        ans.append(n)
        break

ans.sort(reverse=True)
ans = "".join(map(str, ans))
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
aa = reversed(sorted(map(int, input().split())))

t = ['_', 2, 5, 5, 4, 5, 6, 3, 7, 6]

# n 本使ってできる最大の桁数
dp = [-1 for _ in range(n + 1)]
dp[0] = 0

for a in aa:
    for i in range(len(dp)):
        if dp[i] >= 0 and i + t[a] < len(dp):
            dp[i + t[a]] = max(dp[i + t[a]], dp[i] * 10 + a)

print(dp[n])

Submission status: Accepted

Solution code:
import os, sys, re, math
sys.setrecursionlimit(100000)
N,M = list(map(int,input().split(' ')))
A = list(map(int,input().split(' ')))

match = [100,2,5,5,4,5,6,3,7,6]
memo = {}

def doit(m):
    if m in memo:
        return memo[m]
    if m == 0:
        return ""

    ret = None
    for a in A:
        tmp = None
        if m - match[a] >= 0:
            tmp = doit(m - match[a])
            if tmp is not None:
                tmp = str(a) + tmp
                if ret is not None:
                    if len(ret) < len(tmp) or (len(ret) == len(tmp) and tmp > ret):
                        ret = tmp
                else:
                    ret = tmp

    memo[m] = ret
    return ret

print(doit(N))

Submission status: Accepted

Solution code:
inf = 1 << 20
need = -1, 2, 5, 5, 4, 5, 6, 3, 7, 6

n, m = map(int, input().split())
a = map(int, input().split())
d = {need[x]: x for x in sorted(a)}  # sortedで昇順にすることで、同じ本数のとき最大値が残る
e = tuple(sorted(d.items(), key=lambda x: x[1], reverse=True))  # (必要本数,数字)

dp = [-inf] * (n + 1)
dp[0] = 0
# dp[k]:=k本で構成可能な最大桁数

for j in range(1, n + 1):
    dp[j] = max((dp[j - cnt] for cnt, _ in e if j - cnt >= 0), default=-inf) + 1

ret = []
r = dp[n]

curr = n
while r > 0:
    for cnt, num in e:
        if curr - cnt >= 0 and dp[curr - cnt] == r - 1:
            ret.append(num)
            r -= 1
            curr -= cnt
            break

ret.sort(reverse=True)
print(''.join(map(str, ret)))

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
A = list(map(int,input().split()))
weight = [0,2,5,5,4,5,6,3,7,6]
dp = [-1]*(N+1)
dp[0] = 0

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

Submission status: Accepted

Solution code:
#解答例
N,M=map(int,input().split())
A=list(map(int,input().split()))#使える数字の種類
weight=[0,2,5,5,4,5,6,3,7,6]#作るのに何本必要か、また0は作れないので0になっている
dp=[-1]*(N+1)#とりあえずこれくらい確保しておけばok
dp[0]=0#0本では0しか作れない
#dp[i]はちょうどi本で作れる最高の数を入れることにする
for i in range(N+1):#N本あるから、一本ずつ増やしていって最大N本
    if dp[i] == -1:continue
    for a in A:
        if i+weight[a]<N+1:#今あるi本にa本を加えてもN本を超えないか
            dp[i+weight[a]]=max(dp[i+weight[a]],dp[i]*10+a)#今まで作ったi+weight[a]のときのdpの値と、今作ったdp[i]*10+aの値を比べ、大きい方を格納する
                                                           #なぜdp[i]*10+aになるのかに関しては、右から数字を追加していく場合のみを考えることで、重複せずに全通り試せるから#もし一通りもなかった場合、-1が格納されたままになるため問題がない
print(dp[N])

Submission status: Accepted

Solution code:
#解答例
N,M=map(int,input().split())
A=list(map(int,input().split()))#使える数字の種類
weight=[0,2,5,5,4,5,6,3,7,6]#作るのに何本必要か、また0は作れないので0になっている
dp=[-1]*(N+1)#とりあえずこれくらい確保しておけばok
dp[0]=0#0本では0しか作れない
#dp[i]はちょうどi本で作れる最高の数を入れることにする
for i in range(N+1):#N本あるから、一本ずつ増やしていって最大N本
    for a in A:
        if i+weight[a]<N+1:#今あるi本にa本を加えてもN本を超えないか
            dp[i+weight[a]]=max(dp[i+weight[a]],dp[i]*10+a)#今まで作ったi+weight[a]のときのdpの値と、今作ったdp[i]*10+aの値を比べ、大きい方を格納する
                                                           #なぜdp[i]*10+aになるのかに関しては、右から数字を追加していく場合のみを考えることで、重複せずに全通り試せるから
print(dp[N])

Submission status: Accepted

Solution code:
n, m = list(map(int, input().split(' ')))
l = list(map(int, input().split(' ')))
d = {}  # key=match, val=num
d[2] = [1]
d[3] = [7]
d[4] = [4]
d[5] = [5, 3, 2]
d[6] = [9, 6]
d[7] = [8]
enable = [False] * 10
for a in l:
  enable[a] = True
# マッチをk(=2..7)本使う場合の一番大きい値を総当たり
def f(nokori, current):
  if nokori == 0:
    return current
  if nokori < 0:
    return -1
  temps = []
  for key, nums in list(d.items())[::-1]:
    for num in nums:
      if enable[num]:
        if nokori-key != 0 and current % 10 != 0 and current % 10 < num:
          # 98 ok, 89 重複するので最後の桁以外は skip
          continue
        temps.append(f(nokori-key, current*10+num))
        break
  return max(temps)

# 余裕があるうちは一番マッチの本数が少ないモノをヤケクソで詰めまくる
def hoge():
  for key, nums in list(d.items()):
      for num in nums:
        if enable[num]:
          return (num, key)
num, key = hoge()
cs = []
while n > 50:
  n -= key
  cs.append(str(num))

# ヤケクソで詰めたやつと総当たりで調べたマックスを並び替えて辞書順で大きくする
num_ans = str(f(n, 0))
print(''.join(sorted(list(num_ans) + cs)[::-1]))

Submission status: Accepted

Solution code:
NUM = (None, 2, 5, 5, 4, 5, 6, 3, 7, 6)

nSticks, n = map(int, input().split())
a = list(map(int, input().split()))

# maximum value to make using exactly sticks
dp = [0] * (nSticks + 1)
for digit in a:
    if NUM[digit] <= nSticks:
        dp[NUM[digit]] = max(dp[NUM[digit]], digit)
for sticks in range(2, nSticks + 1):
    for digit in a:
        if sticks - NUM[digit] >= 0 and dp[sticks - NUM[digit]] > 0:
            dp[sticks] = max(dp[sticks], dp[sticks - NUM[digit]] * 10 + digit)
print(dp[-1])

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
a = list(map(int, input().split()))
matches = [100, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [""]
for i in range(1, n + 1):
    dp.append(None)
    for d in a:
        m = matches[d]
        if i - m >= 0 and dp[i - m] is not None:
            r = max(dp[i - m] + str(d), str(d) + dp[i - m])
            if dp[i] is None or len(r) > len(dp[i]) or len(r) == len(dp[i]) and r > dp[i]:
                dp[i] = r
print(dp[n])

Submission status: Accepted

Solution code:
n, m = list(map(int, input().split(' ')))
l = list(map(int, input().split(' ')))
d = {}  # key=match, val=num
d[2] = [1]
d[3] = [7]
d[4] = [4]
d[5] = [5, 3, 2]
d[6] = [9, 6]
d[7] = [8]
enable = [False] * 10
for a in l:
  enable[a] = True
# マッチをk(=2..7)本使う場合の一番大きい値を総当たり
def f(nokori, current):
  if nokori == 0:
    return current
  if nokori < 0:
    return -1
  temps = []
  for key, nums in list(d.items())[::-1]:
    for num in nums:
      if enable[num]:
        if nokori-key != 0 and current % 10 != 0 and current % 10 < num:
          # 98 ok, 89 重複するので最後の桁以外は skip
          continue
        temps.append(f(nokori-key, current*10+num))
        break
  return max(temps)

# 余裕があるうちは一番マッチの本数が少ないモノをヤケクソで詰めまくる
hoge = False
for key, nums in list(d.items()):
    # print(key, nums, type(nums))
    for num in nums:
      if enable[num]:
        hoge = True
        break
    if hoge:
      break
cs = []
while n > 50:
  n -= key
  cs.append(str(num))

# ヤケクソで詰めたやつと総当たりで調べたマックスを並び替えて辞書順で大きくする
num_ans = str(f(n, 0))
print(''.join(sorted(list(num_ans) + cs)[::-1]))

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(100000)

n, m = map(int, input().split())
a = list(map(int, input().split()))
memo = {}
matches = [100, 2, 5, 5, 4, 5, 6, 3, 7, 6]

def doit(n):
    if n == 0:
        return ""
    if not n in memo:
        ret = None
        for d in a:
            m = matches[d]
            if n - m >= 0 and doit(n - m) is not None:
                r = max(doit(n - m) + str(d), str(d) + doit(n - m))
                if ret is None or len(r) > len(ret) or len(r) == len(ret) and r > ret:
                    ret = r
        memo[n] = ret
    return memo[n]

print(doit(n))

Submission status: Accepted

Solution code:
n, m = list(map(int, input().split(' ')))
l = list(map(int, input().split(' ')))
d = {}  # key=match, val=num
d[2] = [1]
d[3] = [7]
d[4] = [4]
d[5] = [5, 3, 2]
d[6] = [9, 6]
d[7] = [8]
enable = [False] * 10
for a in l:
  enable[a] = True
memo = {}
# マッチをk(=2..7)本使う場合の一番大きい値を総当たり
def f(nokori, current):
  k = (nokori, current)
  if k in memo:
    return memo[k]
  if nokori <= 0:
    return current if nokori == 0 else -1
  temps = []
  for key, nums in list(d.items())[::-1]:
    for num in nums:
      if enable[num]:
        if nokori-key != 0 and current % 10 != 0 and current % 10 < num:
          # 98 ok, 89 重複するので最後の桁以外は skip
          continue
        temps.append(f(nokori-key, current*10+num))
        break
  memo[k] = max(temps)
  return memo[k]

# 余裕があるうちは一番マッチの本数が少ないモノをヤケクソで詰めまくる
hoge = False
for key, nums in list(d.items()):
    # print(key, nums, type(nums))
    for num in nums:
      if enable[num]:
        hoge = True
        break
    if hoge:
      break
cs = []
while n > 50:
  n -= key
  cs.append(str(num))

# ヤケクソで詰めたやつと総当たりで調べたマックスを並び替えて辞書順で大きくする
num_ans = str(f(n, 0))
print(''.join(sorted(list(num_ans) + cs)[::-1]))

Submission status: Accepted

Solution code:
n, m = list(map(int, input().split(' ')))
l = list(map(int, input().split(' ')))
d = {}
# 1 = 2 = 0.5
d[2] = [1]
# 7 = 3 = 2.3 
d[3] = [7]
# 4 = 4 = 1
d[4] = [4]
# 5 = 5 = 1
# 3 = 5 = .6
# 2 = 5 = .4
d[5] = [5, 3, 2]
# 9 = 6 = 1.5
# 6 = 6 = 1
d[6] = [9, 6]
# 8 = 7 = 1.1...
d[7] = [8]
enable = [False] * 10
for a in l:
  enable[a] = True
memo = {}
def f(nokori, current):
#  print(nokori, current)
  k = (nokori, current)  # 順不同
  if k in memo:
    return memo[k]
  if nokori == 0:
    return current
  if nokori < 0:
    return -1
  temps = []
  for key, nums in list(d.items())[::-1]:
    # print(key, nums, type(nums))
    for num in nums:
      if enable[num]:
        if nokori-key != 0 and current % 10 != 0 and current % 10 < num:
          continue
        temps.append(f(nokori-key, current*10+num))
        break
  memo[k] = max(temps)
  return memo[k]

# pre
hoge = False
for key, nums in list(d.items()):
    # print(key, nums, type(nums))
    for num in nums:
      if enable[num]:
        hoge = True
        break
    if hoge:
      break
cs = []
while n > 50:  #
  n -= key
  cs.append(str(num))
num_ans = str(f(n, 0))
print(''.join(sorted(list(num_ans) + cs)[::-1]))

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort(reverse=True)
nums=[0,2,5,5,4,5,6,3,7,6]
dp=[-1]*(n+1)
dp[0]=0
for i in range(1,n+1):
    for x in a:
        if i-nums[x]>=0:
            dp[i]=max(dp[i-nums[x]]+1,dp[i])
k=dp[n]
ans=[]
for i in range(k):
    for x in a:
        if n-nums[x]<0:
            continue
        if dp[n-nums[x]]==dp[n]-1:
            n-=nums[x]
            ans.append(x)
            break
print("".join(list(map(str,ans))))

Submission status: Accepted

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

x = [-float('inf')] * (n + 1)
x[0] = 0
l = [0] * (n + 1)
_c = [2,5,5,4,5,6,3,7,6]
c = dict()
for i in range(m):
    c[a[i]] = _c[a[i] - 1]

for i in range(1, n + 1):
    x_max = -float('inf')
    l_max = 0
    for digit in c.keys():
        left = i - c[digit]
        if left >= 0:
            tmp_x = digit * (10 ** l[left]) + x[left]
            tmp_l = l[left] + 1
            if tmp_x > x_max:
                x_max = tmp_x
                l_max = tmp_l

    x[i] = x_max
    l[i] = l_max
print(x[-1])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

NUM = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
INF = 10**14

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

dp = [-INF]*(N+1)
dp[0] = 0
for i in range(N):
    for a in A:
        c = NUM[a]
        if i + c <= N:
            dp[i+c] = max(dp[i+c], dp[i]+1)

D = dp[N]
ind = N
ans = ''
for _ in range(D):
    for a in A:
        c = NUM[a]
        if ind - c < 0: continue
        if dp[ind] == dp[ind-c] + 1:
            ind -= c
            ans += str(a)
            break
print(ans)

Submission status: Accepted

Solution code:
n,m,*a=map(int,open(0).read().split())
d=[]
for i,j in((7,3),(9,6),(8,7),(6,6),(5,5),(4,4),(3,5),(1,2),(2,5)):
    if i in a:
        d.append((i,j))
dp=[0]*-~n
for i in range(1,n+1):
    for j,k in d:
        if i-k<0 or i-k!=0 and not dp[i-k]:continue
        dp[i]=max(dp[i],dp[i-k]*10+j)
print(dp[n])