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:
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
# 一次元累積和
from itertools import accumulate
from bisect import bisect_left, bisect_right

import re
# import numpy as np
# from scipy.misc import comb

# 再帰がやばいとき
# import sys
# sys.setrecursionlimit(10**9)

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e50)
MOD = int(1e9)+7 # 10^9 + 7

# field[H][W]
def create_grid(H, W, value = 0):
    return [[ value for _ in range(W)] for _ in range(H)]

########

def main():
    H, M = l_inpl()
    A = l_inpl()
    d = {
        "1": 2,
        "2": 5,
        "3": 5,
        "4": 4,
        "5": 5,
        "6": 6,
        "7": 3,
        "8": 7,
        "9": 6
    }

    new_d = {}
    for Ai in A:
        new_d[Ai] = d[str(Ai)]

    dp = [-INF] * (H+1) # ちょうどi本のマッチ棒を使って，条件を満たす整数を作るときの最大桁数
    dp[0] = 0

    for i in range(1, H+1):
        tmp = []
        for k, v in new_d.items():
            if i-v < 0:
                tmp.append(-INF)
            else:
                tmp.append(dp[i-v]+1)
        dp[i] = max(tmp)

    s = sorted(new_d.items(), key=lambda x:-x[0])

    ans = ""
    remain = H

    while remain != 0:
        for k, v in s:
            if remain > v and dp[remain-v] == dp[remain] - 1: # 一桁だけ減少している
                ans += str(k)
                remain -= v
                break
    print(ans)
if __name__ == "__main__":
    main()

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

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

B = {}
for a in A:
    ind = seg[a]
    if not ind in B.keys():
        B[ind] = a
    else:
        if B[ind] < a:
            B[ind] = a

I = sorted(list(B.keys()))
#print(I)
Ap = []
def search(ind, remain, ret, l, maxl):
    if ind >= len(I):
        return False, ret, l
    #print(I[ind], remain, ret)
    a = I[ind]
    p = remain // a
    r = remain % a 
    if p == 0:
        return False, ret, l
    if r == 0:
        ret.append((a, p))
        l += p
        return True, ret, l
    for q in range(p-1, -1, -1):
        nowl = l
        r += a
        oldr = ret[:]
        ok, newr, newl = search(ind+1, r, oldr, nowl, maxl)
        if ok:
            newl += q
            newr.append((a, q))
            if ind == 0:
                if newl >= maxl:
                    maxl = newl
                    Ap.append(newr)
                continue
            return True, newr, newl
    if ind == 0:
        return False, Ap, l
    return False, ret, l

def main():

    only, Ls, l = search(0, N, [], 0, 0)
    #print(Ls)
    if only:
        Q = []
        for k, v in Ls:
            Q.extend([B[k]]*v)
        Q.sort(reverse=True)
        print(''.join([str(q) for q in Q]))
    else:
        anss = []
        for i, L in enumerate(Ls):
            P = []
            for k, v in L:
                P.append((B[k], v))
            P.sort(reverse=True)
            if i == 0:
                maxp = P[0][1]
            elif P[0][1] >= maxp:
                maxp = P[0][1]
            else:
                continue
            Q = ''
            for p, v in P:
                Q = Q + str(p)*v
            num = int(Q)
            anss.append(num)

        print(max(anss))

if __name__ == "__main__":
    main()

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

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

B = {}
for a in A:
    ind = seg[a]
    if not ind in B.keys():
        B[ind] = a
    else:
        if B[ind] < a:
            B[ind] = a

I = sorted(list(B.keys()))
#print(I)
Ap = []
def search(ind, remain, ret, l, maxl):
    if ind >= len(I):
        return False, ret, l
    #print(I[ind], remain, ret)
    a = I[ind]
    p = remain // a
    r = remain % a 
    if p == 0:
        return False, ret, l
    if r == 0:
        ret.append((a, p))
        l += p
        return True, ret, l
    for q in range(p-1, -1, -1):
        nowl = l
        r += a
        oldr = ret[:]
        ok, newr, newl = search(ind+1, r, oldr, nowl, maxl)
        if ok:
            newl += q
            newr.append((a, q))
            if ind == 0:
                if newl >= maxl:
                    maxl = newl
                    Ap.append(newr)
                continue
            return True, newr, newl
    if ind == 0:
        return False, Ap, l
    return False, ret, l

def main():

    only, Ls, l = search(0, N, [], 0, 0)
    #print(Ls)
    if only:
        Q = []
        for k, v in Ls:
            Q.extend([B[k]]*v)
        Q.sort(reverse=True)
        print(''.join([str(q) for q in Q]))
    else:
        anss = []
        for i, L in enumerate(Ls):
            P = []
            for k, v in L:
                P.append((B[k], v))
            P.sort(reverse=True)
            if i == 0:
                maxp = P[0][1]
            elif P[0][1] >= maxp:
                maxp = P[0][1]
            else:
                continue
            Q = []
            for p, v in P:
                Q.extend([p]*v)
            num = int(''.join([str(q) for q in Q]))
            anss.append(num)

        print(max(anss))

if __name__ == "__main__":
    main()

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

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

B = {}
for a in A:
    ind = seg[a]
    if not ind in B.keys():
        B[ind] = a
    else:
        if B[ind] < a:
            B[ind] = a

I = sorted(list(B.keys()))
#print(I)
Ap = []
def search(ind, remain, ret, l, maxl):
    if ind >= len(I):
        return False, ret, l
    #print(I[ind], remain, ret)
    a = I[ind]
    p = remain // a
    r = remain % a 
    if p == 0:
        return False, ret, l
    if r == 0:
        ret.append((a, p))
        l += p
        return True, ret, l
    for q in range(p-1, -1, -1):
        nowl = l
        r += a
        oldr = ret[:]
        ok, newr, newl = search(ind+1, r, oldr, nowl, maxl)
        if ok:
            newl += q
            newr.append((a, q))
            if ind == 0:
                if newl >= maxl:
                    maxl = newl
                    Ap.append(newr)
                continue
            return True, newr, newl
    if ind == 0:
        return False, Ap, l
    return False, ret, l

def main():

    only, Ls, l = search(0, N, [], 0, 0)
    #print(Ls)
    if only:
        Q = []
        for k, v in Ls:
            Q.extend([B[k]]*v)
        Q.sort(reverse=True)
        print(''.join([str(q) for q in Q]))
    else:
        anss = []
        for i, L in enumerate(Ls):
            P = []
            for k, v in L:
                P.append((B[k], v))
            P.sort(reverse=True)
            if i == 0:
                maxp = P[0][0]
            elif P[0][0] >= maxp:
                maxp = P[0][0]
            else:
                continue
            Q = []
            for p, v in P:
                Q.extend([p]*v)
            num = int(''.join([str(q) for q in Q]))
            anss.append(num)

        print(max(anss))

if __name__ == "__main__":
    main()

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

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

B = {}
for a in A:
    ind = seg[a]
    if not ind in B.keys():
        B[ind] = a
    else:
        if B[ind] < a:
            B[ind] = a

I = sorted(list(B.keys()))
#print(I)
Ap = []
def search(ind, remain, ret, l, maxl):
    if ind >= len(I):
        return False, ret, l
    #print(I[ind], remain, ret)
    a = I[ind]
    p = remain // a
    r = remain % a 
    if p == 0:
        return False, ret, l
    if r == 0:
        ret.append((a, p))
        l += p
        return True, ret, l
    for q in range(p-1, -1, -1):
        nowl = l
        r += a
        oldr = ret[:]
        ok, newr, newl = search(ind+1, r, oldr, nowl, maxl)
        if ok:
            newl += q
            newr.append((a, q))
            if ind == 0:
                if newl >= maxl:
                    maxl = newl
                    Ap.append(newr)
                continue
            return True, newr, newl
    if ind == 0:
        return False, Ap, l
    return False, ret, l

def main():

    only, Ls, l = search(0, N, [], 0, 0)
    #print(Ls)
    if only:
        Q = []
        for k, v in Ls:
            Q.extend([B[k]]*v)
        Q.sort(reverse=True)
        print(''.join([str(q) for q in Q]))
    else:
        anss = []
        for L in Ls:
            P = []
            for k, v in L:
                P.append((B[k], v))
            P.sort(reverse=True)
            Q = []
            for p, v in P:
                Q.extend([p]*v)
            num = int(''.join([str(q) for q in Q]))
            anss.append(num)

        print(max(anss))

if __name__ == "__main__":
    main()

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

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

B = {}
for a in A:
    ind = seg[a]
    if not ind in B.keys():
        B[ind] = a
    else:
        if B[ind] < a:
            B[ind] = a

I = sorted(list(B.keys()))
#print(I)
Ap = []
def search(ind, remain, ret, l, maxl):
    if ind >= len(I):
        return False, ret, l
    #print(I[ind], remain, ret)
    a = I[ind]
    p = remain // a
    r = remain % a 
    if p == 0:
        return False, ret, l
    if r == 0:
        ret.append((a, p))
        l += p
        return True, ret, l
    for q in range(p-1, -1, -1):
        nowl = l
        r += a
        oldr = ret[:]
        ok, newr, newl = search(ind+1, r, oldr, nowl, maxl)
        if ok:
            newl += q
            newr.append((a, q))
            if ind == 0:
                if newl >= maxl:
                    maxl = newl
                    Ap.append(newr)
                continue
            return True, newr, newl
    if ind == 0:
        return False, Ap, l
    return False, ret, l

def main():

    only, Ls, l = search(0, N, [], 0, 0)
    #print(Ls)
    if only:
        Q = []
        for k, v in Ls:
            Q.extend([B[k]]*v)
        Q.sort(reverse=True)
        print(''.join([str(q) for q in Q]))
    else:
        anss = []
        for L in Ls:
            Q = []
            for k, v in L:
                Q.extend([B[k]]*v)
            Q.sort(reverse=True)
            num = int(''.join([str(q) for q in Q]))
            anss.append(num)

        print(max(anss))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

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

B = {}
for a in A:
    ind = seg[a]
    if not ind in B.keys():
        B[ind] = a
    else:
        if B[ind] < a:
            B[ind] = a

I = sorted(list(B.keys()))
#print(I)
def search(ind, remain, ret):
    if ind >= len(I):
        return False, ret
    #print(I[ind], remain, ret)
    a = I[ind]
    p = remain // a
    r = remain % a 
    if p == 0:
        return False, ret
    if r == 0:
        ret.append((a, p))
        return True, ret
    for q in range(p-1, -1, -1):
        r += a
        oldr = ret[:]
        ok, newr = search(ind+1, r, oldr)
        if ok:
            newr.append((a, q))
            if ind == 0:
                Ap.append(newr)
                continue
            return True, newr
    if ind == 0:
        return False, Ap
    return False, ret

Ap = []
only, Ls = search(0, N, [])
#print(Ls)
if only:
    Q = []
    for k, v in Ls:
        Q.extend([B[k]]*v)
    Q.sort(reverse=True)
    print(''.join([str(q) for q in Q]))
else:
    anss = []
    for L in Ls:
        Q = []
        for k, v in L:
            Q.extend([B[k]]*v)
        Q.sort(reverse=True)
        num = int(''.join([str(q) for q in Q]))
        anss.append(num)

    print(max(anss))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

min_cost = min([cost[a] for a in A])
max_cost = max([cost[a] for a in A])

l = 1
k = 1
while min_cost*l<=N:
    dp_new = [-1]*(N+20)
    for i in range(min_cost*l, min(max_cost*l, N)+1):
        for a in A:
            v = dp[i-cost[a]]
            if v>=0:
                dp_new[i] = v + a*k
                break
    dp = dp_new
    if dp[N]>0 : r=dp[N]
    l+=1
    k*=10

print(r)

Submission status: Time Limit Exceeded

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

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

min_cost = min([cost[a] for a in A])
max_cost = max([cost[a] for a in A])
r=0

l = 1
while min_cost*l<=N:
    dp_new = [-1]*(N+20)
    for i in range(min_cost*l, min(max_cost*l, N)+1):
        v = [dp[i-cost[a]] + a*10**(l-1) for a in A if dp[i-cost[a]]>=0]
        if v: dp_new[i] = max(v)
    dp = dp_new
    if dp[N]>0 : r=dp[N]
    l+=1

print(r)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

def solve():
  N, M = LI()
  num_list = LI()
  mapping = [-1,2,5,5,4,5,6,3,7,6]

  a_list = [mapping[num] for num in num_list]
  
  rmap = {}
  for a, num in zip(a_list, num_list):
    if a not in rmap:
      rmap[a] = num
    else:
      if rmap[a] < num:
        rmap[a] = num

  # もっとも効率のいい数字を探す
  eff_num = -1
  eff_a = 10**9
  for a, num in zip(a_list, num_list):
    if a < eff_a or (a == eff_a and num >= eff_num):
      eff_a = a
      eff_num = num

  def search(r, cur, res):
    for a in list(set(a_list)):
      next_cur = [c for c in cur]
      next_cur.append(a)
      if a == r:
        res.append(next_cur)
        return res
      elif a > r:
        return res
      else:
        search(r-a, next_cur, res)
    return res

  k = N // eff_a # 効率のいい数字が作れる数の最大値
  rest =  N - k*eff_a
  if rest == 0:
    print(''.join([str(eff_num)]*k))
    return

  # 答えが出る+10ぐらいまで探索
  first_ans_i = None
  ans_str_cand = []
  for i in range(1, k):
    rest_a = rest + i* eff_a # あまりの数字
    candidates = search(rest_a, [], [])
    if len(candidates) == 0:
      continue
    ans_cand = None
    ans_cand_len = -1
    ans_cand_mx = -1
    for cand in candidates:
      cand_num = [rmap[c] for c in cand]
      cand_mx = max(cand_num)
      if (ans_cand_len < len(cand)) or (ans_cand_len == len(cand) and ans_cand_mx <= cand_mx):
          ans_cand = cand
          ans_cand_len = len(cand)
          ans_cand_mx = cand_mx
    eff = [eff_num]*(k-i)
    num_cand = [rmap[c] for c in ans_cand]
    num_cand.extend(eff)
    num_cand = sorted(num_cand, reverse=True)
    ans_str_cand.append(''.join([str(n) for n in num_cand]))
    if first_ans_i is None:
      first_ans_i = i
    if i >= first_ans_i + 12:
      break
  print(max(ans_str_cand))
solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

def solve():
  N, M = LI()
  num_list = LI()
  mapping = [-1,2,5,5,4,5,6,3,7,6]

  a_list = [mapping[num] for num in num_list]
  
  rmap = {}
  for a, num in zip(a_list, num_list):
    if a not in rmap:
      rmap[a] = num
    else:
      if rmap[a] < num:
        rmap[a] = num

  # もっとも効率のいい数字を探す
  eff_num = -1
  eff_a = 10**9
  for a, num in zip(a_list, num_list):
    if a < eff_a or (a == eff_a and num >= eff_num):
      eff_a = a
      eff_num = num

  def search(r, cur, res):
    for a in list(set(a_list)):
      next_cur = [c for c in cur]
      next_cur.append(a)
      if a == r:
        res.append(next_cur)
        return res
      elif a > r:
        return res
      else:
        search(r-a, next_cur, res)
    return res

  k = N // eff_a # 効率のいい数字が作れる数の最大値
  rest =  N - k*eff_a
  if rest == 0:
    print(''.join([str(eff_num)]*k))
    return

  # 答えが出る+10ぐらいまで探索
  first_ans_i = None
  ans_str_cand = []
  for i in range(1, k):
    rest_a = rest + i* eff_a # あまりの数字
    candidates = search(rest_a, [], [])
    if len(candidates) == 0:
      continue
    ans_cand = None
    ans_cand_len = -1
    ans_cand_mx = -1
    for cand in candidates:
      cand_num = [rmap[c] for c in cand]
      cand_mx = max(cand_num)
      if (ans_cand_len < len(cand)) or (ans_cand_len == len(cand) and ans_cand_mx <= cand_mx):
          ans_cand = cand
          ans_cand_len = len(cand)
          ans_cand_mx = cand_mx
    eff = [eff_num]*(k-i)
    num_cand = [rmap[c] for c in ans_cand]
    num_cand.extend(eff)
    num_cand = sorted(num_cand, reverse=True)
    ans_str_cand.append(''.join([str(n) for n in num_cand]))
    if first_ans_i is None:
      first_ans_i = i
    if i >= first_ans_i + 15:
      break
  print(max(ans_str_cand))
solve()

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse = True)
x = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [0 for i in range(N+1)]
for i in range(1, N+1):
    t = 0
    for a in A:
        if i >= x[a]:
            t = max(dp[i-x[a]] + 1, t)
    dp[i] = t

K = N
k = dp[N]
ans = ""
while k > 0:
    for a in A:
        xa = x[a]
        if K >= xa and k == dp[K-xa] + 1:
            if k == 1 and K != xa:
                continue
            ans += str(a)
            K -= xa
            k -= 1
            break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100001)
def input():
    return sys.stdin.readline()[:-1]

N, M = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse = True)
x = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [0 for i in range(N+1)]
for i in range(1, N+1):
    t = 0
    for a in A:
        if i >= x[a]:
            t = max(dp[i-x[a]] + 1, t)
    dp[i] = t
K = N
ans = ""
while dp[K] > 0:
    for a in A:
        xa = x[a]
        if K >= xa and dp[K] == dp[K-xa] + 1:
            if dp[K] == 1 and K != xa:
                continue
            ans += str(a)
            K -= xa
            break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse = True)
x = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [0 for i in range(N+1)]
for i in range(2, N+1):
    t = 0
    for a in A:
        if i >= x[a]:
            t = max(dp[i-x[a]] + 1, t)
    dp[i] = t
K = N
ans = ""
while K > 0:
    for a in A:
        xa = x[a]
        if K >= xa and dp[K] == dp[K-xa] + 1:
            if dp[K] == 1 and K != xa:
                continue
            ans += str(a)
            K -= xa
            break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse = True)
x = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [0 for i in range(N+1)]
for i in range(2, N+1):
    t = 0
    for a in A:
        if i >= x[a]:
            t = max(dp[i-x[a]] + 1, t)
    dp[i] = t
K = N
ans = ""
while K > 0:
    for a in A:
        if K >= x[a] and dp[K] == dp[K-x[a]] + 1:
            if dp[K] == 1 and K != x[a]:
                continue
            ans += str(a)
            K -= x[a]
            break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100001)
def input():
    return sys.stdin.readline()[:-1]

N, M = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse = True)
x = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [0 for i in range(N+1)]
for i in range(2, N+1):
    for a in A:
        if i >= x[a] and dp[i-x[a]] + 1 > dp[i]:
            dp[i] = dp[i-x[a]] + 1
K = N
ans = ''
while K > 0:
    for a in A:
        if K >= x[a] and dp[K] == dp[K-x[a]] + 1:
            if dp[K] == 1 and K != x[a]:
                continue
            ans += str(a)
            K -= x[a]
            break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
A=[int(i) for i in input().split()]
if 2 in A and 3 in A:
  A.remove(2)
if 3 in A and 5 in A:
  A.remove(3)
if 2 in A and 5 in A:
  A.remove(2)
if 6 in A and 9 in A:
  A.remove(6)
m=len(A)
D={}
D[1]=2
D[2]=5
D[3]=5
D[4]=4
D[5]=5
D[6]=6
D[7]=3
D[8]=7
D[9]=6
DP1,DP2=[-float("inf")]*(n+1),[[]]*(n+1)
DP1[0]=0
for i in range(n):
  for j in range(m):
    if D[A[j]]<=i+1 and DP1[i+1-D[A[j]]]!=-float("inf") and DP1[i+1-D[A[j]]]+1>=DP1[i+1]:
      DP1[i+1]=DP1[i+1-D[A[j]]]+1
      x,y=0,0
      X,Y=DP2[i+1],DP2[i+1-D[A[j]]]+[A[j]]
      X.sort(reverse=True)
      Y.sort(reverse=True)
      for xx in X:
        x=x*10+xx
      for yy in Y:
        y=y*10+yy
      if y>x:
        DP2[i+1]=DP2[i+1-D[A[j]]]+[A[j]]
ans=0
DP2[n].sort(reverse=True)
for i in DP2[n]:
  ans=ans*10+i
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
a=[int(i) for i in input().split()]
cost=[2,2,5,5,4,5,6,3,7,6]

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

for i in range(1,n+1):
    p=0
    for j in a:
        if i-cost[j]>=0 and dp[i-cost[j]]!="0":
            p=max(p,int(dp[i-cost[j]]+str(j)))
    dp[i]=str(p)

print(dp[n])

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
A=list((map(int,input().split())))
 
m=[[1,2],[2,5],[3,5],[4,4],[5,5],[6,6],[7,3],[8,7],[9,6]]
B=[]
    
for a in A:
    B.append(m[a-1])

if [5,5] in B:
    if [2,5] in B:
        B.remove([2,5])
    if [3,5] in B:    
        B.remove([3,5])

if [3,5] in B and [2,5] in B:
    B.remove([2,5])

if [7,3] in B:
    if [6,6] in B:
        B.remove([6,6])
    if [9,6] in B:
        B.remove([9,6])
    
if [9,6] in B and [6,6] in B:
    B.remove([6,6])

if [1,2] in B and [7,3] in B:
    if [2,5] in B:
        B.remove([2,5])
    if [3,5] in B:
        B.remove([3,5])
    if [5,5] in B:
        B.remove([5,5])
    if [8,7] in B:
        B.remove([8,7])

if [1,2] in B and ([2,5] in B or [3,5] in B or [5,5] in B) and [8,7] in B:
    B.remove([8,7])
    
if [4,4] in B and [7,3] in B and [8,7] in B:
    B.remove([8,7])
    
if [1,2] in B and [4,4] in B:
    B.remove([4,4])

maxlist=[""]*(N+1)
 
for i in range(N+1):
    if i!=0 and maxlist[i]=="":
        continue
    else:
        for b in B:
            if i+b[1]>N:
                continue
            ans=maxlist[i]+str(b[0])
            _max=maxlist[i+b[1]]
            if len(ans)<len(_max):
                continue
            elif len(ans)>len(_max):
                maxlist[i+b[1]] = ans
            else:
                for j in range(len(ans)):
                    if ans[j]<_max[j]:
                        break
                    if ans[j]>_max[j]:
                        maxlist[i+b[1]] = ans
                        break
 
print(maxlist[N])

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
A=list((map(int,input().split())))
 
m=[[1,2],[2,5],[3,5],[4,4],[5,5],[6,6],[7,3],[8,7],[9,6]]
B=[]
 
for a in A:
    B.append(m[a-1])
    
maxlist=[0]*(N+10)
 
for i in range(N+1):
    if i!=0 and maxlist[i]==0:
        continue
    else:
        for b in B:
            ans=int(str(maxlist[i])+str(b[0]))
            if ans > maxlist[i+b[1]]:
                maxlist[i+b[1]] = ans
 
print(maxlist[N])

Submission status: Time Limit Exceeded

Solution code:
match_num = [2, 5, 5, 4, 5, 6, 3, 7, 6]
number_list = list(range(1, 10))
n, m = map(int, input().split())
a = [int(i) for i in input().split()]
d_dict = {number_list[i]: match_num[i] for i in range(9) if number_list[i] in a}
d_min = min(d_dict.keys())
dp = [0] * (n+1)
for i in range(0, n - d_min + 1):
    for k, v in d_dict.items():
        if i + v <= n:
            aaa = list(str(dp[i]))
            aaa = [aa for aa in aaa if aa != "0"]
            calc = "".join(reversed(sorted(aaa + [str(k)])))
            if dp[i+v] == 0:
                if (dp[i] != 0):
                    dp[i+v] = int(calc)
                elif i == 0:
                    dp[i+v] = int(calc)
            else:
                if dp[i] != 0:
                    dp[i+v] = max(int(calc), dp[i+v])
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
match_num = [2, 5, 5, 4, 5, 6, 3, 7, 6]
number_list = list(range(1, 10))
n, m = map(int, input().split())
a = [int(i) for i in input().split()]
d_dict = {number_list[i]: match_num[i] for i in range(9) if number_list[i] in a}

dp = [0] * (n+1)
for i in range(0, n+1):
    for k, v in d_dict.items():
        if i + v <= n:
            aaa = list(str(dp[i]))
            aaa = [aa for aa in aaa if aa != "0"]
            calc = "".join(reversed(sorted(aaa + [str(k)])))
            if dp[i+v] == 0:
                if (dp[i] != 0):
                    dp[i+v] = int(calc)
                elif i == 0:
                    dp[i+v] = int(calc)
            else:
                if dp[i] != 0:
                    dp[i+v] = max(int(calc), dp[i+v])
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
l = [0,2,5,5,4,5,6,3,7,6]
n,m = list(map(int,input().split()))
a = list(map(int,input().split()))
dp = [['',0] for i in range(n+1)]
for i in range(n):
  for j in range(m):
    if dp[i][1] + l[a[j]] != i + l[a[j]] or i + l[a[j]] > n:
      pass
    elif len(dp[i][0]) + 1 > len(dp[i + l[a[j]]][0]):
      dp[i + l[a[j]]][0] = str(a[j]) + dp[i][0]
      dp[i + l[a[j]]][1] = dp[i][1] + l[a[j]]
    elif len(dp[i][0]) + 1 == len(dp[i + l[a[j]]][0]):
      if int(str(a[j]) + dp[i][0]) > int(dp[i + l[a[j]]][0]):
        dp[i + l[a[j]]][0] = str(a[j]) + dp[i][0]
        dp[i + l[a[j]]][1] = dp[i][1] + l[a[j]]
      else:
        pass
    else:
      pass
print(dp[n][0])

Submission status: Time Limit Exceeded

Solution code:
import math

if __name__ == "__main__":
    l = [0,2,5,5,4,5,6,3,7,6]
    n,m = list(map(int,input().split()))
    a = list(map(int,input().split()))
    dp = [[0,0,0] for i in range(n+1)]
    for i in range(n):
        for j in range(m):
            if dp[i][2] + l[a[j]] != i + l[a[j]] or i + l[a[j]] > n:
                pass
            elif dp[i][0] + a[j]*pow(10, dp[i][1]) >= dp[i + l[a[j]]][0]:
                dp[i + l[a[j]]][0] = dp[i][0] + a[j]*pow(10, dp[i][1])
                dp[i + l[a[j]]][1] = dp[i][1] + 1
                dp[i + l[a[j]]][2] = dp[i][2] + l[a[j]]
            else:
                pass
    print(dp[n][0])

Submission status: Time Limit Exceeded

Solution code:
## DP問題

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

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


ws = {} #マッチの数に対しての、作れる数字の最大値を算出
for a in As:
    w = match[a] #数aに使うマッチの数
    try: 
        ws[str(w)] = max(a,ws[str(w)])
    except:
        ws[str(w)] = a
ks = list(map(int,ws.keys()))
ns = list(ws.values())

dp = ["0" for _ in range(N+1)]
for i in range(1,min(ks)):#最小
    dp[i] = "-1"

for i in range(N+1):
    for a,k in zip(ns,ks):
        if i+k <= N:
            dp[i+k] = str(max(int(dp[i+k]),int(dp[i]+a)))
        else:
            continue
print(dp[N])

Submission status: Time Limit Exceeded

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

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


ws = {} #マッチの数に対しての、作れる数字の最大値を算出
for a in As:
    w = match[a] #数aに使うマッチの数
    try: 
        ws[str(w)] = max(a,ws[str(w)])
    except:
        ws[str(w)] = a
ks = list(map(int,ws.keys()))
ns = list(ws.values())

dp = ["0" for _ in range(N+1)]
for i in range(1,min(ks)):#最小
    dp[i] = "-1"

for i in range(N+1):
    for a,k in zip(ns,ks):
        if i+k <= N:
            dp[i+k] = str(max(int(dp[i+k]),int(dp[i]+a)))
        else:
            continue
print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
if __name__ == "__main__":

	l = [0,2,5,5,4,5,6,3,7,6]
	n,m = list(map(int,input().split()))
	a = list(map(int,input().split()))
	dp = [[0,0,0] for i in range(n+1)]
	for i in range(n):
		for j in range(m):
			if dp[i][2] + l[a[j]] != i + l[a[j]] or i + l[a[j]] > n:
				pass
			elif dp[i][0] + a[j]*(10**dp[i][1]) >= dp[i + l[a[j]]][0]:
				dp[i + l[a[j]]][0] = dp[i][0] + a[j]*(10**dp[i][1])
				dp[i + l[a[j]]][1] = dp[i][1] + 1
				dp[i + l[a[j]]][2] = dp[i][2] + l[a[j]]
			else:
				pass
	print(dp[n][0])