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:
N,M = map(int,input().split())
A = list(set(map(int,input().split())))
num = {}
num2 = [0,2,5,5,4,5,6,3,7,6]
for i in range(1,10):
    if i in A:
        num[i] = num2[i]
num3 = sorted(list(num.items()),key = lambda x:x[1])
A = [str(i[0]) for i in num3]
num = [i[1] for i in num3]
minum = num[0]
dp = [[0 for i in range(N+1)] for j in range(N//minum+1)]
dp[0][0] = '1'
for i in range(1,N//minum+1):
    for j in range(N+1):
        for k in range(len(num)):
            if j-num[k] >= 0 and dp[i-1][j-num[k]] != 0:
                if dp[i][j] != 0:
                    if dp[i-1][j] == 0:
                        dp[i][j] = str(max(int(dp[i][j]),int(''.join(sorted(list(dp[i-1][j-num[k]]+A[k]),reverse=True)))))
                    else:
                        dp[i][j] = str(max(int(dp[i][j]),int(dp[i-1][j]),int(''.join(sorted(list(dp[i-1][j-num[k]]+A[k]),reverse=True)))))
                else:
                    if dp[i-1][j] == 0:
                        dp[i][j] = ''.join(sorted(list(dp[i-1][j-num[k]]+A[k]),reverse=True))
                    else:
                        dp[i][j] = str(max(int(dp[i-1][j]),int(''.join(sorted(list(dp[i-1][j-num[k]]+A[k]),reverse=True)))))
            else:
                if dp[i-1][j] != 0:
                    if dp[i][j] != 0:
                        dp[i][j] = str(max(int(dp[i][j]),int(dp[i-1][j])))
                    else:
                        dp[i][j] = dp[i-1][j]
print(dp[-1][-1][:-1])

Submission status: Time Limit Exceeded

Solution code:
N,M=[int(x) for x in input().split()]
X=[0,2,5,5,4,5,6,3,7,6]
#    1,2,3,4,5,6,7,8,9

A=[int(x) for x in input().split()]



def po(num):
	ans=1
	if num!=0:
		while (num//10>=1):
			ans+=1
			num=num//10
	return ans-1

ANS=[0]
for i in range(1,N+1):
	ans=0
	for j in A:
		if i==X[j]:
			ans=max(j,ans)
		elif i>=X[j]:
			temp=ANS[i-X[j]]
			if temp!=0:
				power=po(temp)
				ans=max(ans,10*temp+j)
		
		#print(ans)
	ANS.append(ans)
print(ANS[-1])

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    match = [0,2,5,5,4,5,6,3,7,6]
    dp = [-1] * (N + 10)
    dp[0] = 0
    for i in range(N):
        if dp[i] != -1:
            for a in A:
                tmp = str(dp[i]) + str(a)
                dp[i+match[a]] = max(dp[i+match[a]], int(tmp))
        
    print(dp[N])


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect
N, M = map(int, input().split())
A = list(map(int, input().split()))
num = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
num = [(i, num[i]) for i in range(10) if i in A]
num.sort(key=lambda x: x[0], reverse=True)
num.sort(key=lambda x: x[1])
dp = ["0" for i in range(N+1)]


tmp = set()

for i in range(1, N+1):
    tmp2 = set()
    for n, k in num:
        if i - k in tmp:
            tmp2.add(dp[i-k]+str(n))
        else:
            if i == k:
                tmp2.add(str(n))

    for x in tmp2:
        x = list(x)
        x.sort(reverse=True)
        x = int("".join(x))

        dp[i] = str(max(int(dp[i]), x))
        tmp.add(i)


# print(dp)
ans = list(dp[N])
ans.sort(reverse=True)
print("".join(ans))

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
a = list(map(int,input().split()))
machnum = [i for i in range(10)]
a.sort(reverse=True)
machcou = [0,2,5,5,4,5,6,3,7,6]

dp = [0] * (n + 1)
for i in range(n):
    for j in range(len(a)):
        if i + 1 - machcou[a[j]] < 0:continue
        dp[i + 1] = max(dp[i + 1 - machcou[a[j]]] + 1,dp[i + 1])
#print(dp)
i = n
while i > 0:
    for j in range(len(a)):
        o = i - machcou[a[j]]
        if o < 0:continue
        if dp[i] - 1 == dp[o]:
            if dp[i] == 1 and o != 0:continue
            print(a[j],end="")
            i = o
            break
print()

Submission status: Time Limit Exceeded

Solution code:
n, m = list(map(int, input().split(' ')))
l = list(map(int, input().split(' ')))
d = {}  # key=match, val=num
d[2] = [1]
d[3] = [7]
d[4] = [4]
d[5] = [5, 3, 2]
d[6] = [9, 6]
d[7] = [8]
enable = [False] * 10
for a in l:
  enable[a] = True
# マッチをk(=2..7)本使う場合の一番大きい値を総当たり
memo = {}
def f(nokori, current):
  k = (nokori, current)
  if k in memo:
    return memo[k]
  if nokori <= 0:
    return current if nokori == 0 else -1
  temps = []
  for key, nums in list(d.items())[::-1]:
    for num in nums:
      if enable[num]:
        temps.append(f(nokori-key, current*10+num))
        break
  memo[k] = max(temps)
  return memo[k]

# 余裕があるうちは一番マッチの本数が少ないモノをヤケクソで詰めまくる
hoge = False
for key, nums in list(d.items()):
    # print(key, nums, type(nums))
    for num in nums:
      if enable[num]:
        hoge = True
        break
    if hoge:
      break
cs = []
while n > 50:
  n -= key
  cs.append(str(num))

# ヤケクソで詰めたやつと総当たりで調べたマックスを並び替えて辞書順で大きくする
num_ans = str(f(n, 0))
print(''.join(sorted(list(num_ans) + cs)[::-1]))

Submission status: Time Limit Exceeded

Solution code:
n, m = list(map(int, input().split(' ')))
l = list(map(int, input().split(' ')))
d = {}  # key=match, val=num
d[2] = [1]
d[3] = [7]
d[4] = [4]
d[5] = [5, 3, 2]
d[6] = [9, 6]
d[7] = [8]
enable = [False] * 10
for a in l:
  enable[a] = True
# マッチをk(=2..7)本使う場合の一番大きい値を総当たり
def f(nokori, current):
  k = (nokori, current)
  if nokori <= 0:
    return current if nokori == 0 else -1
  temps = []
  for key, nums in list(d.items())[::-1]:
    for num in nums:
      if enable[num]:
        temps.append(f(nokori-key, current*10+num))
        break
  return max(temps)

# 余裕があるうちは一番マッチの本数が少ないモノをヤケクソで詰めまくる
hoge = False
for key, nums in list(d.items()):
    # print(key, nums, type(nums))
    for num in nums:
      if enable[num]:
        hoge = True
        break
    if hoge:
      break
cs = []
while n > 50:
  n -= key
  cs.append(str(num))

# ヤケクソで詰めたやつと総当たりで調べたマックスを並び替えて辞書順で大きくする
num_ans = str(f(n, 0))
print(''.join(sorted(list(num_ans) + cs)[::-1]))

Submission status: Time Limit Exceeded

Solution code:
import collections
import sys

input = sys.stdin.readline

ri = lambda: int(input())
rs = lambda: input().rstrip()
ril = lambda: list(map(int, input().split()))
rsl = lambda: input().rstrip().split()
ris = lambda n: [ri() for _ in range(n)]
rss = lambda n: [rs() for _ in range(n)]
rils = lambda n: [ril() for _ in range(n)]
rsls = lambda n: [rsl() for _ in range(n)]

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

n, m = ril()
ls = ril()

d = collections.defaultdict(int)
for x in ls:
    d[d0[x]] = max(x, d[d0[x]])

dp = [0] * (n + 1)
for i in range(2, n + 1):
    for count, num in d.items():
        if count > i:
            continue
        k = dp[i - count]
        if count != i and k == 0:
            continue
        dp[i] = max(dp[i], 10 * k + num)
        if k != 0:
            dp[i] = max(dp[i], int(str(num) + str(k)))
print(dp[n])

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
N, M = map(int, input().split())
nums = list(map(int, input().split()))

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

dp = [''] * (N + 1)
for n in range(1, N + 1):
    for k in nums:
        d = 0
        cnt = n - matchNum[k]
        if cnt >= 0 and (dp[cnt] != '' or cnt == 0):
            oldVal = list(str(dp[cnt]))[:: -1]
            adder = bisect_left(oldVal, str(k))
            newVal = oldVal[:adder] + [str(k)] + oldVal[adder:]
            newVal = int(''.join(newVal[:: -1]))
            d = max(d, newVal)
        if d == 0:
            continue
        elif dp[n] == '':
            dp[n] = d
        else:
            dp[n] = max(dp[n], d)

print(dp[N])

Submission status: Time Limit Exceeded

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

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

dp = [''] * (N + 1)
for n in range(1, N + 1):
    for k in nums:
        d = 0
        cnt = n - matchNum[k]
        if cnt >= 0 and (dp[cnt] != '' or cnt == 0):
            newVal = int(''.join(sorted(list(str(dp[cnt])) + [str(k)], reverse=True)))
            d = max(d, newVal)
        if d == 0:
            continue
        elif dp[n] == '':
            dp[n] = d
        else:
            dp[n] = max(dp[n], d)

print(dp[N])

Submission status: Time Limit Exceeded

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

num = [0,2,5,5,4,5,6,3,7,6]
minnum = 10

# iけたをj本使ってできる最大値がdp[i][j]
dp = [-1000000000 for _ in range(20000)]
for i in range(1,10):
    if i in A:
        a = i
        dp[num[a]] = max(dp[num[a]],a)
        minnum = min(minnum,num[a])

for i in range(N//minnum+1):
    for j in range(N):
        for a in A:
            dp[j+num[a]] = max(dp[j+num[a]], 10 * dp[j] + a)
print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
input = stdin.readline
lmi = lambda: list(map(int, input().split()))
mi = lambda: map(int, input().split())
 
 
def cast(a, b):
    return int(str(a)+str(b))
 
 
n, m = mi()
match = [2,5,5,4,5,6,3,7,6]
arr = lmi()
dp = [-1 for i in range(n+1)]
dp[0] = 0
for i in range(n):
    if dp[i] != -1:
        for j in arr:
            if i+match[j-1] <= n:
                tmp = cast(j, dp[i])
                if tmp > dp[i+match[j-1]]:
                    dp[i+match[j-1]] = tmp
print(str(dp[-1])[:-1])

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
input = stdin.readline
lmi = lambda: list(map(int, input().split()))
mi = lambda: map(int, input().split())


def cast(a, b):
    return int(str(a)+str(b))


n, m = mi()
match = [2,5,5,4,5,6,3,7,6]
arr = lmi()
dp = [-1 for i in range(n+1)]
dp[0] = 0
for i in range(n):
    if dp[i] != -1:
        for j in arr:
            if i+match[j-1] <= n:
                tmp = cast(j, dp[i])
                if tmp > dp[i+match[j-1]]:
                    dp[i+match[j-1]] = tmp
print(str(dp[-1])[:-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(999999)
dicte = {1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6}
n, m = map(int, input().split())
arr = list(map(int, input().split()))
dp = {}
def cast(a, b):
    return int(str(a)+str(b))
def solve(curn):
    maxi = -1
    if curn in dicte.values():
        for j in arr:
            if curn - dicte[j] == 0:
                maxi = max(j, maxi)
        if maxi == -1:
            return None
        return maxi
    for j in arr:
        if curn - dicte[j] >= 0:
            z = solve(curn-dicte[j])
            if z == None:
                maxi = max(j, maxi)
            else:
                maxi = max(cast(j, solve(curn - dicte[j])), maxi)
    if maxi == -1:
        return None
    return maxi
print(solve(n))

Submission status: Time Limit Exceeded

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

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


for i in range(1,N+1):
    tmp = -1
    for a in A:
        if i-a>=0 and dp[i-d[a]] != -1:
            tmp = max(tmp,dp[i-d[a]]+1)
    dp[i] = tmp


A.sort(reverse=True)
ans = ''
while N>0:
    for a in A:
        if N-d[a]>=0 and dp[N-d[a]] == dp[N]-1:
            ans += str(a)
            N -= d[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()]

dic = {}
dic[1] = 2
dic[2] = 5
dic[3] = 5
dic[4] = 4
dic[5] = 5
dic[6] = 6
dic[7] = 3
dic[8] = 7
dic[9] = 6

ls = [-1]*8
dp = [-1]*(N+1)
dp[0] = 0
for i in a:
  j = dic[i]
  if ls[j]<i:
    ls[j] = i

tag = []
for i in range(len(ls)):
  if ls[i]!=-1:
    tag += [i]
for i in range(N+1):
  for j in tag:
    if i-j>-1 and dp[i-j]!=-1:
      keta = 0
      while 10**keta<=dp[i-j]:
        keta += 1
      s = ls[j]*(10**keta)+dp[i-j]
      if dp[i]<s:
        dp[i] = s

print(dp[N])

Submission status: Time Limit Exceeded

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

dic = {}
dic[1] = 2
dic[2] = 5
dic[3] = 5
dic[4] = 4
dic[5] = 5
dic[6] = 6
dic[7] = 3
dic[8] = 7
dic[9] = 6

ls = [-1]*8
dp = [-1]*(N+1)
dp[0] = ''
for i in a:
  j = dic[i]
  if ls[j]<i:
    ls[j] = i

tag = []
for i in range(len(ls)):
  if ls[i]!=-1:
    tag += [i]
for i in range(N+1):
  for j in tag:
    if i-j>-1 and dp[i-j]!=-1:
      s = str(ls[j])+str(dp[i-j])
      s = int(s)
      if i-j==0 and dp[i]<s:
        dp[i] = s
      elif dp[i]<s:
        dp[i] = s
m = 0

print(dp[N])

Submission status: Time Limit Exceeded

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

dic = {}
dic[1] = 2
dic[2] = 5
dic[3] = 5
dic[4] = 4
dic[5] = 5
dic[6] = 6
dic[7] = 3
dic[8] = 7
dic[9] = 6

ls = [-1]*8
dp = [-1]*(N+1)
dp[0] = 0
for i in a:
  j = dic[i]
  if ls[j]<i:
    ls[j] = i

tag = []
for i in range(len(ls)):
  if ls[i]!=-1:
    tag += [i]
for i in range(N+1):
  for j in tag:
    if i-j>-1 and dp[i-j]!=-1:
      keta = 0
      while 10**keta<=dp[i-j]:
        keta += 1
      s = ls[j]*(10**keta)+dp[i-j]
      if dp[i]<s:
        dp[i] = s

print(dp[N])

Submission status: Time Limit Exceeded

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

dic = {}
dic[1] = 2
dic[2] = 5
dic[3] = 5
dic[4] = 4
dic[5] = 5
dic[6] = 6
dic[7] = 3
dic[8] = 7
dic[9] = 6

ls = [-1]*8
dp = [-1]*(N+1)
dp[0] = ''
for i in a:
  j = dic[i]
  if ls[j]<i:
    ls[j] = i

tag = []
for i in range(len(ls)):
  if ls[i]!=-1:
    tag += [i]
for i in range(N+1):
  for j in tag:
    if i-j>-1 and dp[i-j]!=-1:
      s = str(ls[j])+str(dp[i-j])
      s = int(s)
      if i-j==0 and dp[i]<s:
        dp[i] = s
      elif dp[i]<s:
        dp[i] = s
m = 0

print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

from functools import lru_cache

N,M = II()
A = III()
num = [0]*10
num[1],num[2],num[3],num[4],num[5] = 2,5,5,4,5
num[6],num[7],num[8],num[9] = 6,3,7,6

x = [-1]*(N+1)
for n in range(1,N+1):
    val = []
    for i in range(M):
        if n-num[A[i]] < 0:
            continue
        elif n-num[A[i]] == 0:
            val.append(A[i])
        else:
            if x[n-num[A[i]]]>0:
                val.append(int(str(A[i]) + str(x[n-num[A[i]]])))
    if val:
        x[n] = max(val)
    else:
        x[n] = -1    

print(x[N])

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

from functools import lru_cache

N,M = II()
A = III()
num = [0]*10
num[1],num[2],num[3],num[4],num[5] = 2,5,5,4,5
num[6],num[7],num[8],num[9] = 6,3,7,6

@lru_cache(maxsize=None)
def rec(n):
    val = []
    for i in range(M):
        if n-num[A[i]] < 0:
            continue
        elif n-num[A[i]] == 0:
            val.append(A[i])
        else:
            if rec(n-num[A[i]])>0:
                val.append(int(str(A[i]) + str(rec(n-num[A[i]]))))
    if val:
        return max(val)
    else:
        return -1

print(rec(N))

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

from functools import lru_cache

N,M = II()
A = III()
num = [0]*10
num[1],num[2],num[3],num[4],num[5] = 2,5,5,4,5
num[6],num[7],num[8],num[9] = 6,3,7,6

@lru_cache(maxsize=10**5)
def rec(n):
    val = []
    for i in range(M):
        if n-num[A[i]] < 0:
            continue
        elif n-num[A[i]] == 0:
            val.append(A[i])
        else:
            if rec(n-num[A[i]])>0:
                val.append(int(str(A[i]) + str(rec(n-num[A[i]]))))
    if val:
        return max(val)
    else:
        return -1

print(rec(N))

Submission status: Time Limit Exceeded

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

#import fractions #fractions.gcd() python~3.4
sys.setrecursionlimit(1000000)

N, M = map(int,input().split())
A = list(map(int, input().split()))
INF = 1e+10
def f(x):
    if x == 1:
        return 2
    if x == 2:
        return 5
    if x == 3:
        return 5
    if x == 4:
        return 4
    if x == 5:
        return 5
    if x == 6:
        return 6
    if x == 7:
        return 3
    if x == 8:
        return 7 
    if x == 9:
        return 6

A.sort(reverse=True)

dp=[-INF]*(N+1)
dp[0] = 0
for i in range(1,N+1):
    for j in range(M):
        if i-f(A[j]) >= 0:
            dp[i] = max(dp[i],dp[i-f(A[j])]+1)
 
ans = ""
remain = dp[N]
match = N

while match > 0:
    for i in range(M):
        if match - f(A[i]) >0 and dp[match - f(A[i])] == remain - 1:
            ans += str(A[i])
            match -= f(A[i])
            remain -= 1
            
            break
            
print(ans)

Submission status: Time Limit Exceeded

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

#import fractions #fractions.gcd() python~3.4
sys.setrecursionlimit(1000000)

N, M = map(int,input().split())
A = list(map(int, input().split()))
INF = 1e+10
def f(x):
    if x == 1:
        return 2
    if x == 2:
        return 5
    if x == 3:
        return 5
    if x == 4:
        return 4
    if x == 5:
        return 5
    if x == 6:
        return 6
    if x == 7:
        return 3
    if x == 8:
        return 7 
    if x == 9:
        return 6

A.sort(reverse=True)

dp=[-INF]*(N+1)
dp[0] = 0
for i in range(1,N+1):
    for j in range(M):
        if i-f(A[j]) >= 0:
            dp[i] = max(dp[i],dp[i-f(A[j])]+1)
 
ans = ""
remain = dp[N]
match = N

while match > 0:
    for i in range(M):
        if match - f(A[i]) > 0 and dp[match - f(A[i])] == remain - 1:
            ans += str(A[i])
            match -= f(A[i])
            remain -= 1
            
            break
            
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
a = [int(i) for i in input().split()]
num_dict = {1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6}

if (6 in a) & (9 in a):
    a.remove(6)
    m -= 1
if 5 in a:
    if 3 in a:
        a.remove(3)
        m -= 1
    if 2 in a:
        a.remove(2)
        m -= 1
if 3 in a:
    if 2 in a:
        a.remove(2)
        m -= 1
        

dp = [["" for _ in range(m)] for _ in range(n+1)]
dp[0] = [0 for _ in range(m)]


a.sort()



def ret_max(x, y):
    return int("".join(sorted(list(str(x) + str(y)), reverse=True)))

for nn in range(n+1):
    for mm, num in enumerate(a):
        if mm+1 < m:
            if dp[nn][mm+1] != "":
                if dp[nn][mm] != "":
                    dp[nn][mm+1] = max(dp[nn][mm+1], dp[nn][mm])
            else:
                dp[nn][mm+1] = dp[nn][mm]
        if num_dict[num] + nn < n+1:
            if dp[num_dict[num] + nn][mm] != "":
                if dp[nn][mm] != "":
                    dp[num_dict[num] + nn][mm] = max(ret_max(dp[nn][mm], num), dp[num_dict[num] + nn][mm])
            else:
                dp[num_dict[num] + nn][mm] = ret_max(dp[nn][mm], num)
print(dp[-1][-1]//10)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
a = [int(i) for i in input().split()]
num_dict = {1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6}
dp = [["" for _ in range(m)] for _ in range(n+1)]
dp[0] = [0 for _ in range(m)]
a.sort()

def ret_max(x, y):
    return int("".join(sorted(list(str(x) + str(y)), reverse=True)))

for nn in range(n+1):
    for mm, num in enumerate(a):
        if mm+1 < m:
            if dp[nn][mm+1] != "":
                if dp[nn][mm] != "":
                    dp[nn][mm+1] = max(dp[nn][mm+1], dp[nn][mm])
            else:
                dp[nn][mm+1] = dp[nn][mm]
        if num_dict[num] + nn < n+1:
            if dp[num_dict[num] + nn][mm] != "":
                if dp[nn][mm] != "":
                    dp[num_dict[num] + nn][mm] = max(ret_max(dp[nn][mm], num), dp[num_dict[num] + nn][mm])
            else:
                dp[num_dict[num] + nn][mm] = ret_max(dp[nn][mm], num)
print(dp[-1][-1]//10)

Submission status: Time Limit Exceeded

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

dp = [-1 for i in range(N+10)]
l = [0,2,5,5,4,5,6,3,7,6]
dp[0] = 0
for i in range(N-1):
    for s in A:
        if dp[i] == -1 and i!=0:
            continue
        if dp[i + l[int(s)]] < int(str(dp[i])+s):
            dp[i + l[int(s)]] = int(str(dp[i])+s)
            

print(dp[N])

Submission status: Time Limit Exceeded

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

def cmp(a,b):
    if a == None:
        return True
    elif b == None:
        return False
    if len(a) > len(b):
        return False
    elif len(a) < len(b):
        return True
    else:
        if int(a) >= int(b):
            return False
        else:
            return True

dp = [-1] * (N+10)
l = [0,2,5,5,4,5,6,3,7,6]
dp[0] = 0
for i in range(N-1):
    for s in A:
        if dp[i] == -1 and i!=0:
            continue
        if dp[i + l[int(s)]] < int(str(dp[i])+s):
            dp[i + l[int(s)]] = int(str(dp[i])+s)
            

print(dp[N])

Submission status: Time Limit Exceeded

Solution code:


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

def cmp(a,b):
    if a == None:
        return True
    elif b == None:
        return False
    if len(a) > len(b):
        return False
    elif len(a) < len(b):
        return True
    else:
        if int(a) >= int(b):
            return False
        else:
            return True

dp = [None] * (N+10)
l = [0,2,5,5,4,5,6,3,7,6]
dp[0] = ""
for i in range(N-1):
    for s in A:
        if dp[i] == None and i!=0:
            continue
        if cmp(dp[i + l[int(s)]] , dp[i]+s):
            dp[i + l[int(s)]] = dp[i]+s
            

print(dp[N])

Submission status: Time Limit Exceeded

Solution code:


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

def cmp(a,b):
    if a == None:
        return True
    elif b == None:
        return False
    if len(a) > len(b):
        return False
    elif len(a) < len(b):
        return True
    else:
        if int(a) >= int(b):
            return False
        else:
            return True

dp = [None] * (N+10)
l = [0,2,5,5,4,5,6,3,7,6]
dp[0] = ""
for i in range(N+1):
    for s in A:
        if dp[i] == None and i!=0:
            continue
        ss = "".join([dp[i],s])
        if cmp(dp[i + l[int(s)]] , ss):
            dp[i + l[int(s)]] = ss
            

print(dp[N])

Submission status: Time Limit Exceeded

Solution code:


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

def cmp(a,b):
    if a == None:
        return True
    elif b == None:
        return False
    if len(a) > len(b):
        return False
    elif len(a) < len(b):
        return True
    else:
        if int(a) >= int(b):
            return False
        else:
            return True

dp = [None] * (N+10)
l = [0,2,5,5,4,5,6,3,7,6]
dp[0] = ""
for i in range(N+1):
    for s in A:
        if dp[i] == None and i!=0:
            continue
        ss = dp[i] + s
        if cmp(dp[i + l[int(s)]] , ss):
            dp[i + l[int(s)]] = ss
            

print(dp[N])

Submission status: Time Limit Exceeded

Solution code:


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

def cmp(a,b):
    if a == "" or b == "":
        if len(a) > len(b):
            return False
        elif len(a) < len(b):
            return True
    else:
        if int(a) >= int(b):
            return False
        else:
            return True

dp = [""] * (N+10)
l = [0,2,5,5,4,5,6,3,7,6]

for i in range(N+1):
    for s in A:
        if dp[i] == "" and i!=0:
            continue
        ss = dp[i] + s
        if cmp(dp[i + l[int(s)]] , ss):
            dp[i + l[int(s)]] = ss
            

print(dp[N])

Submission status: Time Limit Exceeded

Solution code:


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

def cmp(a,b):
    if len(a) > len(b):
        return False
    elif len(a) < len(b):
        return True
    else:
        if int(a) >= int(b):
            return False
        else:
            return True

dp = [""] * (N+100)
l = [0,2,5,5,4,5,6,3,7,6]

for i in range(N+1):
    for s in A:
        if dp[i] == "" and i!=0:
            continue
        ss = dp[i] + s
        if cmp(dp[i + l[int(s)]] , ss):
            dp[i + l[int(s)]] = ss
            

print(dp[N])

Submission status: Time Limit Exceeded

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

def cmp(a,b):
    if len(a) > len(b):
        return False
    elif len(a) < len(b):
        return True
    else:
        if int(a) >= int(b):
            return False
        else:
            return True

dp = [""] * (N+100)
l = [0,2,5,5,4,5,6,3,7,6]

for i in range(N+1):
    for s in A:
        if dp[i] == "" and i!=0:
            continue
        if cmp(dp[i + l[int(s)]] , dp[i] + s):
            dp[i + l[int(s)]] = dp[i] + s
            
print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
A = list(map(int, input().split()))
N = list(map(int, input().split()))
MAP =[-1*(10**2)]*10
numList=[0,2,5,5,4,5,6,3,7,6]
dp=[[-1*(10**2),""] for i in [1] * (A[0]+11)]
    
dp[10][0]=0
for i in range(1,A[0]+1):
    tmp = [0]*10
    maxk=0
    maxNum=-1000
    maxNums=-1000
    tmpNum=0
    for k in N:
        tmpNum=dp[10+i-numList[k]][0]+1
        if(tmpNum >= maxNum&tmpNum>=0):
            maxNum=tmpNum
            t = str(k)+str(dp[10+i-numList[k]][1])
            t = int(''.join(sorted(t, reverse=True)))
            if(t >= maxNums):
                maxNums = t
    dp[i+10][0] = maxNum
    dp[i+10][1] = maxNums
print(dp[(A[0]+10)][1])

"""
for i in range(dp[A[0]+10]):
    print("A")
"""

Submission status: Time Limit Exceeded

Solution code:
# ABC 118 D

def resolve():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort(reverse=True)

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

    dp = [0] * (N+1)
    for i in range(1, N+1):
        for a in A:
            if i - costs[a] < 0:
                continue
            dp[i] = max(dp[i-costs[a]] + 1, dp[i])

    ans = ""
    remain = dp[N]
    match = N

    minCosts = 10
    for a in A:
        minCosts = min(minCosts, costs[a])

    while match > 0:
        for a in A:
            if match - costs[a] < 0 or 1<= match - costs[a] < minCosts:
                continue

            if dp[match-costs[a]] == remain-1:
                ans += str(a)
                match -= costs[a]
                remain -= 1
                break

    print(ans)


if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
# ABC 118 D

def resolve():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort(reverse=True)

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

    dp = [0] * (N+1)
    for i in range(1, N+1):
        for a in A:
            if i - costs[a] < 0:
                continue
            dp[i] = max(dp[i-costs[a]] + 1, dp[i])

    ans = ""
    remain = dp[N]
    match = N

    while match > 0:
        for a in A:
            if match - costs[a] < 0 or match - costs[a] == 1:
                continue

            if dp[match-costs[a]] == remain-1:
                ans += str(a)
                match -= costs[a]
                remain -= 1
                break

    print(ans)


if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
# ABC 118 D

def resolve():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()
    A.reverse()

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

    dp = [0] * (N+1)
    for i in range(1, N+1):
        for a in A:
            if i - costs[a] < 0:
                continue
            dp[i] = max(dp[i-costs[a]] + 1, dp[i])

    ans = ""
    remain = dp[N]
    match = N

    while match > 0:
        for a in A:
            if match - costs[a] < 0:
                continue

            if match-costs[a] != 2 and match-costs[a] != 1 and dp[match-costs[a]] == remain-1:
                ans += str(a)
                match -= costs[a]
                remain -= 1
                break

    print(ans)


if __name__ == "__main__":
    resolve()

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 = [-1] * (n + 10)
dp[0] = 0

for i in range(n):
    for ai in a:
        dp[i + cost[ai]] = dp[i] + 1 if dp[i] > 0 else 1

ans = []
i = n
while dp[i] > 0:
    for ai in a:
        if dp[i - cost[ai]] == dp[i] - 1:
            ans.append(str(ai))
            i -= cost[ai]
            break

print(''.join(ans))