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()))
a.sort(reverse=True)
lis = [2,5,5,4,5,6,3,7,6]
def new_val(num1,num2): # 123 , 4 -> 1234
    if num1<0:
        return -(10**10)
    if num1==0:
        return num2
    ret = (10**len(str(num2)))*num1 + num2
    return ret

dp = [[-(10**10) for i in range(1+n)] for j in range(1+m)]
for i in range(m):
    dp[i][0]=0

for i in range(m):
    num=a[i]
    honsu=lis[a[i]-1]
    for j in range(1+n):
        if j<honsu:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(new_val(dp[i+1][j-honsu] , num),dp[i][j])
print(dp[-1][-1])

Submission status: Accepted

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]

dp = [-1 for _ in range(N + 1)] #dp[i] i本のマッチを使って作れる最大の桁数
dp[0] = 0

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

ans = ''

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

print(ans)

Submission status: Accepted

Solution code:
match = {
    1: 2,
    2: 5,
    3: 5,
    4: 4,
    5: 5,
    6: 6,
    7: 3,
    8: 7,
    9: 6,
}

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

# 桁数を決めたい、最大を求めたいので前からDP
# dp[n]: n本のマッチでできる最大の桁？
inf = 10**18
dp = [-1] * (N + 10)
dp[0] = 0
for i in range(N):
    if dp[i] == -1:
        continue
    for a in A:
        dp[i + match[a]] = max(dp[i + match[a]], dp[i] + 1)

digit = dp[N]
pos = N
ans = ""
while pos > 0:
    for a in A[::-1]:
        if dp[pos - match[a]] == digit - 1:
            ans += str(a)
            pos -= match[a]
            digit -= 1
            break

print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    N, M = (int(i) for i in input().split())
    A = [int(i) for i in input().split()]
    A.sort(reverse=True)
    dp = ["-"]*(N+10)
    dp[0] = ""
    match = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
    for i in range(N+1):
        if dp[i] == "-":
            continue
        for a in A:
            cur = dp[i+match[a]]
            ne = dp[i] + str(a)
            if len(cur) < len(ne) or cur < ne:
                dp[i+match[a]] = ne
    # print(dp)
    print(dp[N])


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

def solve():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    A = [int(a) for a in input().split()]
    use = [6, 2, 5, 5, 4, 5, 6, 3, 7, 6]
    U = dict()
    for a in A:
        if use[a] in U: U[use[a]] = max(a, U[use[a]])
        else: U[use[a]] = a

    DP = [-1] * (N + 1)
    DP[0] = 0
    for i in range(N):
        if DP[i] > -1:
            for key in U:
                if i + key <= N:
                    DP[i + key] = max(DP[i + key], DP[i] * 10 + U[key])
    print(DP[N])

    return 0

if __name__ =="__main__":
    solve()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
x=[2,5,5,4,5,6,3,7,6]
a=[]
for i in map(int,input().split()):
    a.append([i,x[i-1]])
a.sort(reverse=True)
dp=[0]*(n+1)
for i in range(m):
    for j in range(n+1):
        if j==0 or dp[j]!=0:
            if j+a[i][1]<=n:
                dp[j+a[i][1]]=max(dp[j+a[i][1]],dp[j]*10+a[i][0])
print(dp[n])
'''
dp[i]をちょうどi本使った時に表せる最大の数と考えれば
(aが数字の値で降順ソートされていることにも注意して)、
a[i][0]をi番目に大きい数字、a[i][1]をその数を表すのに
必要なマッチ棒の本数として、
dp[j+a[i][1]]=max(dp[j+a[i][1]],dp[j]*10+a[i][0])
という更新を行ってdp[n]を求めれば良いです。
また、ある数字の組が決まればマッチの本数が一意に定まり
一番上の桁から順に大きい数字を入れるのが最適なので、
aを降順ソートして大きい数字から順に取ってDPを行うことで
これを実現することができます。
e.g. 9→3→3→2の順番に取れば、
((((0×10+9)×10+3)×10+3)×10+2)=9332((((0×10+9)×10+3)×10+3)×10+2)=9332
'''

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))
table = [0,2,5,5,4,5,6,3,7,6]
A.sort(reverse=True)
inf = (-1) * 10**5
#dp[i] := ちょうどi本のマッチを使って作る整数の、最大桁数
dp = [inf for i in range(N+1)]
dp[0] = 0
for i in range(N+1):
    for j in range(len(A)):
        if i + table[A[j]] > N:
            continue
        if dp[i + table[A[j]]] < dp[i] + 1:
            dp[i + table[A[j]]] = dp[i] + 1
#こうすることで、答えの桁数が分る.
#あとは実現する経路復元のようなものを行う
ans = ""
cur_cost = N
#各桁について一つずつ答えを決めていく
for _ in range(dp[N]):
    #大きい数字から最上位に決めていきたいので、大きい数字から考える
    for j in range(len(A)):
        if cur_cost - table[A[j]] < 0:
            continue
        if dp[cur_cost - table[A[j]]] == dp[cur_cost] - 1:
            ans += str(A[j])
            cur_cost -= table[A[j]]
            break
print(ans)

Submission status: Accepted

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

match = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
d = dict()
for e in a:
    d[e] = match[e]

dp = [-1] * (n + 1)
dp[0] = 0
for i in range(1, n + 1):
    for k, v in d.items():
        if i - v >= 0 and dp[i-v] != -1:
            dp[i] = max(dp[i], dp[i-v] * 10 + k)

print(dp[n])

Submission status: Accepted

Solution code:
#解説参照
n,m = map(int, input().split( ))
a = list(map(int, input().split( )))
mch = (100,2,5,5,4,5,6,3,7,6)

dp = [-1]*(n+10)
dp[0] = 0
for i in range(n+1):##nまでなので+1
    for aj in a:
        if dp[i-mch[aj]]>=0:##ちょうどn本使う必要がある
            dp[i] = max(dp[i], dp[i-mch[aj]]*10+aj)
print(dp[n])

Submission status: Accepted

Solution code:
#118_D
ch={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()))

dp=[-1 for _ in range(n+1)]
dp[0]=0
for i in range(1,n+1):
    res=-1
    for x in a:
        if i-ch[x]>=0:
            res=max(res,dp[i-ch[x]]*10+x)
    dp[i]=res
    
print(dp[n])

Submission status: Accepted

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

# argsは数を文字列で表したリスト
# 一番大きい数を文字列として出力
def maxnum(*args):
    maxn = args[0]
    for i in range(1, len(args)):
        if len(maxn) != len(args[i]):
            if len(args[i]) > len(maxn):
                maxn = args[i]
        else:
            maxn = max(maxn, args[i])
    return maxn


# 数字0〜9を作るのに必要なマッチ棒の数
nmatch = [6, 2, 5, 5, 4, 5, 6, 3, 7, 6]

dp = [""] + [None] * N
for i in range(1, N + 1):
    maxn = ""
    for a in A:
        if i - nmatch[a] >= 0 and dp[i - nmatch[a]] != None:
            maxn = maxnum(maxn, dp[i - nmatch[a]] + str(a), str(a) + dp[i - nmatch[a]])
            dp[i] = maxn

print(dp[N])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,_,*a=map(int,open(0).read().split())
ref={1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}
dp=[0]+[-float('inf')]*(n+9)
for i in range(n+1):
	for x in a:
		if dp[i]<dp[i-ref[x]]*10+x:
			dp[i]=dp[i-ref[x]]*10+x
print(dp[n])

Submission status: Accepted

Solution code:
N,M=list(map(int,input().split()))
A=sorted(list(map(int,input().split())),reverse=True)
C=[-1,2,5,5,4,5,6,3,7,6]
DP=[[0 if j==0 else -1 for i in range(M)] for j in range(N+1)]
for i in range(N+1):
  for j in range(M):
    if(j>0):
      DP[i][j]=max(DP[i][j],DP[i][j-1]);
    if(i-C[A[j]]>=0 and DP[i-C[A[j]]][j]!=-1):
      DP[i][j]=max(DP[i][j],DP[i-C[A[j]]][j]*10+A[j]);
    if(j>0 and i-C[A[j]]>=0 and DP[i-C[A[j]]][j-1]!=-1):
      DP[i][j]=max(DP[i][j],DP[i-C[A[j]]][j-1]*10+A[j]);
print(DP[N][M-1])

Submission status: Accepted

Solution code:
N, M, *A = map(int, open(0).read().split())
ls = [0]*10
ls[1] = 2
ls[2] = 5
ls[3] = 5
ls[4] = 4
ls[5] = 5
ls[6] = 6
ls[7] = 3
ls[8] = 7
ls[9] = 6
A.sort(reverse=True)
cls = {ls[a] for a in A}
cls = sorted(list(cls))
dp = [-float('inf')]*(N+10)
dp[0] = 0
for i in range(1,N+1):
  dp[i] = max(dp[i-c]+1 for c in cls)
ans = 0
M = N
for i in range(dp[N]):
  for a in A:
    c = ls[a]
    if dp[M-c]+1 == dp[M]:
      ans += a*10**(dp[N]-1-i)
      M -= c
      break
print(ans)

Submission status: Accepted

Solution code:
Q = {
    1: 2,
    2: 5,
    3: 5,
    4: 4,
    5: 5,
    6: 6,
    7: 3,
    8: 7,
    9: 6,
}
 
N, M = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
 
# 桁数の最大
dp = [-1] * (N + 1)
dp[0] = 0
 
for a in A:
    for i in range(Q[a], N + 1):
        if dp[i - Q[a]] >= 0:
            dp[i] = max(dp[i], dp[i - Q[a]] + 1)
            #print(dp)
 
# 整数の復元
ans = ''
 
# 大きな数から試す
A.sort(reverse=True)
 
i = N
while i:
    for a in A:
        if i - Q[a] >= 0 and dp[i - Q[a]] == dp[i] - 1:
            ans += str(a)
            i -= Q[a]
            break
 
print(ans)

Submission status: Accepted

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

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

c = [(i, d[i]) for i in A]
minpos = min(c, key=lambda x:x[1])[1]

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

for i in range(minpos, N+1):
    for n, cost in c:
        if i-cost<0 or 0<i-cost<minpos: continue
        a = dp[i]
        b = dp[i-cost] + n * (10**(digit[i-cost]))
        if a<b:
            dp[i] = b
            digit[i] = digit[i-cost] + 1

print(dp[N])

Submission status: Accepted

Solution code:
from copy import deepcopy
def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    l = [2,5,5,4,5,6,3,7,6]
    d = {}
    for i in A:
        if l[i-1] not in d:
            d[l[i-1]] = i
        else:
            if d[l[i-1]] < i:
                d[l[i-1]] = i
    d3 = {}
    for i in d:
        d3[d[i]] = i
    d2 = list(d)
    d2.sort()
    s = [[[-1] * (len(d2)) for _ in range(len(d2))] for _ in range(N+1)]
    dp = [[0] * (len(d2)) for _ in range(N+1)]
    for w in range(N+1):
        if w % d2[0] == 0:
            dp[w][0] = w // d2[0]
            s[w][0] = [0] * (len(d2))
            s[w][0][0] = w // d2[0]
    for i in range(1, len(d2)):
        for w in range(N+1):
            if w < d2[i]:
                continue
            elif max(dp[w-d2[i]]) > 0:
                x = dp[w-d2[i]].index(max(dp[w-d2[i]]))
                if dp[w][i-1] > dp[w-d2[i]][x] + 1:
                    dp[w][i] = dp[w][i-1]
                    s[w][i] = deepcopy(s[w][i-1])
                else:
                    dp[w][i] = dp[w-d2[i]][x] + 1
                    s[w][i] = deepcopy(s[w-d2[i]][x])
                    s[w][i][i] += 1
            elif w == d2[i]:
                dp[w][i] = 1
                s[w][i] = [0] * len(d2)
                s[w][i][i] = 1
            else:
                dp[w][i] = dp[w][i-1]
                s[w][i] = deepcopy(s[w][i-1])
    maxn = 0
    for i in s[-1]:
        if sum(i) <= 0:
            continue
        qq = []
        for j,v in enumerate(i):
            if v > 0:
                qq.append((d[d2[j]],v))
        qq.sort(key=lambda x:x[0], reverse=True)
        r = ''
        for k in qq:
            r += str(k[0]) * k[1]
        if int(r) > maxn:
            maxn = int(r)
    print(maxn)
main()

Submission status: Accepted

Solution code:
nums = [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)
s = set()
candidates = [] # [a, nums[a]]
for a in A:
  if nums[a] in s:
    continue
  s.add(nums[a])
  candidates.append([a, nums[a]])


dp = [-1] * (N+1)
dp[0] = 0
for i in range(N+1):
  for a, n in candidates:
    if i >= n and dp[i-n]>=0:
      dp[i] = max(dp[i], dp[i-n]+1)

ans = ''
idx = N
digit = dp[N]
while digit:
  for a, n in candidates:
    if idx - n >= 0 and dp[idx-n] == dp[idx]-1:
      ans += str(a)
      digit -= 1
      idx -= n
      break

print(int(ans))

Submission status: Accepted

Solution code:
nums = [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)
s = set()
candidates = [] # [a, nums[a]]
for a in A:
  if nums[a] in s:
    continue
  s.add(nums[a])
  candidates.append([a, nums[a]])


dp1 = [0] * (N+1)
dp2 = [-1] * (N+1)
d = {}
for a, n in candidates:
  if n <= N:
    dp1[n] = 1
    dp2[n] = 0
    d[n] = a

for i in range(N+1):
  for a, n in candidates:
    if i >= n and dp1[i-n]:
      if dp1[i] < dp1[i-n] + 1:
        dp1[i] = dp1[i-n] + 1
        dp2[i] = i-n

ans = []
idx = N
while idx:
  next_idx = dp2[idx]
  ans.append(d[idx - next_idx])
  idx = next_idx

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

Submission status: Accepted

Solution code:
def check(i):
    global kmax,nmax
    cnt = 0
    for j in range(i):
        cnt += K[j]*B[j]
    if sum(B[:i])+(N-cnt)//K[i]<kmax:
        return
    for k in range((N-cnt)//K[i],-1,-1):
        if cnt+K[i]*k==N:
             if kmax<=sum(B[:i])+k:
                    kmax = sum(B[:i])+k
                    B[i] = k
                    num = ""
                    for j in range(len(K)):
                        num += str(D[j])*B[K.index(C[D[j]])]
                    num = int(num)
                    nmax = max(nmax,num)
        else:
            if i<len(K)-1:
                B[i] = k
                check(i+1)
            else:
                B[i] = 0
                return
C = {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()))
G = {}
for i in range(M):
    a = A[i]
    k = C[a]
    if k not in G:
        G[k] = 0
    if a>G[k]:
        G[k] = a
K = sorted(list(G.keys()))
D = sorted(list(G.values()),reverse=True)
B = [0 for _ in range(len(K))]
kmax = 0
nmax = 0
check(0)
print(nmax)

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):
    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()))
a.sort(reverse=True)
c = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [[-1, -1] for i in range(n+1)]

dp[0] = [0, 0]
for i in range(1, n+1):
    for ai in a:
        ci = c[ai]
        if i - ci >= 0 and dp[i-ci][0] != -1:
            if dp[i][0] < dp[i-ci][0] + 1:
                dp[i] = [dp[i-ci][0] + 1, ai]
i = n
ans = []
while i > 0:
    ai = dp[i][1]
    ans.append(ai)
    i -= c[ai]
print("".join(map(str, ans)))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)
c = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [[-1, -1] for i in range(n+1)]

dp[0] = [0, 0]
for i in range(1, n+1):
    for ai in a:
        ci = c[ai]
        if i - ci >= 0 and dp[i-ci][0] != -1:
            if dp[i][0] < dp[i-ci][0] + 1:
                dp[i] = [dp[i-ci][0] + 1, ai]
i = n
ans = []
while i > 0:
    ai = dp[i][1]
    ans.append(ai)
    i -= c[ai]
ans.sort(reverse=True)
print("".join(map(str, ans)))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)
c = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [[-1, -1] for i in range(n+1)]
dp[0] = [0, 0]
for i in range(1, n+1):
    for ai in a:
        ci = c[ai]
        if i - ci >= 0 and dp[i-ci] != -1:
            if dp[i][0] < dp[i-ci][0] + 1:
                dp[i] = [dp[i-ci][0] + 1, ai]
i = n
ans = []
while i > 0:
    ai = dp[i][1]
    ans.append(ai)
    i -= c[ai]
ans.sort(reverse=True)
print("".join(map(str, ans)))

Submission status: Accepted

Solution code:
d = {
    1: 2,
    2: 5,
    3: 5,
    4: 4,
    5: 5,
    6: 6,
    7: 3,
    8: 7,
    9: 6,
}
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)

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


for a in A:
    for j in range(d[a], N + 1):
        dp[j] = max(dp[j], dp[j - d[a]] + 1)

ans = ""
remain = dp[N]
match = N
while match > 0:
    for a in A:
        if match - d[a] < 0:
            continue
        if dp[match - d[a]] == remain - 1:
            ans += str(a)
            match -= d[a]
            remain -= 1
            break

print(ans)

Submission status: Accepted

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

tab = [6, 2, 5, 5, 4, 5, 6, 3, 7, 6]
A_cmp = {}
for Ai in sorted(A):
    A_cmp[tab[Ai]] = Ai
A = list(A_cmp.values())
A.sort(key=lambda x: -x)

memo = [None] * (N + 1)
memo[0] = 0

import sys
sys.setrecursionlimit(100000)

def dp(X):
    if X < 0: return -(1000000007)
    if memo[X] != None: return memo[X]
    #
    rets = []
    for i, Ai in enumerate(A):
        rets.append(dp(X - tab[Ai]) + 1)
    #
    ret = max(rets)
    memo[X] = ret
    return ret

ans_len = dp(N)

N_tmp = N
ans = ''
for i in range(ans_len):
    for j, Aj in enumerate(A):
        if dp(N_tmp) - 1 == dp(N_tmp - tab[Aj]):
            ans += str(Aj)
            N_tmp -= tab[Aj]
            break

print(ans)

Submission status: Accepted

Solution code:

N, M = map(int, input().split())
A = list(map(int, input().split()))
numbers = [0,2,5,5,4,5,6,3,7,6]


dp = ["-" for i in range(11000)]
dp[0] = ""

def cal(x, y):
  lenx = len(x)
  leny = len(y)
  
  if lenx > leny:
    return x
  if leny > lenx:
    return y
  
  return max(x, y)

for i in range(N):
  if dp[i] == "-": 
    continue

  for j in range(M):
    num = numbers[A[j]]
    dp[i+num] = cal(dp[i] + str(A[j]), dp[i+num])

print(dp[N])

Submission status: Accepted

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

Submission status: Accepted

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

def main():
    N,M = map(int,input().split())
    p = {1:2,7:3,4:4,5:5,3:5,2:5,9:6,6:6,8:7}
    a = list(map(int,input().split()))
    INF = float("inf")
    dp = [-INF for _ in range(N+1)]
    dp[0] = 0
    for i in range(N):
        for j in a:
            if i+p[j] <= N:
                dp[i+p[j]] = max(dp[i+p[j]],dp[i]+1)
    
    dp.reverse()
    use = []
    for i in a:
        use.append((i,p[i]))
        
    use.sort(key=lambda x:(-x[0],-x[1]))
    ans = []
    now = 0
    while now < N:
        for num,i in use:
            if (now+i <= N and dp[now+i] == dp[now]-1):
                ans.append(str(num))
                now += i
                break
    print("".join(ans))
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

def get():
	return [int(x) for x in sys.stdin.readline().rstrip().split(" ")]

N, M = get()
A = get()

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

memo = [0 for x in range(N + 1)]

def search(n):
	if n < 0:
		return None
	else:
		return memo[n]

for n in range(1, N + 1):
	answer = None
	for d in A:
		senzinnnotie = search(n - tukaukazu[d])
		if senzinnnotie is not None:
			candidate = senzinnnotie * 10 + d
			if (answer is None) or (candidate > answer):
				answer = candidate
	memo[n] = answer

print(search(n))

Submission status: Accepted

Solution code:

"""
個数無制限ナップザック
大小判定は和が大きいほう→同じなら桁で比較していって先に大きくなった方
"""

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

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

lis = [[0] * 10 for i in range(N+1)]
able = [False] * (N+1)
able[0] = True

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

for i in A:

    for j in range(N):

        if able[j] and j+nums[i] <= N:

            if not able[j+nums[i]]:
                able[j+nums[i]] = True
                
                for k in range(10):
                    lis[j+nums[i]][k] = lis[j][k]

                lis[j+nums[i]][i] += 1

            else:

                flag = False

                if sum(lis[j+nums[i]]) < sum(lis[j]) + 1:
                    flag = True

                elif sum(lis[j+nums[i]]) == sum(lis[j]) + 1:

                    cp = lis[j].copy()
                    cp[i] += 1

                    for k in range(9,0,-1):

                        if lis[j+nums[i]][k] < cp[k]:
                            flag = True
                            break

                        elif lis[j+nums[i]][k] > cp[k]:
                            break


                if flag:
                    for k in range(10):
                        lis[j+nums[i]][k] = lis[j][k]
                    lis[j+nums[i]][i] += 1


ans = []

for i in range(9,0,-1):

    for j in range(lis[-1][i]):
        ans.append(i)

print ("".join(map(str,ans)))

Submission status: Accepted

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

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

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

print(dp[-1])

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
x=[2,5,5,4,5,6,3,7,6]#各数に使うマッチ棒の本数
a=[]#使う数字でけ格納するリスト
for i in map(int,input().split()):
    a.append([i,x[i-1]])#数と使う本数をリストで入力
    #ここでタプルにするとソートできない
a.sort(reverse=True)
#tuple(a)#タプルにしても実行時間、メモリーに大きな変化なし
#ソートしないと、大きい数字が先に来ないので間違う
#(OK)print(a)使える数字だけ
dp=[0]*(n+1)
#dp[i]：ちょうどi本使った時に表せる最大の数
#ループの順番が、いまひとつ、腑に落ちない
#大きい数字から先に試す。マッチの本数は徐々に増やす。
for i in range(m):
#外側ループが使用できる数、最初１番大きい数字、その後、使える数字が増える
    #print(i)
    for j in range(n+1):#マッチ棒は0からnまで使える
        #print(j,dp[j])
        if j==0 or dp[j]!=0:
        #(NG)if dp[j]!=0: 「jの範囲を1始め」でもNG
            if j+a[i][1]<=n:#マッチ棒が使用範囲内なら
                #print(dp[j+a[i][1]],dp[j]*10+a[i][0])
                #print(max(dp[j+a[i][1]],dp[j]*10+a[i][0]))
                dp[j+a[i][1]]=max(dp[j+a[i][1]],dp[j]*10+a[i][0])
#この更新はDP典型。右１項が左と同じ。右は両項とも、前から使っているj本に
#新しく使うi番目を使った　本数での数を表している。
print(dp[n])

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
x=[2,5,5,4,5,6,3,7,6]#各数に使うマッチ棒の本数
a=[]#使う数字でけ格納するリスト
for i in map(int,input().split()):
    a.append([i,x[i-1]])#数と使う本数をリストで入力
    #ここでタプルにするとソートできない
a.sort(reverse=True)
#tuple(a)#タプルにしても実行時間、メモリーに大きな変化なし
#ソートしないと、大きい数字が先に来ないので間違う
#(OK)print(a)使える数字だけ
dp=[0]*(n+1)
#dp[i]：ちょうどi本使った時に表せる最大の数
#ループの順番が、いまひとつ、腑に落ちない
for i in range(m):
#外側ループが使用できる数、最初１番大きい数字、その後、使える数字が増える
    for j in range(n+1):#マッチ棒は0からnまで使える
        if j==0 or dp[j]!=0:
        #(NG)if dp[j]!=0: 「jの範囲を1始め」でもNG
            if j+a[i][1]<=n:#マッチ棒が使用範囲内なら
                #print(dp[j+a[i][1]],dp[j]*10+a[i][0])
                #print(max(dp[j+a[i][1]],dp[j]*10+a[i][0]))
                dp[j+a[i][1]]=max(dp[j+a[i][1]],dp[j]*10+a[i][0])
#この更新はDP典型。右１項が左と同じ。右は両項とも、前から使っているj本に
#新しく使うi番目を使った　本数での数を表している。
print(dp[n])

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
x=[2,5,5,4,5,6,3,7,6]#各数に使うマッチ棒の本数
a=[]#使う数字でけ格納するリスト
for i in map(int,input().split()):
    a.append([i,x[i-1]])#数と使う本数をリストで入力
    #ここでタプルにするとソートできない
a.sort(reverse=True)
tuple(a)
#ソートしないと、大きい数字が先に来ないので間違う
#(OK)print(a)使える数字だけ
dp=[0]*(n+1)
#dp[i]：ちょうどi本使った時に表せる最大の数
#ループの順番が、いまひとつ、腑に落ちない
for i in range(m):#外側ループが使用できる数
    for j in range(n+1):#マッチ棒は0からnまで使える
        if j==0 or dp[j]!=0:
        #(NG)if dp[j]!=0: 「jの範囲を1始め」でもNG
            if j+a[i][1]<=n:#マッチ棒が使用範囲内なら
                #print(dp[j+a[i][1]],dp[j]*10+a[i][0])
                #print(max(dp[j+a[i][1]],dp[j]*10+a[i][0]))
                dp[j+a[i][1]]=max(dp[j+a[i][1]],dp[j]*10+a[i][0])
#この更新はDP典型。右１項が左と同じ。右は両項とも、前から使っているj本に
#新しく使うi番目を使った　本数での数を表している。
print(dp[n])

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
x=[2,5,5,4,5,6,3,7,6]#各数に使うマッチ棒の本数
a=[]#使う数字でけ格納するリスト
for i in map(int,input().split()):
    a.append([i,x[i-1]])#以上、入力
a.sort(reverse=True)
#ソート：なるべく大きい数字を先に使う：更新減る
#(OK)print(a)使える数字だけ
dp=[0]*(n+1)
#dp[i]：ちょうどi本使った時に表せる最大の数
#ループの順番が、いまひとつ、腑に落ちない
for i in range(m):#外側ループが使用できる数
    for j in range(n+1):#マッチ棒は0からnまで使える
        if j==0 or dp[j]!=0:
        #(NG)if dp[j]!=0: 「jの範囲を1始め」でもNG
            if j+a[i][1]<=n:#マッチ棒が使用範囲内なら
                dp[j+a[i][1]]=max(dp[j+a[i][1]],dp[j]*10+a[i][0])
#この更新はDP典型。右１項が左と同じ。右は両項とも、前から使っているj本に
#新しく使うi番目を使った　本数での数を表している。
print(dp[n])

Submission status: Accepted

Solution code:
m = [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)
for i in range(len(A)-1, 0, -1):
    for j in range(i-1, -1, -1):
        if m[A[i]] == m[A[j]]:
            del A[i]
            break

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

for i in range(N):
    if dp[i]==-1: continue
    for j in range(len(A)):
        ind = i + m[A[j]]
        if ind <= N:
            dp[ind] = max(dp[ind], dp[i] * 10 + A[j])

print(dp[-1])

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
x=[2,5,5,4,5,6,3,7,6]
a=[]
for i in map(int,input().split()):
    a.append([i,x[i-1]])
a.sort(reverse=True)
dp=[0]*(n+1)
for i in range(m):
    for j in range(n+1):
        if j==0 or dp[j]!=0:
            if j+a[i][1]<=n:
                dp[j+a[i][1]]=max(dp[j+a[i][1]],dp[j]*10+a[i][0])
print(dp[n])

Submission status: Accepted

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}

def lenmax(a,b):
    if len(a) > len(b):
        return a
    elif len(a) < len(b):
        return b
    return max(a,b)

dp = ['-' for i in range(10**4+10)]
dp[0] = ''
for i in range(N+1):
    if dp[i] == '-':
        continue
    for a in A:
        dp[i+num[a]] = lenmax(dp[i+num[a]],dp[i]+str(a))
print(dp[N])

Submission status: Accepted

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

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

dp = ["-" for _ in range(11000)]
dp[0] = ""


def _max(a, b):
    if len(a) > len(b):
        return a
    if len(a) < len(b):
        return b
    return max(a, b)


for i in range(N+1):
    if dp[i] == "-":
        continue
    for a in A:
        dp[i+match[a]] = _max(dp[i+match[a]], dp[i]+str(a))

print(dp[N])

Submission status: Accepted

Solution code:
import resource
import sys
sys.setrecursionlimit(20000)
f = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
n, m = map(int, input().split())
a = list(map(int, input().split()))

memo = [-1]*10100


def dp(i):
    # i本のマッチを使って作れる最大の整数
    if i < 0:
        return - 10 ** 100000
    if not (0 <= i and i < 10100):
        print(-1)
        exit()
    if memo[i] != -1:
        return memo[i]
    if i == 0:
        return 0
    ret = -10**100000
    for x in a:
        ret = max(ret, 10 * dp(i - f[x]) + x)
    memo[i] = ret
    return ret


print(dp(n))

Submission status: Accepted

Solution code:
import resource
import sys
sys.setrecursionlimit(20000)
f = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
n, m = map(int, input().split())
a = list(map(int, input().split()))

memo = ["-1"] * 10100


def MAX(x, y):
    if y[0] != '#' and (x == "#" or len(x) < len(y) or (len(x) == len(y) and x < y)):
        return y
    else:
        return x


def dp(i):
    # i本のマッチを使って作れる最大の整数
    if i < 0:
        return "#"

    if memo[i] != "-1":
        return memo[i]

    if i == 0:
        return ""

    ret = "#"
    for x in a:
        ret = MAX(ret, dp(i - f[x]) + str(x))
    memo[i] = ret
    return ret


print(dp(n))

Submission status: Accepted

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


dp=[0]*(N+10)
for j in range(M):
    need=B[A[j]-1]
    dp[need]=max(dp[need],A[j])

for i in range(1,N+1):
    for j in range(M):
        need=B[A[j]-1]
        if i-need>=0:
            if dp[i-need]:
                dp[i]=max(dp[i], dp[i-need]*10+dp[need])
            
print(dp[N])

Submission status: Accepted

Solution code:
import queue
from collections import defaultdict
import copy

N,M=map(int,input().split())
A=list(map(int,input().split()))
ma=[2,5,5,4,5,6,3,7,6]
BA=[[0,0] for _ in range(M)] #(必要本数，-1*数字)
for i in range(M):
    BA[i][1]=-1*A[i]
    BA[i][0]=ma[A[i]-1]
    
BA.sort()

#同じ本数使うものを消去
can=[]
ii=0
while ii <len(BA):
    if BA[ii][0] in can:
        BA.pop(ii)
    else:
        can.append(BA[ii][0])
        ii+=1
M=len(BA)#Mの書き換え

diff=[0]*M#数字変更の際に追加で必要な本数
for i in range(M):
    diff[i]=BA[i][0]-BA[0][0]
    BA[i][1]=BA[i][1]*-1#(必要本数，数字)に直しておく

fi=BA[0]###
#BA.sort(key=lambda x: x[1]*-1)#数字の大きいもの順


    
p=[1]*(N+1)
for i in range(N):
    p[i+1]=p[i]*10

#数字のセットL(sort済み)から作れる最大の数値を出力
def set_to_num(L):
    ans=0
    for i in range(len(L)):
        ans+=L[i]*p[i]
    return ans

#2つの配列を合わせる
def make_set(temp,L):
    ori=copy.deepcopy(temp)
    for i in range(len(L)):
        ori[i]=L[i]
    ori.sort()
    return ori
    

#dd用hash
def make_h(L):
    h=0
    for i in range(len(L)):
        h+=p[i]*L[i]
    return h
    
    
ans=-1
Max_dig=N//fi[0]

for d in range(Max_dig):#減らす桁数
    dig=Max_dig-d
    rem=N-fi[0]*dig
    temp=[fi[1]]*dig
    dd = defaultdict(int)
    q=queue.Queue()
    q.put((rem,[]))#残り本数，入れ替える数字
    
    while not q.empty():
        rem2,L=q.get()
        if rem2==0:
            #print(temp,L)
            LLL=make_set(temp,L)
            #print(LLL)
            ans=max(ans,set_to_num(LLL))
        else:
            for i in range(1,M):#変更候補の数字を見ていく.0番は自身のためのぞく
                if rem2>=diff[i]:
                    LL=copy.deepcopy(L)
                    LL.append(BA[i][1])
                    if len(LL)<=len(temp):
                        LL.sort()
                        h=make_h(LL)
                        if dd[h]==0:
                            q.put((rem2-diff[i],LL))
                            dd[h]=1
    if ans!=-1:
        break
        
print(ans)