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:
B=[-1,2,5,5,4,5,6,3,7,6]
N,M=map(int,input().split())
A=[int(i) for i in input().split()]
X=sorted([(B[i],-i) for i in A])
Y=[0 for i in range(10)]
dp=[[0 for j in range(N+1)] for i in range(M+1)]
dp[0][0]=1
dp2=[0 for i in range(N+1)]
for i in range(M):
    a=X[i][0]
    tmp=[0 for k in range(a)]
    for j in range(N+1):
        if dp[i][j]==1:
            tmp[j%a]=1
        if tmp[j%a]==1:
            dp[i+1][j]=1
            if dp2[j]==0:
                dp2[j]=-X[i][1]
#print(dp[M])
t=N%X[0][0]
s=-1
for j in range(t,N+1,X[0][0]):
    if dp[M][j]==1:
        s=j
        break
if s==-1:
    exit()
#print(dp2)
Y[-X[0][1]]+=(N-s)//X[0][0]
L=[]
while(s>0):
    L.append(dp2[s])
    s-=B[dp2[s]]
#print(L)
#print(X)
for i in L:
    Y[i]+=1
#print(Y)
R=[]
for i in range(10):
    for j in range(Y[i]):
        R.append(i)
R.sort(reverse=True)
ans=""
for i in R:
    ans=ans+str(i)
print(ans)

Submission status: Wrong Answer

Solution code:
from sys import stdin

N, M, *A = map(int, stdin.read().split())
req = {1: 2,
       2: 5,
       3: 5,
       4: 4,
       5: 5,
       6: 6,
       7: 3,
       8: 7,
       9: 6}

num = {a: req[a] for a in A}
num_min = min(num.items(), key=lambda x: x[1])
rem = sorted([(k, n-num_min[1]) for k, n in num.items()], reverse=True)
order = N // num_min[1]
sum_rem = N - num_min[1]*order

s = ''
for _ in range(order):
    if sum_rem:
        for k, n in rem:
            if sum_rem >= n:
                s += str(k)
                sum_rem -= n
                break
    else:
        s += str(num_min[0])

print(s)

Submission status: Wrong Answer

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

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

def match(i):
    ANS=0
    for s in str(i):
        ANS+=M[int(s)]

    return ANS
        

def dfs(i,NOW):
    if NOW==N:
        L=sorted(list(i),reverse=True)
        
        print("".join(L))
        sys.exit()
    elif NOW>N:
        return
    else:
        for a in A:
            dfs(i+str(a),NOW+M[a])


A.sort(reverse=True)
#print(A)
A.sort(key=lambda x:M[x])
#print(A)

dfs("",0)

Submission status: Wrong Answer

Solution code:
B=[-1,2,5,5,4,5,6,3,7,6]
N,M=map(int,input().split())
A=[int(i) for i in input().split()]
X=sorted([(B[i],i) for i in A])
Y=[0 for i in range(10)]
dp=[[0 for j in range(N+1)] for i in range(M+1)]
dp[0][0]=1
dp2=[0 for i in range(N+1)]
for i in range(M):
    a=X[i][0]
    tmp=[0 for k in range(a)]
    for j in range(N+1):
        if dp[i][j]==1:
            tmp[j%a]=1
        if tmp[j%a]==1:
            dp[i+1][j]=1
            if dp2[j]==0:
                dp2[j]=X[i][1]
#print(dp[M])
t=N%X[0][0]
s=-1
for j in range(t,N+1,X[0][0]):
    if dp[M][j]==1:
        s=j
        break
if s==-1:
    exit()
#print(dp2)
Y[X[0][1]]+=(N-s)//X[0][0]
L=[]
while(s>0):
    L.append(dp2[s])
    s-=B[dp2[s]]
#print(L)
#print(X)
for i in L:
    Y[i]+=1
#print(Y)
R=[]
for i in range(10):
    for j in range(Y[i]):
        R.append(i)
R.sort(reverse=True)
ans=""
for i in R:
    ans=ans+str(i)
print(ans)

Submission status: Time Limit Exceeded

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)
Num = [-1] * (N + 1)
Num[0] = ''
for i in range(1, N+1):
    for u, v in Usable:
        if i < u:
            continue
        if type(Num[i - u]) is str:
            if Num[i - u] == '':
                Num[i] = Num[i - u] + str(v)
            elif int(Num[i]) < int(Num[i - u] + str(v)):
                Num[i] = Num[i - u] + str(v)

print(Num[N])

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline


def main():
    match = [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 + 1)
    dp[0] = ""

    for i in range(N):
        for a in A:
            b = match[a]
            if i + 1 >= b:
                if dp[i + 1 - b] != "0":
                    tmp = dp[i + 1 - b]
                    tmp += str(a)
                    tmp = ''.join(sorted(tmp, reverse=True))
                    dp[i + 1] = str(max(dp[i + 1], tmp, key=int))

    print(dp[N])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict as dd
n, m = map(int, input().split())
A = list(map(int, input().split()))

Arr = [2, 5, 5, 4, 5, 6, 3, 7, 6]
#num_match[num] => match_num
num_match = {}
for i, val in enumerate(Arr):
    num_match[i+1] = val

#match_num -> num
match_to_num = dd(int)
#num -> match_num
num_to_match = dd(int)
for a in A:
    match = num_match[a]
    num_to_match[a] = match
    match_to_num[match] = max(match_to_num[match], a)
cands = sorted(match_to_num.keys())
#print(cands)

#print(match_to_num)

def f(str1, str2):
    if str2 == None:
        return str1
    if len(str1) > len(str2):
        return str1
    elif len(str1) == len(str2):
        return max(str1, str2)
    else:
        return str2
#print(f("aa", "bb"))


import bisect
def concat(string, char):
    lis = list(string)[::-1]
    #print(lis)
    bisect.insort_left(lis, char)
    return "".join(lis[::-1])
#print(concat("1234", "2"))

dp = [None for i in range(n+1)]
dp[0] = ""
#print(dp[0])
#print(concat("", "1"))

#dp[match] -> digit
for i in range(n):
    for match in cands:
        if dp[i] != None:
            try:
                dp[i + match] = f(concat(dp[i], str(match_to_num[match])), dp[i + match])
                #print(i, dp[i], end = " (try replace)=> ")
                #print(i + match, dp[i+match])
            except:
                pass
digit = dp[n]
print(digit)

Submission status: Time Limit Exceeded

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) for _ in range(10**4+10)]

    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: Time Limit Exceeded

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) for _ in range(10**4+10)]

    i = 1
    # for i in range(100):
    while True:
        mx = 0
        X = set()
        for j in range(N,0,-1):
            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)
                if j-match[a] == 0:
                    mx = max(mx,dp[i][j-match[a]])
                    # print("mx",mx)
                    X.add(mx)

        # print(max(dp[i]))
        
        if i != len(str(mx)):
            break
        i += 1
    
    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: Time Limit Exceeded

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

def nax(a, b):
    if a == '-':
        return b
    return a if int(a)>int(b) else b


match = [2,5,5,4,5,6,3,7,6]
# dp[i]  : iほんのマッチを使ってできる数値の最大値
dp = ['-'] * 10101
dp[0] = ''

for i in range(N+1):
    if dp[i] == '-':
        continue
    for a in A:
        dp[i+match[a-1]] = nax(dp[i+match[a-1]], dp[i] + chr(ord('0') + a))

print(dp[N])

Submission status: Time Limit Exceeded

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]

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 = len(str(dp[i]))
            s0 = x*10**(k)+dp[i]
            s1 = 10*dp[i]+x
        dp[i+t] = max(dp[i+t],s0,s1)
print(dp[-1])

Submission status: Time Limit Exceeded

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]

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:
            s0 = str(x)+str(dp[i])
            s1 = str(dp[i])+str(x)
        dp[i+t] = max(dp[i+t],int(s0),int(s1))
print(dp[-1])

Submission status: Time Limit Exceeded

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

need =(2,5,5,4,5,6,3,7,6)

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: Time Limit Exceeded

Solution code:
from numba import jit

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

need =(2,5,5,4,5,6,3,7,6)

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)

@jit
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: Time Limit Exceeded

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

need =(2,5,5,4,5,6,3,7,6)

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)

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] = max(A[i]*(10**len(str(tmp2)) + tmp2,tmp2*10+A[i]))
    if tmpmax < dp[i][j]:
      tmpmax = dp[i][j]
  dpmax[j] = tmpmax
  
print(dpmax[-1])

Submission status: Time Limit Exceeded

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

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

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

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)] 
  
M = len(A)

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

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] = max(A[i]*(10**len(str(tmp2)) + tmp2,tmp2*10+A[i]))
    if tmpmax < dp[i][j]:
      tmpmax = dp[i][j]
  dpmax[j] = tmpmax
  
print(dpmax[-1])

Submission status: Time Limit Exceeded

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

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

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

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)]
  
M = len(A)

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

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] = max(A[i]*(10**len(str(tmp2)) + tmp2,tmp2*10+A[i]))
    if tmpmax < dp[i][j]:
      tmpmax = dp[i][j]
  dpmax[j] = tmpmax
  
print(dpmax[-1])

Submission status: Time Limit Exceeded

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

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

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

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

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] = max(A[i]*(10**len(str(tmp2)) + tmp2,tmp2*10+A[i]))
    if tmpmax < dp[i][j]:
      tmpmax = dp[i][j]
  dpmax[j] = tmpmax
  
print(dpmax[-1])

Submission status: Time Limit Exceeded

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

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

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

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

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

Submission status: Time Limit Exceeded

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

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

dp = [[0 for i in range(N+1)] for j in range(M)]
dpmax = [0 for i in range(N+1)]

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

Submission status: Time Limit Exceeded

Solution code:
n,m=list(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}
kind={}

for i in range(1,10):
    for aa in a:
        if i==aa:
            kind[match[i]]=i
m=len(kind)

inf=10**10

dp=[[-inf]*(n+1) for _ in range(m+1)]
cnt=[[0]*(n+1) for _ in range(m+1)]

dp[0][0]=0

a=sorted(list(kind.values()),reverse=True)
cost=[match[aa] for aa in a]
for i in range(m):
    cm=cost[i]

    for j in range(n+1):
        dp[i+1][j]=dp[i][j]

        if j>=cm and dp[i+1][j]<dp[i+1][j-cm]+1:
            dp[i+1][j]=dp[i+1][j-cm]+1

maxlen=dp[m][n]

def rec(x,i,s):
    if x==0 and len(s)==maxlen:
        print(s)
        exit(0)
    if i==m:
        return

    j=x//cost[i]
    while j>=0:
        rec(x-j*cost[i],i+1,s+''.join([str(a[i]) for _ in range(j)]))
        j-=1
    
rec(n,0,'')

Submission status: Time Limit Exceeded

Solution code:
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,len(str(dpi))))+dpi)
            elif i == 0:
                dp[idx] = max(dp[idx],k)
print(dp[n])

Submission status: Time Limit Exceeded

Solution code:
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)
dp[0] = ""
for i in range(n+1):
    for k in aas:
        idx = i+needs[k]
        if idx <= n and dp[i] != 0:
            dp[idx] = str(max(int(dp[idx]),int(str(k)+str(dp[i]))))
print(dp[n])

Submission status: Time Limit Exceeded

Solution code:
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)
dp[0] = ""
for i in range(n+1):
    for k in aas:
        if i+needs[k] <= n and dp[i] != 0:
            dp[i+needs[k]] = str(max(int(dp[i+needs[k]]),int(str(k)+str(dp[i]))))
print(dp[n])

Submission status: Time Limit Exceeded

Solution code:
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]*10 for _ in range(n+1)]
for j in range(10):
    dp[0][j] = ""
for i in range(n+1):
    for j in range(10):
        for k in aas:
            if i+needs[k] <= n:
                if dp[i][j] != 0:
                    dp[i+needs[k]][k] = str(max(int(dp[i+needs[k]][k]),int(str(k)+str(dp[i][j]))))
res = 0
for i in dp[n]:
    res = max(res,int(i))
print(res)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int,raw_input().split(' '))
ais= map(int, raw_input().split(' '))

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

cost  = {i+1:v for i,v in enumerate([2,5,5,4,5,6,3,7,6])}

def f(c,dp,suffix):

	a = dp[c] if (dp[c] is not None) else ()
	if a is None: return b
	if len(a) > len(suffix) + 1:
		return a
	b = tuple(sorted(list((digit,) + suffix))[::-1])
	if len(b) > len(a): return b
	return max(a,b)
	
for c in range(1,n + 1):
	for digit in ais:
		if c >= cost[digit] and dp[c-  cost[digit]] is not None:
			dp[c] = f(c,dp,dp[c-cost[digit]]) 
print ''.join(map(str,list(dp[n])))

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int,raw_input().split(' '))
ais= map(int, raw_input().split(' '))

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

cost  = {i+1:v for i,v in enumerate([2,5,5,4,5,6,3,7,6])}

def f(c,dp,suffix):
	a = dp[c] if dp[c] is not None else ()
	b = tuple(sorted(list((digit,) + suffix))[::-1])
	if len(b) > len(a): return b
	if len(a) > len(b): return a
	return max(a,b)
	
for c in range(1,n + 1):
	for digit in ais:
		if c >= cost[digit] and dp[c-  cost[digit]] is not None:
			dp[c] = f(c,dp,dp[c-cost[digit]]) 
print ''.join(map(str,list(dp[n])))

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int,raw_input().split(' '))
ais= map(int, raw_input().split(' '))

dp = {0:()}
cost  = {i+1:v for i,v in enumerate([2,5,5,4,5,6,3,7,6])}
def f(c,dp,suffix):
	a = dp[c] if c in dp else ()
	b = tuple(sorted(list((digit,) + suffix))[::-1])
	if len(b) > len(a): return b
	if len(a) > len(b): return a
	return max(a,b)
	

for c in range(1,n + 1):
	for digit in ais:
		if c >= cost[digit] and (c - cost[digit]) in dp:
			dp[c] = f(c,dp,dp[c-cost[digit]]) 

print ''.join(map(str,list(dp[n])))

Submission status: Time Limit Exceeded

Solution code:
def main():  
  N,M=map(int,input().split())
  A=list(map(int,input().split()))
  dp=[2,5,5,4,5,6,3,7,6]
  p=[]
  q=[]
  for i in range(M):
    p.append(dp[A[i]-1])
    q.append(str(A[i]))
  bp=['0']*(N+1)
  for i in range(N-1):
    for j in range(len(p)):
      if i+p[j]>N:
        continue
      if bp[i]=='0':
          if i!=0:
              continue
      bp[i+p[j]]=str(max(int(bp[i+p[j]]),int(q[j]+bp[i])))
  ans=bp[N]
  ans=ans.rstrip('0')
  print(ans)
if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
A=list(map(int,input().split()))
dp=[2,5,5,4,5,6,3,7,6]
p=[]
for i in range(M):
  p.append([dp[A[i]-1],A[i]])
bp=[]
for i in range(N+1):
  bp.append('0')
for i in range(N-1):
  for j in range(len(p)):
    if i+p[j][0]>N:
      continue
    if bp[i]=='0':
        if i!=0:
            continue
    bp[i+p[j][0]]=str(max(int(bp[i+p[j][0]]),int(str(p[j][1])+bp[i])))
ans=bp[N]
ans=ans.rstrip('0')
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, M = mapint()
As = list(mapint())
num_lis = [2, 5, 5, 4, 5, 6, 3, 7, 6]
need_m = [num_lis[a-1] for a in As]
dp = [-1]*(N+1)
dp[0] = 0

for i in range(1, N+1):
    for a, need in zip(As, need_m):
        if need>i:
            continue
        elif dp[i-need]==-1:
            continue
        elif dp[i-need]==0:
            dp[i] = max(dp[i], a)
        else:
            dp[i] = max(dp[i], int(str(a)+str(dp[i-need])))

print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, M = mapint()
As = list(mapint())
num_lis = [2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [-1]*(N+1)
dp[0] = 0

for i in range(1, N+1):
    for a in As:
        need = num_lis[a-1]
        if need>i:
            continue
        elif dp[i-need]==-1:
            continue
        elif dp[i-need]==0:
            dp[i] = max(dp[i], a)
        else:
            dp[i] = max(dp[i], int(str(a)+str(dp[i-need])))

print(dp[-1])

Submission status: Time Limit Exceeded

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

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

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

# たとえば2と3を両方作れるときに、2を作るメリットはない。
if 2 in A and 3 in A:
  A.remove(2)
if 2 in A and 5 in A:
  A.remove(2)
if 3 in A and 5 in A:
  A.remove(3)
if 6 in A and 9 in A:
  A.remove(6)

# ある本数を使ったときに、作った桁数が大きいほうが有利
# 使った本数でダイクストラ

dp = [-1] * (N + 1)
dp[0] = 0
import heapq
# 使った本数, 作った数(最後に降順に並べ替える)
q = [(0,"")]
heapq.heapify(q)
while q:
  used, num = heapq.heappop(q)
  #print("used",used,"num",num)
  if used > N:
    continue
  #print("num",num)
  if num == "":
    num = 0
  else:
    num = int("".join(sorted(num,reverse = True)))
  if dp[used] > num:
    # すでに作った数より桁数が小さい
    continue
  dp[used] = num
  if used == N:
    continue
  for a in A:
    if num == 0:
      numstr = ""
    else:
      numstr = str(num)
    heapq.heappush(q,(used + dic[a],numstr + str(a)))

print(dp[N])

Submission status: Time Limit Exceeded

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

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

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

# たとえば2と3を両方作れるときに、2を作るメリットはない。
if 2 in A and 3 in A:
  A.remove(2)
if 2 in A and 5 in A:
  A.remove(2)
if 3 in A and 5 in A:
  A.remove(3)
if 6 in A and 9 in A:
  A.remove(6)

# ある本数を使ったときに、作った桁数が大きいほうが有利
# 使った本数でダイクストラ

dp = [-1] * (N + 1)
dp[0] = 0
import heapq
# 桁数, 使った本数, 作った数(最後に降順に並べ替える)
q = [(0,0,"")]
heapq.heapify(q)
while q:
  digit, used, num = heapq.heappop(q)
  #print("used",used,"num",num)
  if used > N:
    continue
  #print("num",num)
  if num == "":
    num = 0
  else:
    num = int("".join(sorted(num,reverse = True)))
  if dp[used] > num:
    # すでに作った数より桁数が小さい
    continue
  dp[used] = num
  if used == N:
    continue
  for a in A:
    if num == 0:
      numstr = ""
    else:
      numstr = str(num)
    heapq.heappush(q,(digit - 1,used + dic[a],numstr + str(a)))

print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
# match matching
import bisect
import sys
input = sys.stdin.readline
compare = [10**i for i in range(5*10**3+1)]
N, M = map(int, input().split())
ok = list(map(int, input().split()))
a = [i for i in range(1, 10)]
b = [2, 5, 5, 4, 5, 6, 3, 7, 6]
data = {a[i]: b[i] for i in range(9)}
how = {i: [] for i in range(2, 8)}
for n in ok:
    how[data[n]].append(n)
new = []
for i in range(2, 8):
    if len(how[i]) > 0:
        new.append(max(how[i]))
new.sort()
ok = new
dp = [[0 for i in range(N+1)] for j in range(M+1)]


def find(X):
    return bisect.bisect_right(compare, X)


for i in range(M):
    for cnt in range(N+1):
        for num in ok[:i+1]:
            cost = data[num]
            if cnt > cost:
                K = dp[i+1][cnt-cost]
                if K > 0:
                    dp[i+1][cnt] = max(K + num*10 ** find(K), dp[i+1][cnt])
                    continue
                else:
                    dp[i+1][cnt] = max(K, dp[i+1][cnt])
                    continue
            elif cnt == cost:
                dp[i+1][cnt] = max(num, dp[i+1][cnt])
                continue
            else:
                dp[i+1][cnt] = max(dp[i][cnt], dp[i+1][cnt])
                continue
ans = dp[M][N]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# match matching
import bisect
import sys
input = sys.stdin.readline
compare = [10**i for i in range(5*10**3+1)]
N, M = map(int, input().split())
ok = list(map(int, input().split()))
a = [i for i in range(1, 10)]
b = [2, 5, 5, 4, 5, 6, 3, 7, 6]
data = {a[i]: b[i] for i in range(9)}
how = {i: [] for i in range(2, 8)}
for n in ok:
    how[data[n]].append(n)
new = []
for i in range(2, 8):
    if len(how[i]) > 0:
        new.append(max(how[i]))
new.sort()
ok = new
dp = [[0 for i in range(N+1)] for j in range(M+1)]


def find(X):
    return bisect.bisect_right(compare, X)


for i in range(M):
    for cnt in range(N+1):
        for num in ok[:i+1]:
            cost = data[num]
            if cnt > cost:
                K = dp[i+1][cnt-cost]
                if K > 0:
                    dp[i+1][cnt] = max(K + num*10 ** find(K), dp[i+1][cnt])
                    continue
                else:
                    dp[i+1][cnt] = max(K, dp[i+1][cnt])
                    continue
            elif cnt == cost:
                dp[i+1][cnt] = max(num, dp[i+1][cnt])
                continue
            else:
                dp[i+1][cnt] = max(dp[i][cnt], dp[i+1][cnt])
                continue
ans = dp[M][N]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# match matching
import bisect
import sys
input = sys.stdin.readline
compare = [10**i for i in range(5*10**3+1)]
N, M = map(int, input().split())
ok = list(map(int, input().split()))
ok.sort()
a = [i for i in range(1, 10)]
b = [2, 5, 5, 4, 5, 6, 3, 7, 6]
data = {a[i]: b[i] for i in range(9)}
dp = [[0 for i in range(N+1)] for j in range(M+1)]


def find(X):
    return bisect.bisect_right(compare, X)


for i in range(M):
    for cnt in range(N+1):
        for num in ok[:i+1]:
            cost = data[num]
            if cnt > cost:
                K = dp[i+1][cnt-cost]
                if K > 0:
                    dp[i+1][cnt] = max(K + num*10 ** find(K), dp[i+1][cnt])
                    continue
                else:
                    dp[i+1][cnt] = max(K, dp[i+1][cnt])
                    continue
            elif cnt == cost:
                dp[i+1][cnt] = max(num, dp[i+1][cnt])
                continue
            else:
                dp[i+1][cnt] = max(dp[i][cnt], dp[i+1][cnt])
                continue
ans = dp[M][N]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# match matching
import bisect
import sys
input = sys.stdin.readline
compare = [10**i for i in range(5*10**3+1)]
N, M = map(int, input().split())
ok = list(map(int, input().split()))
ok.sort()
a = [i for i in range(1, 10)]
b = [2, 5, 5, 4, 5, 6, 3, 7, 6]
data = {a[i]: b[i] for i in range(9)}
dp = [[0 for i in range(N+1)] for j in range(M+1)]


def find(X):
    return bisect.bisect_right(compare, X)


for i in range(M):
    for cnt in range(N+1):
        for num in ok[:i+1]:
            cost = data[num]
            if cnt > cost:
                K = dp[i+1][cnt-cost]
                if K > 0:
                    dp[i+1][cnt] = max(K + num*10 ** find(K), dp[i+1][cnt])
                    continue
                else:
                    dp[i+1][cnt] = max(K, dp[i+1][cnt])
                    continue
            elif cnt == cost:
                dp[i+1][cnt] = max(num, dp[i+1][cnt])
                continue
            else:
                dp[i+1][cnt] = max(dp[i][cnt], dp[i+1][cnt])
                continue
ans = dp[M][N]
print(ans)