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: Wrong Answer

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

d1 = {1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}
d2 = {2:[1],3:[7],4:[4],5:[5,3,2],6:[9,6],7:[8]}

p = 0
mn = 8
for ai in a:
  if mn > d1[ai]:
    p = ai
    mn = d1[ai]
  elif mn == d1[ai]:
    if p < ai:
      p = ai
#print(p)

ans = [p for _ in range(n//d1[p])]
x = n-d1[p]*len(ans)

i = 0
while(x > 0 and i < len(ans)):
  #print(x)
  for j in range(9,ans[i],-1):
    if j in a and 0 <= d1[j]-d1[ans[i]] <= x:
      x -= d1[j]-d1[ans[i]]
      ans[i] = j
      break
  i += 1
i = len(ans)-1
while(x > 0 and i >= 0):
  flag = False
  #print(ans[i],d1[ans[i]],x)
  for j in range(d1[ans[i]]+x,1,-1):
    if j in d2:
      for v in d2[j]:
        #print('v=',v)
        if v in a and ans[i] > v:
          x -= d1[v]-d1[ans[i]]
          ans[i] = v
          flag = True
          break
    if flag:
      break
  i -= 1

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

Submission status: Wrong Answer

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

d1 = {1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}
d2 = {2:[1],3:[7],4:[4],5:[5,3,2],6:[9,6],7:[8]}

p = 0
mn = 8
for ai in a:
  if mn > d1[ai]:
    p = ai
    mn = d1[ai]
  elif mn == d1[ai]:
    if p < ai:
      p = ai
#print(p)

ans = [p for _ in range(n//d1[p])]
x = n-d1[p]*len(ans)

i = 0
while(x > 0 and i < len(ans)):
  #print(x)
  for j in range(9,ans[i],-1):
    if j in a and 0 <= d1[j]-d1[ans[i]] <= x:
      x -= d1[j]-d1[ans[i]]
      ans[i] = j
      break
  i += 1
i = len(ans)-1
while(x > 0 and i >= 0):
  flag = False
  #print(ans[i],d1[ans[i]],x)
  for j in range(d1[ans[i]]+x,1,-1):
    if j in d2:
      for v in d2[j]:
        #print('v=',v)
        if v in a:
          ans[i] = v
          x -= d1[v]
          flag = True
          break
    if flag:
      break
  i -= 1

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

Submission status: Wrong Answer

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

T=[0,2,5,5,4,5,6,3,7,6]
B=[]
for i in A:
    B.append(T[i])
B=sorted(list(set(B)))

dp=[0 for i in range(N+1)]
dp2=['' for i in range(N+1)]
#for i in range(1,B[0]):
#    dp[i]=-1
#print(B)

for i in range(1,N+1):
    for j in B:
        if i-j>=0 and dp[i-j]!=-1:
            dp[i]=max(dp[i],dp[i-j]+1)
            #print(i,j,dp[i])
    if dp[i]==0:
        dp[i]=-1

c1,c2=N,N
U=[0 for i in range(8)]
while c1>0:
    c2-=1
    if dp[c2]+1==dp[c1]:
        U[c1-c2]+=1
        c1=c2
        
#print(U)
            
ans=""
if 9 in A:
    ans+='9'*U[6]
    U[6]=0
if 8 in A:
    ans+='8'*U[7]
if 7 in A:
    ans+='7'*U[3]
if 6 in A:
    ans+='6'*U[6]
if 5 in A:
    ans+='5'*U[5]
    U[5]=0
if 4 in A:
    ans+='4'*U[4]
if 3 in A:
    ans+='3'*U[5]
    U[5]=0
if 2 in A:
    ans+='2'*U[5]
if 1 in A:
    ans+='1'*U[2]

print(ans)

Submission status: Wrong Answer

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()))
A.sort(reverse=True)
C=[]
for a in A:
    C.append(cost[a])

dp=[0]*(N+1)
DP=[""]*(N+1)
for i in range(1,N+1):
    num=0
    for j in range(M):
        if i-C[j]<0:
            continue
        if i-C[j]==0:
            dp[i]=1
            DP[i]=str(A[j])
            continue
        elif dp[i-C[j]]+1>num:
            num=dp[i-C[j]]+1
            DP[i]=DP[i-C[j]]+str(A[j])
        dp[i]=num
ans=list(map(int,DP[N]))
ans.sort(reverse=True)
ANS=""
for i in range(dp[N]):
    ANS+=str(ans[i])
print(ANS)

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
a=list(map(int,input().split()))
d=dict()
need=[0,2,5,5,4,5,6,3,7,6]
for i in range(m):
    if need[a[i]] not in d:
        d[need[a[i]]]=a[i]
    else:
        if a[i]>d[need[a[i]]]:
            d[need[a[i]]]=a[i]
d=list(d.items())
d.sort()
m=len(d)
dp=[[0]*10 for _ in range(n+1)]
for i in range(n+1):
    for j in range(m):
        if i-d[j][0]>=0:
            if dp[i][0]==dp[i-d[j][0]][0]+1:
                ok=False
                for k in reversed(range(1,10)):
                    if k==d[j][1]:
                        if dp[i][k]<dp[i-d[j][0]][k]+1:
                            ok=True
                            break
                        elif dp[i][k]>dp[i-d[j][0]][k]+1:
                            break
                    else:
                        if dp[i][k]<dp[i-d[j][0]][k]:
                            ok=True
                            break
                        elif dp[i][k]>dp[i-d[j][0]][k]:
                            break
                if ok:
                    for k in range(10):
                        dp[i][k]=dp[i-d[j][0]][k]
                    dp[i][d[j][1]]+=1
                    dp[i][0]+=1
            elif dp[i][0]<dp[i-d[j][0]][0]+1:
                for k in range(10):
                    dp[i][k]=dp[i-d[j][0]][k]
                dp[i][d[j][1]]+=1
                dp[i][0]+=1
ans=str()
for i in reversed(range(1,10)):
    ans+=str(i)*dp[-1][i]
print(ans)
#print(d)
#print(dp[-1])

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
a=list(map(int,input().split()))
d=dict()
need=[0,2,5,5,4,5,6,3,7,6]
for i in range(m):
    if need[a[i]] not in d:
        d[need[a[i]]]=a[i]
    else:
        if a[i]>d[need[a[i]]]:
            d[need[a[i]]]=a[i]
d=list(d.items())
d.sort()
m=len(d)
dp=[[0]*10 for _ in range(n+1)]
for i in range(n+1):
    for j in range(m):
        if i-d[j][0]>=0:
            if dp[i][0]==dp[i-d[j][0]][0]+1:
                ok=False
                for k in reversed(range(1,10)):
                    if k==d[j][1]:
                        if dp[i][k]<dp[i-d[j][0]][k]+1:
                            ok=True
                    else:
                        if dp[i][k]<dp[i-d[j][0]][k]:
                            ok=True
                if ok:
                    for k in range(10):
                        dp[i][k]=dp[i-d[j][0]][k]
                    dp[i][d[j][1]]+=1
                    dp[i][0]+=1
            elif dp[i][0]<dp[i-d[j][0]][0]+1:
                for k in range(10):
                    dp[i][k]=dp[i-d[j][0]][k]
                dp[i][d[j][1]]+=1
                dp[i][0]+=1
ans=str()
for i in reversed(range(1,10)):
    ans+=str(i)*dp[-1][i]
print(ans)
#print(d)
#print(dp[-1])

Submission status: Wrong Answer

Solution code:
def max_for_str(a, b):
    if len(a) > len(b):
        return a
    elif len(a) < len(b):
        return b
    else:#This case is unlikely to happen.
        for c1, c2 in zip(a, b):
            if c1 > c2:
                return a
            elif c1 < c2:
                return b
        return a
            
match = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]

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

dp = [None] * (N+1)
dp[0] = ""

for i in range(N+1):
    for A in As:
        if i - match[int(A)] >= 0 and not dp[i - match[int(A)]] is None:
            if dp[i] is None:
                if A >= dp[i - match[int(A)]]:
                    dp[i] = A + dp[i - match[int(A)]]
            else:
                dp[i] = max_for_str(dp[i] , A + dp[i - match[int(A)]])
                
print(dp[N])

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
a = list(map(int,input().split()))
a.sort(reverse = True)
l = [0,2,5,5,4,5,6,3,7,6]
INF = 10**18
dp = [[[-INF]*2 for i in range(n+1)] for j in range(m+1)]
dp[0][0] = [0,0]
for i in range(m):
    for j in range(n+1):
        x = l[a[i]]
        dp[i+1][j] = dp[i][j]
        if x <= j:
            if dp[i+1][j-x][0] > -INF:
                a1 = dp[i+1][j-x][0] +1
                a2 = dp[i+1][j-x][1] + a[i]
                if a1 > dp[i][j][0]:
                    dp[i+1][j] = [a1,a2]
                elif a1 == dp[i][j][0] and a2 > dp[i][j][1]:
                    dp[i+1][j] = [a1,a2]

ans = []
na = dp[-1][-1][0]
nb = dp[-1][-1][1]
a.sort()
for i in range(m,0,-1):
    for j in range(n,-1,-1):
        x = l[a[i-1]]
        if dp[i][j] == [na-1,nb-a[i-1]]:
            na -= 1
            nb -= a[i-1]
            ans.append(a[i-1])

ans.sort(reverse = True)
print(*ans,sep="")

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
l = [0,2,5,5,4,5,6,3,7,6]
INF = 10**18
dp = [[[-INF]*2 for i in range(n+1)] for j in range(m+1)]
dp[0][0] = [0,0]
for i in range(m):
    for j in range(n+1):
        x = l[a[i]]
        dp[i+1][j] = dp[i][j]
        if x <= j:
            if dp[i+1][j-x][0] > -INF:
                a1 = dp[i+1][j-x][0] +1
                a2 = dp[i+1][j-x][1] + a[i]
                if a1 > dp[i][j][0]:
                    dp[i+1][j] = [a1,a2]
                elif a1 == dp[i][j][0] and a2 > dp[i][j][1]:
                    dp[i+1][j] = [a1,a2]

ans = []
na = dp[-1][-1][0]
nb = dp[-1][-1][1]

for i in range(m,0,-1):
    for j in range(n,-1,-1):
        x = l[a[i-1]]
        if dp[i][j] == [na-1,nb-a[i-1]]:
            na -= 1
            nb -= a[i-1]
            ans.append(a[i-1])

ans.sort(reverse = True)
print(*ans,sep="")

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
a = list(map(int,input().split()))
a.sort(reverse = True)
l = [0,2,5,5,4,5,6,3,7,6]
INF = 10**18
dp = [[[-INF]*2 for i in range(n+1)] for j in range(m+1)]
dp[0][0] = [0,0]
for i in range(m):
    for j in range(n+1):
        x = l[a[i]]
        dp[i+1][j] = dp[i][j]
        if x <= j:
            if dp[i+1][j-x][0] > -INF:
                a1 = dp[i+1][j-x][0] +1
                a2 = dp[i+1][j-x][1] + a[i]
                if a1 > dp[i][j][0]:
                    dp[i+1][j] = [a1,a2]
                elif a1 == dp[i][j][0] and a2 > dp[i][j][1]:
                    dp[i+1][j] = [a1,a2]

ans = []
na = dp[-1][-1][0]
nb = dp[-1][-1][1]

for i in range(m,0,-1):
    for j in range(n,-1,-1):
        x = l[a[i-1]]
        if dp[i][j] == [na-1,nb-a[i-1]]:
            na -= 1
            nb -= a[i-1]
            ans.append(a[i-1])

ans.sort(reverse = True)
print(*ans,sep="")

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
a = list(map(int,input().split()))
l = [0,2,5,5,4,5,6,3,7,6]
INF = 10**18
dp = [[[-INF]*2 for i in range(n+1)] for j in range(m+1)]
dp[0][0] = [0,0]
for i in range(m):
    for j in range(n+1):
        x = l[a[i]]
        dp[i+1][j] = dp[i][j]
        if x <= j:
            if dp[i+1][j-x][0] > -INF:
                a1 = dp[i+1][j-x][0] +1
                a2 = dp[i+1][j-x][1] + a[i]
                if a1 > dp[i][j][0]:
                    dp[i+1][j] = [a1,a2]
                elif a1 == dp[i][j][0] and a2 > dp[i][j][1]:
                    dp[i+1][j] = [a1,a2]

ans = []
na = dp[-1][-1][0]
nb = dp[-1][-1][1]

for i in range(m,0,-1):
    for j in range(n,-1,-1):
        x = l[a[i-1]]
        if dp[i][j] == [na-1,nb-a[i-1]]:
            na -= 1
            nb -= a[i-1]
            ans.append(a[i-1])

ans.sort(reverse = True)
print(*ans,sep="")

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# まずは桁数を増やす→数字の大きい順に並べる
N, M = lr()
A = lr()
matches = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
A = [(matches[a], a) for a in A]
A.sort(key = lambda x: x[1], reverse=True)
A.sort(key = lambda x: x[0])
top_match = A[0][0]
dp = [None] * (N+1)
dp[0] = []
used = set()
for match, num in A:
    if match in used:
        continue
    used.add(match)
    for x in range(N+1):
        if x - match < 0:
            continue
        if dp[x] == None and dp[x-match] != None:
            dp[x] = dp[x-match] + [num]
        elif dp[x] != None and dp[x-match] != None:
            if len(dp[x-match]) >= len(dp[x]):
                dp[x] = dp[x-match] + [num]
            elif len(dp[x-match]) == len(dp[x]) - 1 and num > dp[x][-1]:
                dp[x] = dp[x-match] + [num]

X = dp[N]
X.sort(reverse=True)
answer = ''.join(list(map(str, X)))
print(answer)
# 37

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# まずは桁数を増やす→数字の大きい順に並べる
N, M = lr()
A = lr()
matches = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
A = [(matches[a], a) for a in A]
A.sort(key = lambda x: x[1], reverse=True)
A.sort(key = lambda x: x[0])
top_match = A[0][0]
dp = [None] * (N+1)
dp[0] = []
used = set()
for match, num in A:
    if match in used:
        continue
    used.add(match)
    for x in range(N+1):
        if x - match < 0:
            continue
        if dp[x] == None and dp[x-match] != None:
            dp[x] = dp[x-match] + [num]
        elif dp[x] != None and dp[x-match] != None and len(dp[x-match]) >= len(dp[x]) - 1:
            dp[x] = dp[x-match] + [num]

X = dp[N]
X.sort(reverse=True)
answer = ''.join(list(map(str, X)))
print(answer)
# 37

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# まずは桁数を増やす→数字の大きい順に並べる
N, M = lr()
A = lr()
matches = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
A = [(matches[a], a) for a in A]
A.sort(key = lambda x: x[1], reverse=True)
A.sort(key = lambda x: x[0])
top_match = A[0][0]
dp = [None] * (N+1)
dp[0] = []
used = set()
for match, num in A:
    if match in used:
        continue
    used.add(match)
    for x in range(N+1):
        if x - match < 0:
            continue
        if dp[x] == None and dp[x-match] != None:
            dp[x] = dp[x-match] + [num]
        if dp[x] != None and dp[x-match] != None and len(dp[x-match]) >= len(dp[x]) - 1:
            dp[x] = dp[x-match] + [num]

X = dp[N]
X.sort(reverse=True)
answer = ''.join(list(map(str, X)))
print(answer)
# 37

Submission status: Wrong Answer

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

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

    # dig: マッチ本数 -> 使える数字
    nm = [999, 2, 5, 5, 4, 5, 6, 3, 7, 6]
    dig = [None for i in range(8)]
    for x in a:
        dig[nm[x]] = x

    # dp[j]: j本のマッチを使って作れる最大の数 tuple(桁数d, prevj, lastdig)
    dp = [None for j in range(n + 1)]
    dp[0] = (0, None, None)
    for j in range(1, n + 1):  # もらう
        for use in [2, 3, 4, 5, 6, 7]:
            jp = j - use
            if jp < 0:
                continue
            if dig[use] is None:
                continue
            if dp[jp] is None:
                continue
            d = dp[jp][0] + 1
            tup = (d, jp, dig[use])
            if (dp[j] is None) or (dp[j][0] < d) or (dp[j][0] == d and dp[j][2] < dig[use]):
                dp[j] = tup

    res = []
    j = n
    while True:
        d, jp, i = dp[j]
        if jp is None:
            break
        res.append(str(i))
        j = jp
    assert len(res) == dp[n][0]

    print("".join(res))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

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

    # dig: マッチ本数 -> 使える数字
    nm = [999, 2, 5, 5, 4, 5, 6, 3, 7, 6]
    dig = [None for i in range(8)]
    for x in a:
        dig[nm[x]] = x

    # dp[j]: j本のマッチを使って作れる最大の数 tuple(桁数d, prevj, lastdig)
    dp = [None for j in range(n + 1)]
    dp[0] = (0, None, None)
    for j in range(1, n + 1):  # もらう
        for use in [2, 3, 4, 5, 6, 7]:
            jp = j - use
            if jp < 0:
                continue
            if dig[use] is None:
                continue
            if dp[jp] is None:
                continue
            d = dp[jp][0] + 1
            tup = (d, jp, dig[use])
            if (dp[j] is None) or (dp[j][0] < d) or (dp[j][0] == d and dp[j][2] < dig[use]):
                dp[j] = tup

    res = []
    j = n
    while True:
        d, jp, i = dp[j]
        if jp is None:
            break
        res.append(str(i))
        j = jp

    print("".join(res))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

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

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

dp = [0] * (n+10)

for i in range(n):
  tmp = dp[i]
  k = 1
  while tmp:
    tmp //= 10
    k *= 10
  for ai in a:
    dp[l[ai] + i] = max(dp[l[ai] + i], dp[i] + k * ai, dp[i] * 10 + ai)
print(dp[n])

Submission status: Wrong Answer

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=[-2*n]*(n+10)
dp[0]=0
ans=[]
for i in range(1,n+1):
    for j in cost:
        if i>=j:
            dp[i]=max(dp[i],dp[i-j]+1)
cnt=n
while cnt:
    for j in a:
        if cnt>=j and dp[cnt-cost[j]]==dp[cnt]-1:
            ans.append(j)
            cnt-=cost[j]
            break
for j in ans:
    print(j, end="")
    print("")

Submission status: Wrong Answer

Solution code:
def main():
    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=[-2*n]*(n+10)
    dp[0]=0
    ans=[]
    for i in range(1,n+1):
        for j in cost:
            if i>=j:
                dp[i]=max(dp[i],dp[i-j]+1)
    cnt=n
    while cnt:
        for j in a:
            if cnt>=j and dp[cnt-cost[j]]==dp[cnt]-1:
                ans.append(j)
                cnt-=cost[j]
                break
    for j in ans:
        print(j, end="")
        print("")

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
l=list(map(int,input().split()))
x=[0,2,5,5,4,5,6,3,7,6]
d=dict()
for j in l:
    d[x[j]]=j
INF=float('inf')
dp=[-INF for i in range(n+1)]
dp[0]=0
for i in range(2,n+1):
    for j in d.keys():
        if j<=i:
            dp[i]=max(dp[i],dp[i-j]*10+d[j])
print(dp[n])

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
A=reversed(sorted(map(int,input().split())))
M=[2,5,5,4,5,6,3,7,6]
D={}
E={}
for a in A:
    if M[a-1] in D:
        continue
    else:
        D[M[a-1]]=a
        E[a]=M[a-1]
S=list(reversed(sorted(E)))
        
dp=[0]*(n+2)
for i in range(1,n+2):
    cnt=-1
    for d in D:
        if i-d>=0:
            if dp[i-d]!=-1:
                cnt=max(dp[i-d]+1,cnt)
    dp[i]=cnt    
k=dp[n]
ans=""
print(E)

while k>0:
    for s in S:
        x=E[s]
        if n-x<0:
            continue
        if dp[n-x]==k-1:
            ans+=str(s)
            k-=1
            n-=x
            break
print(ans)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
A=reversed(sorted(map(int,input().split())))
M=[2,5,5,4,5,6,3,7,6]
D={}
E={}
for a in A:
    if M[a-1] in D:
        continue
    else:
        D[M[a-1]]=a
        E[a]=M[a-1]
S=list(reversed(sorted(E)))
        
dp=[0]*(n+2)
for i in range(1,n+2):
    cnt=-1
    for d in D:
        if i-d>=0:
            if dp[i-d]!=-1:
                cnt=max(dp[i-d]+1,cnt)
    dp[i]=cnt    
k=dp[n]
ans=""


while k>0:
    for s in S:
        x=E[s]
        if dp[n-x]==k-1:
            ans+=str(s)
            k-=1
            n-=x
            break
print(ans)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
A=reversed(sorted(map(int,input().split())))
M=[2,5,5,4,5,6,3,7,6]
D={}
E={}
for a in A:
    if M[a-1] in D:
        continue
    else:
        D[M[a-1]]=a
        E[a]=M[a-1]
S=list(reversed(sorted(E)))
        
dp=[0]*(n+2)
for i in range(1,n+2):
    cnt=-1
    for d in D:
        if i-d>=0:
            if dp[i-d]!=-1:
                cnt=max(dp[i-d]+1,cnt)
    dp[i]=cnt    
k=dp[n]
ans=""


print(dp)
while k>0:
    for s in S:
        x=E[s]
        if dp[n-x]==k-1:
            ans+=str(s)
            k-=1
            n-=x
            break
print(ans)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
A=reversed(sorted(map(int,input().split())))
M=[2,5,5,4,5,6,3,7,6]
D={}
for a in A:
    if M[a-1] in D:
        continue
    else:
        D[a]=M[a-1]
        
dp=[0]*(n+2)
for i in range(1,n+2):
    cnt=-1
    for d in D:
        x=D[d]
        if i-x>=0:
            if dp[i-x]!=-1:
                cnt=max(dp[i-x]+1,cnt)
    dp[i]=cnt    
k=dp[n]
ans=""
S=list(reversed(sorted(D)))

while k>0:
    for s in S:
        x=D[s]
        if dp[n-x]==k-1:
            ans+=str(s)
            k-=1
            n-=x
            break
print(ans)

Submission status: Wrong Answer

Solution code:
n,m = map(int, input().split())
a = sorted(list(map(int, input().split())))
match = [0,2,5,5,4,5,6,3,7,6]
move = [0,0,0,0,0,0]
for i in a:
  stick = match[i]
  move[stick-2] = i
if move[0]:
  if move[1]:
    move[3] = 0
    move[5] = 0
  move[2] = 0
  move[4] = 0
if move[1]:
  if move[2]:
    move[5] = 0
  move[4] = 0

  
dp = [[0,0,0,0,0,0] for i in range(n+10)]
for i in range(n):
  if not any(dp[i]):
    if i:
      continue
  for k,v in enumerate(move,2):
    if v:
      dp[i+k] = list()
      for k2,v2 in enumerate(dp[i]):
        if k-2 == k2:
          v2 += 1
        dp[i+k].append(v2)
ANS = sorted([[i,j] for i,j in zip(move,dp[n])],reverse=True)
ans = ""
for i,j in ANS:
  ans += str(i) * j
print(ans)

Submission status: Wrong Answer

Solution code:
n,m = map(int, input().split())
a = sorted(list(map(int, input().split())))
match = [0,2,5,5,4,5,6,3,7,6]
move = [0,0,0,0,0,0]
for i in a:
  stick = match[i]
  move[stick-2] = i
dp = [[0,0,0,0,0,0] for i in range(n+10)]
for i in range(n):
  if not any(dp[i]):
    if i:
      continue
  for k,v in enumerate(move,2):
    if v:
      dp[i+k] = list()
      for k2,v2 in enumerate(dp[i]):
        if k-2 == k2:
          v2 += 1
        dp[i+k].append(v2)
ANS = sorted([[i,j] for i,j in zip(move,dp[n])],reverse=True)
ans = ""
for i,j in ANS:
  ans += str(i) * j
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 4)
from fractions import gcd

num = [10**9, 2, 5, 5, 4, 5, 6, 3, 7, 6]

def main():
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort(key=lambda x: (num[x], -x))
    for i in reversed(range(1, len(a))):
        if num[a[i]] == num[a[i-1]]:
            a.pop(i)
    dp = [[""]*(n+1) for _ in range(len(a))]
    dp[0][num[a[0]]] = str(a[0])
    for i in range(num[a[0]], n+1):
        if len(dp[0][i-num[a[0]]]) > 0:
            dp[0][i] = dp[0][i-num[a[0]]] + str(a[0])
    for i in range(1, len(a)):
        for j in range(n+1):
            if j < num[a[i]]:
                dp[i][j] = dp[i-1][j]
            else:
                if j == num[a[i]] or dp[i][j-num[a[i]]] != "":
                    buf = dp[i][j-num[a[i]]] + str(a[i])
                    if len(buf) < len(dp[i-1][j]):
                        dp[i][j] = dp[i-1][j]
                    else:
                        dp[i][j] = buf
                else:
                    dp[i][j] = dp[i-1][j]
    ans = list(dp[len(a)-1][n])
    ans.sort(reverse=True)
    print("".join(ans))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 4)
from fractions import gcd

num = [10**9, 2, 5, 5, 4, 5, 6, 3, 7, 6]

def main():
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort(key=lambda x: (num[x], -x))
    for i in reversed(range(1, len(a))):
        if num[a[i]] == num[a[i-1]]:
            a.pop(i)
    dp = [[""]*(n+1) for _ in range(len(a))]
    dp[0][num[a[0]]] = str(a[0])
    for i in range(num[a[0]], n+1):
        if len(dp[0][i-num[a[0]]]) > 0:
            dp[0][i] = dp[0][i-num[a[0]]] + str(a[0])
    for i in range(1, len(a)):
        for j in range(n+1):
            if j < num[a[i]]:
                dp[i][j] = dp[i-1][j]
            else:
                buf = dp[i][j-num[a[i]]] + str(a[i])
                if len(buf) < len(dp[i-1][j]):
                    dp[i][j] = dp[i-1][j]
                else:
                    dp[i][j] = buf
    ans = list(dp[len(a)-1][n])
    ans.sort(reverse=True)
    print("".join(ans))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N,_ = map(int, input().split())
A = [int(i) for i in input().split()]

INF = 10 ** 18

# 数字 : 必要なマッチの本数
n2c = dict(zip(range(1,10), [2,5,5,4,5,6,3,7,6]))

# マッチの本数 : 今回作れる数字の最大値
c2n = dict()
for a in sorted(A):
    c2n[n2c[a]] = a

# prev[i]: dp[i]の遷移元
prev = [-1] * (N + 1)
# dp[i]: ちょうどi本のマッチ棒を使うときの最大桁数
dp = [-INF] * (N + 1)

# 初期条件
dp[0] = 0
prev[0] = INF

# 貰うDP
for i in range(1, N + 1):
    for c in c2n.keys():
        if i - c >= 0 and dp[i - c] >= 0:
            if dp[i] < dp[i - c] + 1:
                dp[i] = dp[i - c] + 1
                if prev[i] < 0:
                    prev[i] = i - c
                else:
                    if c2n[i - prev[i]] < c2n[c]:
                        prev[i] = i - c

ans = []
now = N
while prev[now] != INF:
    cnt = now - prev[now]
    ans.append(c2n[cnt])
    now = prev[now]

ans.sort(reverse=True)
print(*ans, sep="")

Submission status: Wrong Answer

Solution code:
N,_ = map(int, input().split())
A = [int(i) for i in input().split()]

INF = 10 ** 18

# 数字 : 必要なマッチの本数
n2c = dict(zip(range(1,10), [2,5,5,4,5,6,3,7,6]))

# マッチの本数 : 今回作れる数字の最大値
c2n = dict()
for a in sorted(A):
    c2n[n2c[a]] = a

# prev[i]: dp[i]の遷移元 (遷移できない -> -1)
prev = [-1] * (N + 1)
# dp[i]: ちょうどi本のマッチ棒を使うときの最大桁数
dp = [0] * (N + 1)

# 初期条件
dp[0] = 0
prev[0] = INF

# 貰うDP
for i in range(1, N + 1):
    for c in c2n.keys():
        if i - c >= 0 and prev[i - c] >= 0:
            if dp[i] < dp[i - c] + 1:
                prev[i] = i - c
                dp[i] = dp[i - c] + 1

ans = []
now = N
while prev[now] != INF:
    cnt = now - prev[now]
    ans.append(c2n[cnt])
    now = prev[now]

ans.sort(reverse=True)
print(*ans, sep="")

Submission status: Wrong Answer

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

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

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

use = {i: [] for i in range(1, 10)}

for some in lists:
    howmatch = dic[some]
    use[howmatch].append(some)

data = {}

for i in range(1, 10):
    if use[i]:
        maxi = max(use[i])
        data[i] = maxi


dp=[-1 for  i in range(0,10**4+100)]

dp[0]={some:0 for some in data}

  
for i in range(1,10**4+1):
    for key in data:

        if dp[i-key]!=-1:
            if dp[i]!=-1:

                sub=dp[i].copy()
                new=dp[i-key].copy()
                new[key]+=1
                if sum(sub.values())<sum(new.values()):
                    dp[i]=new                  
            elif dp[i]==-1:
                dp[i]=dp[i-key].copy()
                dp[i][key]+=1
        else:
           pass
    
    
ans_data=dp[n]

anslist=[]

for some in data.keys():
    if ans_data[some]>0:
        for _ in range(ans_data[some]):
            anslist.append(data[some])
            
            
anslist=sorted(anslist)

A=0

for i in range(len(anslist)):
    A+=anslist[i]*(10**i)
    
print(A)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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]
wv=[]
for i in a:
  wv.append((b[i],i))
wv.sort()
dp=[-1 for i in range(n+1)]
dp[0]=0
for w,v in wv:
  for i in range(w,max(w,n+1)):
    if dp[i-w]==-1:
      continue
    dp[i]=max(dp[i],dp[i-w]*10+v)
print(dp[n])

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
A = list(map(int,input().split()))
L = [2,5,5,4,5,6,3,7,6]
dp = ['' for i in range(n+1)]
for i in range(n+1):
    for j in range(m):
        t = L[A[j]-1]
        if i < t:
            None
        else:
            if dp[i-t] == '' and dp[i] == '':
                if i-t == 0:
                    dp[i] = str(A[j])
            elif dp[i-t] != '' and dp[i] == '':
                if int(dp[i-t][0]) <= A[j]:
                    dp[i] = str(A[j])+dp[i-t]
                else:
                    dp[i] = dp[i-t]+str(A[j])
            elif dp[i-t] == '' and dp[i] != '':
                None
            else:
                cur = dp[i-t]
                comp = dp[i]
                flag = False
                for k in range(len(cur)):
                    if int(cur[k]) <= A[j]:
                        temp = cur[:k]+str(A[j])+cur[k:]
                        flag = True
                        break
                if not flag:
                    temp = cur+str(A[j])
                if int(temp) >= int(comp):
                    dp[i] = temp
print(int(dp[n]))

Submission status: Wrong Answer

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

COST = {
    1: 2,
    2: 5,
    3: 5,
    4: 4,
    5: 5,
    6: 6,
    7: 3,
    8: 7,
    9: 6,
}
A.sort(key=lambda x: (COST[x], -x))

best = [None for _ in range(N + 1)]
best[0] = tuple([0] * len(A))
for n in range(N + 1):
    for ai, a in enumerate(A):
        before = n - COST[a]
        if before < 0 or best[before] is None:
            continue
        val = tuple(x + (1 if i == ai else 0) for i, x in enumerate(best[before]))
        if (
            best[n] is None
            or sum(best[n]) < sum(val)
            or (sum(best[n]) == sum(val) and best[n] < val)
        ):
            best[n] = val

print(''.join(sorted(''.join(str(d) * n for d, n in zip(A, best[N])), reverse=True)))

Submission status: Wrong Answer

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

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

for i in range(n):
    if dp[i] == (0, 0):
        continue
    for j in a:
        t = dp[i]
        k = i + ma[j]
        if k <= n:
            dp[k] = max(dp[k], (t[0] + j * 10 ** t[1], t[1] + 1))
            dp[k] = max(dp[k], (t[0]*10 + j, t[1] + 1))

print(dp[-1][0])

Submission status: Wrong Answer

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

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

for i in range(n):
    for j in a:
        t = dp[i]
        k = i + ma[j]
        if k <= n:
            dp[k] = max(dp[k], (t[0] + j * 10 ** t[1], t[1] + 1))
            dp[k] = max(dp[k], (t[0]*10 + j, t[1] + 1))

print(dp[-1][0])