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())
l=list(map(int,input().split()))
w=[2,5,5,4,5,6,3,7,6]
dp=[0]*(max(N+1,8))
for j in l:
   dp[w[j-1]]=j
for i in range(N):
   if dp[i]!=0:
      for j in l:
         if w[j-1]+i<=N:
            dp[i+w[j-1]]=max(dp[i+w[j-1]],dp[i]*10+j)
print(dp[N])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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]
inf = float('inf')
dp = [-inf] * (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)

Submission status: Wrong Answer

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

N, M = map(int, input().split())
A = list(map(int, input().split()))
Need = [-1, 2, 5, 5, 4, 5, 6, 3, 7, 6]
Usable = {}
for a in A:
    if Need[a] in Usable:
        for key, value in Usable.items():
            if Need[a] == key and a > value:
                Usable[key] = a
    else:
        Usable[Need[a]] = a
Num = [-1] * (N + 1)
Num[0] = 0
for i in range(1, N+1):
    for u, v in Usable.items():
        if i < u:
            continue
        if Num[i - u] >= 0:
            if Num[i - u] == 0:
                Num[i] = v
            elif Num[i] < Num[i - u] * 10 + v:
                Num[i] = Num[i - u] * 10 + v

print(Num[N])

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))
Need = [-1, 2, 5, 5, 4, 5, 6, 3, 7, 6]
Usable = {}
for a in A:
    if Need[a] in Usable:
        for key, value in Usable.items():
            if Need[a] == key and a > value:
                Usable[key] = a
    else:
        Usable[Need[a]] = a
Usable = sorted(Usable.items(), reverse=True)
DP = [0] * (N + 1)
Num = [[] for _ in range(N + 1)]
for i in range(1, N+1):
    for u, v in Usable:
        if i < u:
            continue
        if DP[i] < DP[i - u] + 1:
            DP[i] = DP[i - u] + 1
            Num[i] = Num[i - u] + [v]

print(''.join(map(str, sorted(Num[N], reverse=True))))

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))
Need = [-1, 2, 5, 5, 4, 5, 6, 3, 7, 6]
Usable = {}
for a in A:
    if Need[a] in Usable:
        for key, value in Usable.items():
            if Need[a] == key and a > value:
                Usable[key] = a
    else:
        Usable[Need[a]] = a
Usable =sorted(Usable.items())
DP = [0] * (N + 1)
Num = [[] for _ in range(N + 1)]
for i in range(1, N+1):
    for u, v in Usable:
        if i < u:
            continue
        if DP[i] <= DP[i - u] + 1:
            DP[i] = DP[i - u] + 1
            Num[i] = Num[i - u] + [v]

print(''.join(map(str, sorted(Num[N], reverse=True))))

Submission status: Wrong Answer

Solution code:
def dfs(i,a,s,li):
    if s>a:
        return
    if s==a:
        Rem.append(li)
        return
    if i==M:
        return
    for j in range(6):
        dfs(i+1,a,s+A[i][1]*j,li+[A[i][0]]*j)

def check(x,ans_num):
    x.sort(reverse=True)
    S=L.copy()
    l,r=0,N//m-1
    for p in x:
        if p>ans_num:
            S[l]=str(p)
            l+=1
        else:
            S[r]=str(p)
            r-=1
    return int(''.join(S))
    

cost=[-1,2,5,5,4,5,6,3,7,6]
N,M=map(int,input().split())
A=list(map(int,input().split()))
for i in range(M):
    A[i]=[A[i],cost[A[i]]]
A.sort(key=lambda x:x[1])
m=A[0][1]
l=A[0][0]

L=[str(l)]*(N//m)

for i in range(M):
    A[i][1]-=m
mod=N%m

Rem=[]
dfs(1,mod,0,[])

res=0
for x in Rem:
    if len(x)>N//m:
        continue
    num=check(x,l)
    if num>res:
        res=num
print(res)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
e = [0,2,5,5,4,5,6,3,7,6]
d = [0] * 8
c = set()
for a in map(int, input().split()):
    m = e[a]
    d[m] = max(d[m], a)
    c.add(m)
d2 = [x for x in d if x != 0]
d2.sort(reverse=True)
c = list(c)
c.sort()
e2 = list(map(lambda x: x-c[0], e))
n = N%c[0]
i = 0
res = []
while i < len(d2):
    if n - e2[d2[i]]>=0:
        n -= e2[d2[i]]
        res.append(d2[i])
    else:
        i += 1
        if i < len(d2) and d2[i] == d[c[0]]:
            i += 1
res += [d[c[0]]]*(N//c[0]-len(res))
res.sort(reverse=True)
print("".join(map(str, res)))

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
e = [0,2,5,5,4,5,6,3,7,6]
d = [0] * 8
c = set()
for a in map(int, input().split()):
    m = e[a]
    d[m] = max(d[m], a)
    c.add(m)
d2 = [x for x in d if x != 0]
d2.sort(reverse=True)
c = list(c)
c.sort()
e2 = list(map(lambda x: x-c[0], e))
n = N%c[0]
i = 0
res = []
while i < len(d2):
    if n - e2[d2[i]]>=0:
        n -= e2[d2[i]]
        res.append(d2[i])
    else:
        i += 1
        if i < len(d2) and d2[i] == d[c[0]]:
            i += 2
res += [d[c[0]]]*(N//c[0]-len(res))
res.sort(reverse=True)
print("".join(map(str, res)))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

N, M = map(int, input().split())
A = list(map(int, input().split()))
L = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
D = defaultdict(int)

for i in A:
  if D[L[i]] < i:
    D[L[i]] = i

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

for i in range(1, N+1):
  for j in D.keys():
    if i-j >= 0:
      dp[i] = max(dp[i], dp[i-j] + 1)
    else:
      dp[i] = max(dp[i], 0)

ans = ""
temp = N

for cnt in range(dp[-1]):
  if cnt < dp[-1] - 1:
    for i, x in sorted(D.items(), key=lambda x: x[1], reverse=True):
      if temp - i >= 0 and dp[temp-i] == dp[temp] - 1:
        ans += str(x)
        temp -= i
        break
  else:
    for i, x in sorted(D.items(), key=lambda x: x[1], reverse=True):
      if temp - i == 0 and dp[temp-i] == dp[temp] - 1:
        ans += str(x)
        temp -= i
        break

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from itertools import product, permutations, combinations, combinations_with_replacement

N, M = map(int, input().split())
A = sorted(map(int, input().split()), reverse=True)
L = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
D = defaultdict(int)

for i in A:
  if D[L[i]] < i:
    D[L[i]] = i

Nums = sorted((D.keys()))

sup = N//Nums[0]
E = defaultdict(int)
Flag = False

for i in range(Nums[0]):
  if sup >= Nums[0]:
    base = (sup-i)*Nums[0]
  else:
    base = i*Nums[0]

  if base == N:
    E[Nums[0]] += sup-i
    break

  for cwr in combinations_with_replacement([0]+Nums[1:], Nums[0]):
    if base + sum(cwr) == N:
      E[Nums[0]] += base//Nums[0]
      for j in cwr:
        if j != 0:
          E[j] += 1
      Flag = True
      break
  if Flag:
    break

ans = ""
for i, x in E.items():
  ans += str(D[i])*x

print(*sorted(list(ans), reverse=True), sep="")

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from itertools import product, permutations, combinations, combinations_with_replacement

N, M = map(int, input().split())
A = list(map(int, input().split()))
L = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
D = defaultdict(int)

for i in A:
  if D[L[i]] < i:
    D[L[i]] = i

Nums = sorted((D.keys()))

sup = N//Nums[0]
E = defaultdict(int)
Flag = False

for i in range(Nums[-1]):
  base = (max(sup-Nums[-1], 0) + i) * Nums[0]
  if base == N:
    E[Nums[0]] += sup-i
    break
  for cwr in combinations_with_replacement([0]+Nums[1:], Nums[0]):
    if base + sum(cwr) == N:
      E[Nums[0]] += sup-i
      for j in cwr:
        if j != 0:
          E[j] += 1
      Flag = True
      break
  if Flag:
    break

ans = ""
for i, x in E.items():
  ans += str(D[i])*x

print(*sorted(list(ans), reverse=True), sep="")

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from itertools import product, permutations, combinations, combinations_with_replacement

N, M = map(int, input().split())
A = list(map(int, input().split()))
L = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
D = defaultdict(int)

for i in A:
  if D[L[i]] < i:
    D[L[i]] = i

Nums = sorted((D.keys()))

sup = N//Nums[0]
E = defaultdict(int)
Flag = False

for i in range(Nums[-1]):
  base = (max(sup-Nums[-1]+1, 0) + i) * Nums[0]
  if base == N:
    E[Nums[0]] += sup-i
    break
  for cwr in combinations_with_replacement([0]+Nums[1:], Nums[0]):
    if base + sum(cwr) == N:
      E[Nums[0]] += sup-i
      for j in cwr:
        if j != 0:
          E[j] += 1
      Flag = True
      break
  if Flag:
    break

ans = ""
for i, x in E.items():
  ans += str(D[i])*x

print(ans, D, Nums, E)
print(*sorted(list(ans), reverse=True), sep="")

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from itertools import product, permutations, combinations, combinations_with_replacement

N, M = map(int, input().split())
A = list(map(int, input().split()))
L = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
D = defaultdict(int)

for i in A:
  if D[L[i]] < i:
    D[L[i]] = i

Nums = sorted((D.keys()))

sup = N//Nums[0]
E = defaultdict(int)
Flag = False

for i in range(Nums[-1]):
  base = (sup-i)*Nums[0]
  if base == N:
    E[Nums[0]] += sup-i
    break
  for cwr in combinations_with_replacement(Nums[1:]+[0], Nums[0]):
    if base + sum(cwr) == N:
      E[Nums[0]] += sup-i
      for j in cwr:
        if j != 0:
          E[j] += 1
      Flag = True
      break
  if Flag:
    break

ans = ""
for i, x in E.items():
  ans += str(D[i])*x

print(*sorted(list(ans), reverse=True), sep="")

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


def main():
    N, M = NMI()
    A = NLI()

    match_dict = {i+1: m for i, m in enumerate([2,5,5,4,5,6,3,7,6])}
    usable_list = [[a, match_dict[a]] for a in A]
    usable_list.sort(key=lambda x: (x[1], -x[0]))

    def dfs(now_num, n):
        if n == 0:
            now = list(str(now_num))
            now.sort(reverse=True)
            print("".join(now))
            exit()

        for num, m in usable_list:
            if n < m:
                break
            dfs(now_num*10+num, n-m)

    dfs(0, N)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import math

n,_,*a=map(int,open(0).read().split())
match={1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}
a=sorted(a)

num=[0]*8

for d in a:
    num[match[d]]=d

dig=set(num)
dig.remove(0)

dp=[[-1]*(n+1) for _ in range(2)]
dp[0][0]=0
i=0

while True:
    flag=True
    for j in range(n):
        if dp[i][j]==-1:
            continue
        flag=False
        
        for d in dig:
            if j+match[d]>n:
                continue

            ma=dp[i][j]*10+d
            if dp[i][j]>0:
                ma=max(ma,d*10**(int(math.log10(dp[i][j]))+1)+dp[i][j])

            dp[(i+1)%2][j+match[d]]=max(dp[(i+1)%2][j+match[d]],ma)
        
        dp[i][j]=-1
    
    i=(i+1)%2
    
    if flag:
        break

print(dp[i][n])

Submission status: Wrong Answer

Solution code:
import math

n,_,*a=map(int,open(0).read().split())
match={1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}
a=sorted(a)

num=[0]*8

for d in a:
    num[match[d]]=d

dig=set(num)
dig.remove(0)

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

while True:
    flag=True
    for i in range(n):
        if dp[i]==-1:
            continue
        flag=False
        
        for d in dig:
            if i+match[d]>n:
                continue
            ma=-1
            ma=max(ma,dp[i]*10+d)
            if dp[i]>0:
                ma=max(ma,d*10**(int(math.log10(dp[i]))+1)+dp[i])

            dp[i+match[d]]=max(dp[i+match[d]],ma)
        
        dp[i]=-1
    
    if flag:
        break

print(dp[n])

Submission status: Wrong Answer

Solution code:
import math

n,_,*a=map(int,open(0).read().split())
match={1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}
a=sorted(a)

num=[0]*8

for d in a:
    num[match[d]]=d

dig=set(num)
dig.remove(0)

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

while True:
    flag=True
    for i in range(n):
        if dp[i]==-1:
            continue
        flag=False
        ma=-1

        for d in dig:
            if i+match[d]>n:
                continue

            ma=max(ma,dp[i]*10+d)
            if dp[i]>0:
                ma=max(ma,d*10**(int(math.log10(dp[i]))+1)+dp[i])

            dp[i+match[d]]=max(dp[i+match[d]],ma)
        
        dp[i]=-1
    
    if flag:
        break

print(dp[n])

Submission status: Wrong Answer

Solution code:
import math

n,_,*a=map(int,open(0).read().split())
match={1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}
a=sorted(a)

num=[0]*8

for d in a:
    num[match[d]]=d

dig=set(num)
dig.remove(0)

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

while True:
    flag=False
    for i in range(n):
        if dp[i]==-1:
            flag=True
            continue
        
        ma=-1

        for d in dig:
            if i+match[d]>n:
                continue

            ma=max(ma,dp[i]*10+d)
            if dp[i]>0:
                ma=max(ma,d*10**(int(math.log10(dp[i]))+1)+dp[i])

            dp[i+match[d]]=max(dp[i+match[d]],ma)
        
        dp[i]=-1
    
    if flag:
        break

print(dp[n])

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    N,M=mi()
    A=list(mi())

    match = [0,2,5,5,4,5,6,3,7,6] # 1-index

    dp = [0] * (10**4+10)

    X = set()
    for i in range(N):
        for a in A:
            dp[i+match[a]] = max(dp[i+match[a]], dp[i] * 10 + a)
            if i+match[a] == N:
                X.add(dp[i+match[a]])
    
    ans = 0
    for x in X:
        z = x
        cnt = 0
        while x > 0:
            y = x % 10
            cnt += match[y]
            x -= y
            x //= 10
        if cnt == N:
            ans = max(ans,z)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    N,M=mi()
    A=list(mi())

    match = [0,2,5,5,4,5,6,3,7,6] # 1-index

    dp = [[0]*(N+10) for _ in range(10**4)]

    i = 1
    # for i in range(100):
    J = set([N])
    _J = set()
    while True:
        mx = 0
        X = set()
        newJ = set()
        for j in J:
            for a in A:
                if j-match[a] < 0: continue
                dp[i][j-match[a]] = max(dp[i][j-match[a]],dp[i-1][j]*10 + a)
                newJ.add(j-match[a])

        _J = J
        J = newJ
        # print(J)
        if len(J) == 0:
            break

        i += 1
    
    i -= 1
    ans = 0
    for j in _J:
        x = dp[i][j] 
        if x == 0: continue
        elif i != len(str(x)): continue

        z = x
        cnt = 0
        while x > 0:
            y = x % 10
            cnt += match[y]
            x -= y
            x //= 10
        if cnt == N:
            ans = max(ans,z)
 
    print(ans)
 

    



if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    N,M=mi()
    A=list(mi())

    match = [0,2,5,5,4,5,6,3,7,6] # 1-index

    dp = [[0]*(N+10) for _ in range(10**4)]

    i = 1
    # for i in range(100):
    J = set([N])
    while True:
        mx = 0
        X = set()
        newJ = set()
        for j in J:
            for a in A:
                if j-match[a] < 0: continue
                dp[i][j-match[a]] = max(dp[i][j-match[a]],dp[i-1][j]*10 + a)
                newJ.add(j-match[a])

        J = newJ
        # print(J)
        if len(J) == 0:
            break

        i += 1
    
    i -= 1
    ans = 0
    for x in dp[i]: 
        if x == 0: continue
        elif i != len(str(x)): continue

        z = x
        cnt = 0
        while x > 0:
            y = x % 10
            cnt += match[y]
            x -= y
            x //= 10
        if cnt == N:
            ans = max(ans,z)
 
    print(ans)
 

    



if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from math import log10
n,m = map(int,input().split())
a = list(map(int,input().split()))
l = [0,2,5,5,4,5,6,3,7,6]

dp = [0]*(n+1)
for i in range(n):
    for j in range(m):
        if dp[i] == 0 and i != 0:
            continue
        x = a[j]
        t = l[x]
        if i+t > n:
            continue
        if dp[i] == 0:
            s0 = x
            s1 = x
        else:
            k = int(log10(dp[i]))
            s0 = x*10**(k+1)+dp[i]
            s1 = 10*dp[i]+x
        dp[i+t] = max(dp[i+t],s0,s1)
print(dp[-1])

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
from collections import defaultdict
a=list(map(int,input().split()))
dic={i:[2,5,5,4,5,6,3,7,6][i-1]for i in range(1,10)}
s=defaultdict(int)
for i in a:
    s[dic[i]]=max(s[dic[i]],i)
ok=list(s.items())#hon,digit
dp=defaultdict(int)
for i in range(1,n+1):
    for h,d in ok:
        if h<=i:
            dp[i]=max(dp[i],dp[i-h]+1)
from operator import itemgetter as it 
ok.sort(reverse=1,key=it(1))
ans=''
now=n
keta=dp[n]
while keta>1:
    for h,d in ok:
        if now>=h and dp[now]==dp[now-h]+1:
            ans+=str(d);now-=h;keta-=1;break
print(ans+str(s[now]))

Submission status: Wrong Answer

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

if N % 2 == 0:
  if 1 in A:
    print(int('1'*(N//2)))
    exit()

need =(2,5,5,4,5,6,3,7,6)
    
if N % 2 == 1:
  if 1 in A:
    minodd=10
    argmin=0
    for i in range(M):
      if need[A[i]-1] % 2 == 1 and need[A[i]-1]<=minodd:
        minodd=need[A[i]-1]
        if A[i] > argmin:
          argmin=A[i]
    N -= minodd
    print(int(str(argmin)+'1'*(N//2)))
    exit()

if 2 in A and 3 in A:
  del A[A.index(2)]
if 3 in A and 5 in A:
  del A[A.index(3)]
if 6 in A and 9 in A:
  del A[A.index(6)]
if 1 in A and 4 in A:
  del A[A.index(4)]
if 6 in A and 7 in A:
  del A[A.index(6)] 
if 7 in A and 9 in A:
  del A[A.index(9)] 
if 1 in A and 6 in A:
  del A[A.index(6)] 
if 1 in A and 9 in A:
  del A[A.index(9)] 
  
A = tuple(A)
M = len(A)

dp = [[0]*(N+1) for _ in range(M)]
dpmax = [0]*(N+1)

def take_max():
  return max(A[i]*(10**len(str(tmp2)) + tmp2,tmp2*10+A[i]))

for j in range(2,N+1):
  tmpmax = 0
  for i in range(M):
    tmp = need[A[i]-1]
    if j == tmp:
      dp[i][j] = A[i]
    elif j > tmp:
      if dpmax[j-tmp] != 0:
        tmp2 = dpmax[j-tmp]
        dp[i][j] = take_max()
    if tmpmax < dp[i][j]:
      tmpmax = dp[i][j]
  dpmax[j] = tmpmax
  
print(dpmax[-1])

Submission status: Wrong Answer

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

if N % 2 == 0:
  if 1 in A:
    print(int('1'*(N//2)))
    exit()

need =(2,5,5,4,5,6,3,7,6)
    
if N % 2 == 1:
  if 1 in A:
    minodd=10
    argmin=0
    for i in range(M):
      if need[A[i]-1] % 2 == 1 and need[A[i]-1]<minodd:
        minodd=need[A[i]-1]
        argmin=A[i]
    N -= minodd
    print(int(str(argmin)+'1'*(N//2)))
    exit()

if 2 in A and 3 in A:
  del A[A.index(2)]
if 3 in A and 5 in A:
  del A[A.index(3)]
if 6 in A and 9 in A:
  del A[A.index(6)]
if 1 in A and 4 in A:
  del A[A.index(4)]
if 6 in A and 7 in A:
  del A[A.index(6)] 
if 7 in A and 9 in A:
  del A[A.index(9)] 
if 1 in A and 6 in A:
  del A[A.index(6)] 
if 1 in A and 9 in A:
  del A[A.index(9)] 
  
A = tuple(A)
M = len(A)

dp = [[0]*(N+1) for _ in range(M)]
dpmax = [0]*(N+1)

def take_max():
  return max(A[i]*(10**len(str(tmp2)) + tmp2,tmp2*10+A[i]))

for j in range(2,N+1):
  tmpmax = 0
  for i in range(M):
    tmp = need[A[i]-1]
    if j == tmp:
      dp[i][j] = A[i]
    elif j > tmp:
      if dpmax[j-tmp] != 0:
        tmp2 = dpmax[j-tmp]
        dp[i][j] = take_max()
    if tmpmax < dp[i][j]:
      tmpmax = dp[i][j]
  dpmax[j] = tmpmax
  
print(dpmax[-1])

Submission status: Wrong Answer

Solution code:
def examA():
    A, B = LI()
    if B%A==0:
        ans = A+B
    else:
        ans = B-A
    print(ans)
    return

def examB():
    N, M = LI()
    Flag = [0]*M
    for i in range(N):
        K = LI()
        for j in range(1,K[0]+1):
            Flag[K[j]-1] +=1
    ans = 0
    for i in Flag:
        if i==N:
            ans +=1
    print(ans)
    return

def gcd(x,y):
    if y==0:
        return x
    while(y!=0):
        x, y = y,x%y
    return x
def examC():
    N = I()
    A = LI()
    cur = A[0]
    for i in range(N-1):
        cur = gcd(cur,A[i+1])
    ans = cur
    print(ans)
    return

def examD():
    N, M = LI()
    A = LI(); A.sort()
    Matti = [2,5,5,4,5,6,3,7,6]
    D = {}
    for a in A:
        D[Matti[a-1]] = a
    #print(D)
    dp = [-inf]*(N+10)
    dp[0] = 0
    for i in range(N):
        for matti,num in D.items():
            dp[i+matti] = max(dp[i+matti],dp[i]+1)
    #print(dp)
    used = []
    i = N
    while(i>0):
        #print(i)
        #input()
        for matti,num in D.items():
            if i-matti<0:
                continue
            if dp[i-matti]==dp[i]-1:
                used.append(num)
                i -= matti
    #print(used)
    used.sort(reverse=True)
    ans = "".join(map(str,used))
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examD()


"""
31 2
5 8
"""

Submission status: Wrong Answer

Solution code:
def examA():
    A, B = LI()
    if B%A==0:
        ans = A+B
    else:
        ans = B-A
    print(ans)
    return

def examB():
    N, M = LI()
    Flag = [0]*M
    for i in range(N):
        K = LI()
        for j in range(1,K[0]+1):
            Flag[K[j]-1] +=1
    ans = 0
    for i in Flag:
        if i==N:
            ans +=1
    print(ans)
    return

def gcd(x,y):
    if y==0:
        return x
    while(y!=0):
        x, y = y,x%y
    return x
def examC():
    N = I()
    A = LI()
    cur = A[0]
    for i in range(N-1):
        cur = gcd(cur,A[i+1])
    ans = cur
    print(ans)
    return

def examD():
    N, M = LI()
    A = LI(); A.sort()
    Matti = [2,5,5,4,5,6,3,7,6]
    D = {}
    for a in A:
        D[Matti[a-1]] = a
    #print(D)
    dp = [0]*(N+10)
    for i in range(N):
        for matti,num in D.items():
            dp[i+matti] = max(dp[i+matti],dp[i]+1)
    #print(dp[N])
    used = []
    i = N
    while(i>0):
        for matti,num in D.items():
            if i<matti:
                continue
            if dp[i-matti]==dp[i]-1:
                used.append(num)
                i -= matti
    #print(used)
    used.sort(reverse=True)
    ans = "".join(map(str,used))
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examD()

Submission status: Wrong Answer

Solution code:
import math
n, m = map(int, input().split())
aas = list(map(int, input().split()))
needs = {1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}
dp = {}
def rc(rn):
    if rn in dp:
        return dp[rn]
    if rn == 0:
        return 0
    ret = 0
    for i in aas:
        if needs[i] <= rn:
            try:
                tmp = rc(rn-needs[i])
                if tmp == 0:
                    ret = max(ret, i)
                else:
                    ret = max(ret, i*pow(10,int(math.log10(tmp)+1))+tmp)
            except:
                pass
    if ret == 0:
        return "err"
    dp[rn] = ret
    return ret
print(rc(n))

Submission status: Wrong Answer

Solution code:
import math
n, m = map(int, input().split())
aas = list(map(int, input().split()))
needs = {1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}
dp = [0]*(n+1)
for i in range(n+1):
    for k in aas:
        idx = i+needs[k]
        if idx <= n:
            dpi = dp[i]
            if dpi != 0:
                dp[idx] = max(dp[idx],k*(pow(10,int(math.log10(dpi)+1)))+dpi)
            elif i == 0:
                dp[idx] = max(dp[idx],k)
print(dp[n])

Submission status: Wrong Answer

Solution code:
import sys
N,M = map(int,sys.stdin.readline().rstrip().split())
A = list(map(int,sys.stdin.readline().rstrip().split()))

from collections import defaultdict

d = defaultdict(int)  # d[i] = (Aの中でi本用いて表せる最大の数)
for i in range(M):
    if A[i] == 1:
        d[2] = 1
    elif A[i] == 7:
        d[3] = 7
    elif A[i] == 4:
        d[4] = 4
    elif A[i] in [2,3,5]:
        d[5] = max(d[5],A[i])
    elif A[i] in [6,9]:
        d[6] = max(d[6],A[i])
    else:
        d[7] = 8

B = list(d.keys())
B.sort()

a = B[0]
B[0] = 0

if N % a == 0:
    print(''.join([str(d[a])]*(N//a)))
    exit()

from itertools import combinations_with_replacement

for i in range(N//a,-1,-1):  # aをi回用いる
    x = N-a*i
    for u in list(combinations_with_replacement(B,5)):
        if sum(u) == x:
            r = i
            s = []
            for j in range(5):
                if u[j] != 0:
                    s.append(u[j])
            break
    else:
        continue
    break

C = [d[a]]*r + [d[i] for i in s]
C.sort(reverse=True)

ans = ''
for i in C:
    ans += str(i)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
N,M = map(int,sys.stdin.readline().rstrip().split())
A = list(map(int,sys.stdin.readline().rstrip().split()))

if M == 1:
    print(''.join([str(A[0])]*N))
    exit()

from collections import defaultdict

d = defaultdict(int)  # d[i] = (Aの中でi本用いて表せる最大の数)
for i in range(M):
    if A[i] == 1:
        d[2] = 1
    elif A[i] == 7:
        d[3] = 7
    elif A[i] == 4:
        d[4] = 4
    elif A[i] in [2,3,5]:
        d[5] = max(d[5],A[i])
    elif A[i] in [6,9]:
        d[6] = max(d[6],A[i])
    else:
        d[7] = 8

B = list(d.keys())
B.sort()

a = B[0]
B[0] = 0

if N % a == 0:
    print(''.join([str(d[a])]*(N//a)))
    exit()

from itertools import combinations_with_replacement

for i in range(N//a,-1,-1):  # aをi回用いる
    x = N-a*i
    for u in list(combinations_with_replacement(B,5)):
        if sum(u) == x:
            r = i
            s = []
            for j in range(5):
                if u[j] != 0:
                    s.append(u[j])
            break
    else:
        continue
    break

C = [d[a]]*r + [d[i] for i in s]
C.sort(reverse=True)

ans = ''
for i in C:
    ans += str(i)
print(ans)

Submission status: Wrong Answer

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

req = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
Q = [(req[a], a) for a in A]
Q.sort(key=lambda x: x[1], reverse=True)

t = [0]*(N+1)
for i in range(N+1):
    for q, d in Q:
        if i - q >= 0:
            t[i] = max(t[i], t[i-q]+1)
T = t[-1]
ans = []
MIN = min(Q)[0]
for i in range(T-1):
    for q, d in Q:
        if N-q >= (T-1-i)*MIN:
            ans.append(d)
            N -= q
            break
for q, d in Q:
    if N-q == 0:
        ans.append(d)
        break

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

Submission status: Wrong Answer

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

req = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
Q = [(req[a], a) for a in A]
Q.sort(key=lambda x: x[1], reverse=True)

t = [0]*(N+1)
for i in range(N+1):
    for q, d in Q:
        if i - q >= 0:
            t[i] = max(t[i], t[i-q]+1)
T = max(t)
ans = []
MIN = min(Q)[0]
for i in range(T-1):
    for q, d in Q:
        if N-q >= (T-1-i)*MIN:
            ans.append(d)
            N -= q
            break
for q, d in Q:
    if N-q == 0:
        ans.append(d)
        break

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

Submission status: Wrong Answer

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

req = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
minR = min(req[a] for a in A)
R = [(req[a], a) for a in A if req[a] < 2*minR]
R.sort(reverse=True)
Q = []
p = -1
for r in R:
    if r[0] == p:
        continue
    p = r[0]
    Q.append(r)

t = [0]*(N+1)
for i in range(N+1):
    for q, d in Q:
        if i - q >= 0:
            t[i] = max(t[i], t[i-q]+1)
T = max(t)
ans = []
Q.sort(key=lambda x: x[1], reverse=True)
for i in range(T-1):
    for q, d in Q:
        if N-q >= (T-1-i)*minR:
            ans.append(d)
            N -= q
            break
for q, d in Q:
    if N-q == 0:
        ans.append(d)
        break

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