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

Solution code:
# match matching
import bisect
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)


def main():
    for i in range(M):
        for cnt in range(N+1):
            for j in range(M):
                num = ok[j]
                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])
                    else:
                        dp[i+1][cnt]=max(K, dp[i+1][cnt])
                elif cnt == cost:
                    dp[i+1][cnt]=max(num, dp[i+1][cnt])
                else:
                    dp[i+1][cnt]=max(dp[i][cnt], dp[i+1][cnt])
    ans=dp[M][N]
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# match matching
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)]

for i in range(M):
    for cnt in range(N+1):
        for j in range(M):
            num = ok[j]
            cost = data[num]
            if cnt > cost:
                P = len(str(dp[i+1][cnt-cost]))
                if dp[i + 1][cnt-cost] > 0:
                    dp[i+1][cnt] = max(dp[i+1][cnt-cost] +
                                       num*10 ** P, dp[i+1][cnt])
                else:
                    dp[i+1][cnt] = max(dp[i+1][cnt-cost], dp[i+1][cnt])
            elif cnt == cost:
                dp[i+1][cnt] = max(num, dp[i+1][cnt])
            elif cnt < cost:
                dp[i+1][cnt] = max(dp[i][cnt], dp[i+1][cnt])

ans = dp[M][N]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# D - Match Matching
import sys
sys.setrecursionlimit(10**7)
from collections import deque
from collections import defaultdict

MATCH = [(0, 6), (1, 2), (2, 5), (3, 5), (4, 4), (5, 5), (6, 6), (7, 3), (8, 7), (9, 6)]
N, M = map(int, input().split())
A = list(int(x) for x in input().split())
MA = []
for a in A:
    MA.append(MATCH[a])
MA.sort(key=lambda x: x[1])

def dfs(tmp, s):
    global ans
    if s == N:
        ans = max(ans, tmp)    
    for ma in MA:
        if s+ma[1] <= N:
            tmp = tmp*10 + ma[0]
            dfs(tmp, s + ma[1])
            tmp //= 10

tmp = 0
ans = 0
dfs(tmp, 0)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
N,M,*A = map(int, open(0).read().split())
ls = [0]*10
ls[1] = 2
ls[2] = 5
ls[3] = 5
ls[4] = 4
ls[5] = 5
ls[6] = 6
ls[7] = 3
ls[8] = 7
ls[9] = 6
dic = defaultdict(int)
for a in A:
  k = ls[a]
  dic[k] = max(dic[k],a)
dp = [-1]*(N+1)
for k in dic.keys():
  if k>N:
    continue
  dp[k] = dic[k]
for i in range(N+1):
  for k in dic.keys():
    if i-k>0 and dp[i-k]!=-1:
      s = str(dp[i-k])
      m = int(s+str(dic[k]))
      dp[i] = max(dp[i], m)
print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(4100000)

N, M = map(int,input().split())
A = list(map(int,input().split()))
A.sort(reverse = True)
d = [0,2,5,5,4,5,6,3,7,6]
S = set()
for a in A:
    S.add(d[a])

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

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

digit = dp[N]

def dfs(N, digit, ans):
    if digit == 0:
        if N == 0:
            return ans
        else:
            return 0
    for a in A:
        temp = dfs(N - d[a], digit - 1, ans * 10 + a)
        if temp:
            return temp

print(dfs(N, digit, 0))

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
B=[[] for i in range(0,10)]
for i in range(0,M):
    if 1 in A:
        B[2].append(1)
    if 2 in A:
        B[5].append(2)
    if 3 in A:
        B[5].append(3)
    if 4 in A:
        B[4].append(4)
    if 5 in A:
        B[5].append(5)
    if 6 in A:
        B[6].append(6)
    if 7 in A:
        B[3].append(7)
    if 8 in A:
        B[7].append(8)
    if 9 in A:
        B[6].append(9)


dp=['n' for i in range(0,max(10,N+1))]
for i in range(0,min(N+1,10)):
    if  i==1:
        if 1 in A:
            dp[2]='1'
    if i==2:
        if 2 in A:
            dp[5]='2'
    if i==3:
        if 3 in A:
            dp[5]='3'
    if i==4:
        if 4 in A:
            dp[4]='4'
    if i==5:
        if 5 in A:
            dp[5]='5'
    if i==6:
        if 6 in A:
            dp[6]='6'
    if i==7:
        if 7 in A:
            dp[3]='7'
    if i==8:
        if 8 in A:
            dp[7]='8'
    if i==9:
        if 9 in A:
            dp[6]='9'

if N>=4:
    if B[2]!=[]:
        dp[4]='11'
if N>=5:
    if B[3]!=[] and dp[2]!='n':
        dp[5]='71'
if N>=6:
    a='0'
    b='0'
    c='0'
    if B[2]!=[] and dp[4]!='n':
        a='1'+dp[4]
    if B[3]!=[]:
        b='77'
    if B[4]!=[] and dp[2]!='n':
        c='41'
    if dp[6]=='n':
        a=int(a)
        b=int(b)
        c=int(c)
        x=max(a,b,c)
        if x!=0:
            dp[6]=str(x)
    else:
        a=int(a)
        b=int(b)
        c=int(c)
        d=int(dp[6])
        dp[6]=str(max(a,b,c,d))

if N>=7:
    a='0'
    b='0'
    c='0'
    d='0'
    if B[2]!=[] and dp[5]!='n':
        a='1'+dp[5]
    if B[3]!=[] and dp[4]!='n':
        b='7'+dp[4]
    if B[4]!=[] and dp[3]!='n':
        c='47'
    if B[5]!=[] and dp[2]!='n':
        d=str(max(B[5]))+'1'
    if dp[7]=='n':
        a=int(a)
        b=int(b)
        c=int(c)
        d=int(d)
        x=max(a,b,c,d)
        if x!=0:
            dp[7]=str(x)
    else:
        a=int(a)
        b=int(b)
        c=int(c)
        d=int(d)
        e=int(dp[7])
        dp[7]=str(max(e,a,b,c,d))

for i in range(8,N+1):
    a='0'
    b='0'
    c='0'
    d='0'
    e='0'
    f='0'
    if B[2]!=[] and dp[i-2]!='n':
        a='1'+dp[i-2]
    if B[3]!=[] and dp[i-3]!='n':
        b='7'+dp[i-3]
    if B[4]!=[] and dp[i-4]!='n':
        c='4'+dp[i-4]
    if B[5]!=[] and dp[i-5]!='n':
        d=str(max(B[5]))+dp[i-5]
    if B[6]!=[] and dp[i-6]!='n':
        e=str(max(B[6]))+dp[i-6]
    if B[7]!=[] and dp[i-7]!='n':
        f='8'+dp[i-7]
    a=int(a)
    b=int(b)
    c=int(c)
    d=int(d)
    e=int(e)
    f=int(f)
    x=max(a,b,c,d,e,f)
    if x==0:
        dp[i]='n'
    else:
        dp[i]=str(x)
print(int(dp[N]))

Submission status: Time Limit Exceeded

Solution code:
import math
from collections import Counter
n, m = map(int, input().split())
a = list(map(int, input().split()))

req_m = [-1, 2, 5, 5, 4, 5, 6, 3, 7, 6]

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


for i in range(1, n+1):
    for j in a:
        if i >= req_m[j] and dp[i-req_m[j]] is not None:
            v = dp[i-req_m[j]] + Counter([j])
            if dp[i] is None:
                dp[i] = v
            else:
                if sum(dp[i].values()) < sum(v.values()):
                    dp[i] = v
                elif sum(dp[i].values()) == sum(v.values()):
                    if sorted(dp[i].elements(), reverse=True) < sorted(v.elements(), reverse=True):
                        dp[i] = v

print(''.join(map(str, sorted(dp[-1].elements(), reverse=True))))

Submission status: Time Limit Exceeded

Solution code:
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):
    if i == 11:
        pass
    for A in As:
        if i - match[int(A)] >= 0 and not dp[i - match[int(A)]] is None:
            if dp[i] is None:
                dp[i] = str(max(int(A + dp[i - match[int(A)]]), int(dp[i - match[int(A)]] + A)))
            else:
                dp[i] = str(max(int(dp[i]), int(dp[i - match[int(A)]] + A)))
                dp[i] = str(max(int(dp[i]), int(A + dp[i - match[int(A)]])))

print(dp[N])

Submission status: Time Limit Exceeded

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]

dp = [0]*(n+1)

for i in range(1,n+1):
    c = 0
    for j in range(m):
        if i >= l[a[j]]:
            c = max(c,dp[i-l[a[j]]]+1)
    dp[i] = c

ans = []
remain = dp[-1]
now = n
while now > 0 and remain > 0:
    for i in range(m):
        if now >= l[a[i]] and dp[now-l[a[i]]] == remain-1:
            if remain == 1:
                if now == l[a[i]]:
                    ans.append(a[i])
                    now = remain = 0
            else:
                if now >= l[a[i]] and dp[now-l[a[i]]] == remain-1:
                    ans.append(a[i])
                    remain -= 1
                    now -= l[a[i]]
                    break
            
print(*ans,sep="")

Submission status: Time Limit Exceeded

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]) >= 1 and len(dp[x-match]) == len(dp[x]) - 1:
                y = list(map(str, dp[x][::-1])); y.sort(reverse=True)
                z = [str(num)] + list(map(str, dp[x-match][::-1])); z.sort(reverse=True)
                y = int(''.join(y))
                z = int(''.join(z))
                if z > y:
                    dp[x] = dp[x-match] + [num]

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

Submission status: Time Limit Exceeded

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]
inf = float("INF")
dp = [-inf] * (n+10)
dp[0] = 0
for i in range(n):
  if dp[i] == -inf: continue
  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: Time Limit Exceeded

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

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
    print(''.join(map(str,ans)))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n,m=map(int,input().split())
    a=list(map(int,input().split()))
    a.sort(reverse=True)
    c=[0,2,5,5,4,5,6,3,7,6]
    cost=[0]*m
    for i,x in enumerate(a):
        cost[i]=c[x]
    dp=[0]*(n+10)
    ans=[]
    for i in range(n+1):
        for j in cost:
            dp[i+j]=max(dp[i]+1,dp[i+j])
    cnt=n
    while cnt>0:
        for i,j in enumerate(cost):
            if cnt>=j and dp[cnt-j]==dp[cnt]-1:
                ans.append(a[i])
                cnt-=j
                break
    print(''.join(map(str,ans)))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n,m=map(int,input().split())
    a=list(map(int,input().split()))
    a.sort(reverse=True)
    c=[0,2,5,5,4,5,6,3,7,6]
    cost=[0]*m
    for i,x in enumerate(a):
        cost[i]=c[x]
    dp=[0]*(n+10)
    ans=0
    for i in range(n+1):
        for j in cost:
            dp[i+j]=max(dp[i]+1,dp[i+j])
    cnt=n
    while cnt>0:
        for i,j in enumerate(cost):
            if dp[cnt]==1:
                if j==cnt:
                    ans*=10
                    ans+=a[i]
                    cnt-=j
                    break
            elif dp[cnt-j]==dp[cnt]-1:
                ans*=10
                ans+=a[i]
                cnt-=j
                break
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
from collections import deque

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

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

A = list(map(int, input().split()))
queue = deque()
queue.append((0, ""))

ans = 0
while queue:
    c_num, c_str = queue.popleft()
    if c_num == N:
        ans = max(ans, int(c_str))
        continue
    if c_num > N:
        continue
    for num in A:
        match_num = match_dict[num]
        new_str = c_str + str(num)
        queue.append((c_num + match_num, new_str))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,m = inpl()
a = sorted(inpl(), reverse = True)
b = [0,2,5,5,4,5,6,3,7,6]
dp = [[0]*(n+1) for _ in range(m+1)]

for i,x in enumerate(a):
    for c in range(b[x],n+1,b[x]):
        va = x * (c//b[x])
        # print(c,va)
        for j in range(n+1):
            if j != 0 and (j % c == 0 or (j >= c and dp[i+1][j-c] != 0)):
                dp[i+1][j] = max(dp[i][j],dp[i+1][j], dp[i+1][j-c]*10 + va)
                continue
            dp[i+1][j] = max(dp[i+1][j], dp[i][j])
print(dp[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,m = inpl()
a = sorted(inpl(), reverse = True)
b = [0,2,5,5,4,5,6,3,7,6]
dp = [['0']*(n+1) for _ in range(m+1)]

for i,x in enumerate(a):
    for c in range(b[x],n+1,b[x]):
        va = str(x) * (c//b[x])
        # print(c,va)
        for j in range(n+1):
            if j != 0 and (j % c == 0 or (j >= c and dp[i+1][j-c] != '0')):
                dp[i+1][j] = max(int(dp[i][j]),int(dp[i+1][j]), int(dp[i+1][j-c] + va))
                dp[i+1][j] = str(dp[i+1][j])
                continue
            dp[i+1][j] = max(int(dp[i+1][j]), int(dp[i][j]))
            dp[i+1][j] = str(dp[i+1][j])
print(dp[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))
count = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [0] * (N+1) # the largest number using i matches
for a in A:
    if count[a] <= N:
        dp[count[a]] = a
for i in range(N+1):
    if dp[i] == 0:
        continue
    for a in A:
        if i + count[a] <= N:
            dp[i+count[a]] = max(dp[i+count[a]], int(''.join(sorted(list(str(dp[i]) + str(a)), reverse=True))))
print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import copy

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])


class Num:
    def __init__(self):
        self.nums = defaultdict(int)

    def __lt__(self, rhs):
        nd1 = sum(self.nums.values())
        nd2 = sum(rhs.nums.values())
        if nd1 < nd2:
            return True
        elif nd1 > nd2:
            return False
        keys = set(self.nums.keys()) | set(rhs.nums.keys())
        for n in sorted(keys, reverse=True):
            if self.nums[n] < rhs.nums[n]:
                return True
            elif self.nums[n] > rhs.nums[n]:
                return False
        return False

    def __add__(self, rhs):
        obj = copy.deepcopy(self)
        obj.nums[rhs] += 1
        return obj

    def __repr__(self):
        if not self.nums:
            return 0
        s = []
        for k in sorted(self.nums.keys(), reverse=True):
            s.extend([str(k)] * self.nums[k])
        return ''.join(s)


best = [None for _ in range(N + 1)]
best[0] = Num()
for n in range(N + 1):
    for a in A:
        before = n - COST[a]
        if before < 0 or best[before] is None:
            continue
        val = best[before] + a
        if best[n] is None:
            best[n] = val
        else:
            best[n] = max(val, best[n])

print(best[N])

Submission status: Time Limit Exceeded

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

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

for i in range(n):
    if dp[i] == "":
        continue
    elif dp[i] == "0":
        for j in a:
            k = i + ma[j]
            if k <= n:
                if dp[k] == "":
                    dp[k] = "0"
                dp[k] = max(dp[k], str(j), key=int)
    else:
        for j in a:
            k = i + ma[j]
            if k <= n:
                if dp[k] == "":
                    dp[k] = "0"
                dp[k] = max(dp[k], dp[i] + str(j), key=int)
                dp[k] = max(dp[k], str(j)+dp[i], key=int)

print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

DEPMAX = 6

def foo(n,dep):
    if dep>DEPMAX or n<0:
        ret = "-1"
    elif n==0:
        ret = ""
    elif n%mn==0:
        ret = str(mni)*(n//mn)
    else:
        mxs = "-1"
        for x in a:
            v = foo(n-cs[x],dep+1)
            if v=="-1":
                continue
            vv = v+str(x)
            if int(vv)>int(mxs):
                mxs = vv
            vv = str(x)+v
            if int(vv)>int(mxs):
                mxs = vv
        ret = mxs
    #ddprint(f"foo n {n} k {k} ret {ret}")
    return ret

n,m = inm()
a = inl()
a.sort()
cs = [0,2,5,5,4,5,6,3,7,6]
mn = min([cs[x] for x in a])
for i in range(m-1,-1,-1):
    if cs[a[i]]==mn:
        mni = a[i]
        break
#k = (n+mn-1)//mn
#k = (n)//mn
#ddprint(f"mn {mn} mni {mni}")
#ddprint(a)
print(foo(n,0))

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()))
a.sort()
a.reverse()
lis = [2,5,5,4,5,6,3,7,6]
mat=[]
for num in a:
    mat.append([num,lis[num-1]])

def new_val(num1,num2): # 123 , 4 -> 4123
    if num1<0:
        return -(10**10)
    if num1==0:
        return num2

    return int(str(num1)+str(num2))

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

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

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
a.reverse()
lis = [2,5,5,4,5,6,3,7,6]
mat=[]
for num in a:
    mat.append([num,lis[num-1]])

def new_val(num1,num2): # 123 , 4 -> 4123
    if num1<0:
        return -(10**10)
    if num1==0:
        return num2
    return int(str(num1)+str(num2))

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

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

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int, input().split())
a = list(map(int, input().split()))
lis = [2,5,5,4,5,6,3,7,6]
mat=[]
for num in a:
    mat.append([num,lis[num-1]])

def new_val(num1,num2): # 123 , 4 -> 4123
    if num1<0:
        return -(10**10)
    if num1==0:
        return num2
    return max(int(str(num2)+str(num1)),int(str(num1)+str(num2)))

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

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

Submission status: Time Limit Exceeded

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#118_D
ch={1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}

def max_num(x,y):#yは一桁
    if x==-1:
        return -1
    if x==0:
        return y
    l=list(str(x))+[str(y)]
    l.sort(reverse=True)
    return int(''.join(l))

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

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

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
B=[[] for i in range(0,10)]
for i in range(0,M):
    if 1 in A:
        B[2].append(1)
    if 2 in A:
        B[5].append(2)
    if 3 in A:
        B[5].append(3)
    if 4 in A:
        B[4].append(4)
    if 5 in A:
        B[5].append(5)
    if 6 in A:
        B[6].append(6)
    if 7 in A:
        B[3].append(7)
    if 8 in A:
        B[7].append(8)
    if 9 in A:
        B[6].append(9)


dp=['n' for i in range(0,max(10,N+1))]
for i in range(0,min(N+1,10)):
    if  i==1:
        if 1 in A:
            dp[2]='1'
    if i==2:
        if 2 in A:
            dp[5]='2'
    if i==3:
        if 3 in A:
            dp[5]='3'
    if i==4:
        if 4 in A:
            dp[4]='4'
    if i==5:
        if 5 in A:
            dp[5]='5'
    if i==6:
        if 6 in A:
            dp[6]='6'
    if i==7:
        if 7 in A:
            dp[3]='7'
    if i==8:
        if 8 in A:
            dp[7]='8'
    if i==9:
        if 9 in A:
            dp[6]='9'

for i in range(4,N+1):
    if i==4:
        if B[2]!=[]:
            dp[4]='11'
    if i==5:
        if B[3]!=[] and dp[2]!='n':
            dp[5]='71'
    if i==6:
        a='0'
        b='0'
        c='0'
        if B[2]!=[] and dp[4]!='n':
            a='1'+dp[4]
        if B[3]!=[]:
            b='77'
        if B[4]!=[] and dp[2]!='n':
            c='41'
        if dp[6]=='n':
            a=int(a)
            b=int(b)
            c=int(c)
            x=max(a,b,c)
            if x!=0:
                dp[6]=str(x)
        else:
            a=int(a)
            b=int(b)
            c=int(c)
            d=int(dp[6])
            dp[6]=str(max(a,b,c,d))
    if i==7:
        a='0'
        b='0'
        c='0'
        d='0'
        if B[2]!=[] and dp[5]!='n':
            a='1'+dp[5]
        if B[3]!=[] and dp[4]!='n':
            b='7'+dp[4]
        if B[4]!=[] and dp[3]!='n':
            c='47'
        if B[5]!=[] and dp[2]!='n':
            d=str(max(B[5]))+'1'
        if dp[7]=='n':
            a=int(a)
            b=int(b)
            c=int(c)
            d=int(d)
            x=max(a,b,c,d)
            if x!=0:
                dp[7]=str(x)
        else:
            a=int(a)
            b=int(b)
            c=int(c)
            d=int(d)
            e=int(dp[7])
            dp[7]=str(max(e,a,b,c,d))
    if i>7:
        a='0'
        b='0'
        c='0'
        d='0'
        e='0'
        f='0'
        if B[2]!=[] and dp[i-2]!='n':
            a='1'+dp[i-2]
        if B[3]!=[] and dp[i-3]!='n':
            b='7'+dp[i-3]
        if B[4]!=[] and dp[i-4]!='n':
            c='4'+dp[i-4]
        if B[5]!=[] and dp[i-5]!='n':
            d=str(max(B[5]))+dp[i-5]
        if B[6]!=[] and dp[i-6]!='n':
            e=str(max(B[6]))+dp[i-6]
        if B[7]!=[] and dp[i-7]!='n':
            f='8'+dp[i-7]
        a=int(a)
        b=int(b)
        c=int(c)
        d=int(d)
        e=int(e)
        f=int(f)
        x=max(a,b,c,d,e,f)
        if x==0:
            dp[i]='n'
        else:
            dp[i]=str(x)
print(int(dp[N]))

Submission status: Time Limit Exceeded

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

d = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
c = [(i, d[i]) for i in A]
minpos = min(c, key=lambda x:x[1])[1]

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

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

print(dp[N])

Submission status: Time Limit Exceeded

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

dp = [""] * (N+1)
d = {
    1: 2,
    2: 5,
    3: 5,
    4: 4,
    5: 5,
    6: 6,
    7: 3,
    8: 7,
    9: 6
}

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

dp[0] = ""
dp[1] = ""

for i in range(minpos, N+1):
    for n, cost in c:
        if i-cost<0: continue
        if 0<i-cost<minpos: continue
        a = int(dp[i]) if dp[i] else 0
        b = int(str(n) + dp[i-cost])
        if a<b:
            dp[i] = str(n) + dp[i-cost]

print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
import sys
import copy

sys.setrecursionlimit(10**6)

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

def a_le_b(a, b):
    la, lb = len(a), len(b)
    if la == lb:
        for i in range(la):
            if a[i] < b[i]:
                return True
            elif a[i] > b[i]:
                return False
        return True
    return la < lb

N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)
for i in range(len(A)-1, 0, -1):
    for j in range(i-1, -1, -1):
        if m[A[i]] == m[A[j]]:
            del A[i]
            break
# print(A)
dp = [[] for _ in range(N+1)]

for i in range(N):
    if len(dp[i])==0 and i != 0: continue
    x = copy.copy(dp[i]) + [0]
    # print(x)
    for j in range(len(A)):
        ind = i + m[A[j]]
        if ind <= N:
            x[-1] = A[j]
            if a_le_b(dp[ind], x):
                dp[ind] = copy.copy(x)
# print(dp)
print(''.join(map(str, dp[-1])))

Submission status: Time Limit Exceeded

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

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

memo = [None] * (N + 1)
memo[0] = ''
# for Ai in A:
#     memo[tab[Ai]] = str(Ai)

ERROR_CODE = 'a'

import sys
sys.setrecursionlimit(10000)

def dp(X):
    global ERROR_CODE
    # print("#", X)
    if X < 0: return ERROR_CODE
    if memo[X] != None: return memo[X]
    len_max = 0
    rets = []
    for Ai in A:
        ret_tmp = str(Ai) + dp(X - tab[Ai])
        if ret_tmp[-1] == ERROR_CODE: continue
        ret_tmp = ''.join(sorted(list(ret_tmp), key=lambda x: -int(x)))
        rets.append(ret_tmp)
        len_max = max(len_max, len(ret_tmp))
    for i in range(len(rets)):
        rets[i] = '0' * (len_max - len(rets[i])) + rets[i]
    #
    rets.sort()
    # print("#", rets)
    if len(rets) == 0:
        ret = ERROR_CODE
    else:
        ret = rets[-1].replace('0', '')
    #
    memo[X] = ret
    return ret

ans = dp(N)
print(ans)
# print("#", memo)