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: Accepted

Solution code:
N, M = [int(v) for v in input().split()]
a = [int(v) for v in input().split()]
a.sort(reverse=True)

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

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

for i in range(1, N+1):
    max_digit = -1
    for v in a:
        if num_dict[v] > i:
            continue
        max_digit = max(max_digit, dp[i - num_dict[v]] + 1)
    if max_digit > 0:
        dp[i] = max_digit

ans = ''
ret = N
while ret > 0:
    for v in a:
        if num_dict[v] > ret:
            continue
        if dp[ret - num_dict[v]] == dp[ret] - 1:
            ans += str(v)
            ret -= num_dict[v]
            break

print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
A = list(reversed(sorted(map(int, input().split()))))
c = [2,5,5,4,5,6,3,7,6]
x = [0]*(N+1)
for i in range(1,N+1):
    x[i] = max([-1]+[x[i-c[a-1]]+1 for a in A if i >= c[a-1]])
n = N
for _ in range(N):
    for a in A:
        if n >= c[a-1] and x[n-c[a-1]] == x[n]-1:
            print(a, end="")
            n -= c[a-1]
            break
print("")

Submission status: Accepted

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]

dp = [0]*(N+1)

for i in range(N+1):
	for j in range(len(A)):
		if i-num[A[j]]<0:
			continue
		if i-num[A[j]]>0 and dp[i-num[A[j]]]==0:
			continue
		dp[i] = max(dp[i],dp[i-num[A[j]]]+1)

A.sort()
A.reverse()
ans = ""
now = N
while now!=0:
	for i in range(len(A)):
		if now-num[A[i]]<0:
			continue
		if dp[now-num[A[i]]]==dp[now]-1:
			if dp[now-num[A[i]]]==0 and now-num[A[i]]!=0:
				continue
			ans = ans+str(A[i])
			now -= num[A[i]]
			break
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
A=list(map(int,input().split()))
D={1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}
C=[]
for i in range(1,10):
    if i in A:
        C.append(D[i])
DP=[-float('inf')]*(n+1)
DP[0]=0
for i in range(1,n+1):
    for j in C:
        if i>=j:
            tmp=DP[i-j]+1
            DP[i]=max(DP[i],tmp)
A=sorted(A,reverse=True)
ans=''
while n>0:
    for i in A:
        if n-D[i]<0:
            continue
        if DP[n-D[i]]==DP[n]-1:
            ans+=str(i)
            n-=D[i]
            break
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
A=list(map(int,input().split()))
D={1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}
C=[]
for i in range(1,10):
    if i in A:
        C.append(D[i])
DP=[-float('inf')]*(n+1)
DP[0]=0
for i in range(1,n+1):
    for j in C:
        if i>=j:
            tmp=DP[i-j]+1
            DP[i]=max(DP[i],tmp)
A=sorted(A,reverse=True)
ans=''
while DP[n]:
    for i in A:
        if n-D[i]<0:
            continue
        if DP[n-D[i]]==DP[n]-1:
            ans+=str(i)
            n-=D[i]
            break
print(ans)

Submission status: Accepted

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

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

dp = [-float("inf")] * (N + 1)
b_list = []
for a in a_list:
    need = items[a]
    if need <= N:
        dp[need] = 1
        b_list.append(a)

M = len(b_list)
dp[0] = 0
for i in range(N + 1):
    for b in b_list:
        if i - items[b] >= 0:
            if dp[i - items[b]] != -float("inf"):
                dp[i] = max(dp[i], dp[i - items[b]] + 1)

b_list.sort(reverse=True)
ans = ""

for i in range(dp[N]):
    for b in b_list:
        if dp[N - items[b]] == dp[N] - 1:
            ans += str(b)
            N -= items[b]
            break
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
use = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [[0] * 10 for i in range(n+1)]
for i in range(1,n+1):
    for j in a:
        if i - use[j] >= 0:
            if dp[i-use[j]] == [0] * 10 and i - use[j] != 0: # マッチの数が合わない場合
                continue #何もしない
            else:
                if sum(dp[i-use[j]])+1 >= sum(dp[i]):
                    copy = dp[i-use[j]][:]
                    copy[j] += 1
                    dp[i] = copy
ans = ""
for i in range(9,0,-1):
    ans += (str(i) * dp[n][i])
print(ans)

Submission status: Accepted

Solution code:
c=[0,2,5,5,4,5,6,3,7,6]
I=lambda:map(int,input().split())
N,M=I()
A=sorted(I())[::-1]
d=[0]
for i in range(N):l=[d[i+1-c[a]]for a in A if i+2>c[a]];d+=[-1 if len(l)==0 else max(l)+1]
S=''
T=0
for i in range(d[N]):
 for a in A:
  b=c[a]
  if N-T-b>=0 and d[N-T-b]==d[N]-1-i:S+=str(a);T+=b;break
print(S)

Submission status: Accepted

Solution code:
#解説より
cost=[0,2,5,5,4,5,6,3,7,6]
N,M=map(int,input().split())
A=sorted(map(int,input().split()))[::-1]
dp=[0]
for i in range(1,N+1):
    l=[dp[i-cost[a]]for a in A if i>=cost[a]]
    if len(l)==0:dp+=[-1]
    else:dp+=[max(l)+1]
S=''
Sum=0
for i in range(dp[N]):
    for a in A:
        if N-Sum-cost[a]>=0 and dp[N-Sum-cost[a]]==dp[N]-1-i:
            S+=str(a)
            Sum+=cost[a]
            break
print(S)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
A=list(map(int,input().split()))
if(1 in A):
    if(4 in A):
        A.remove(4)
    if(9 in A):
        A.remove(9)
    if(6 in A):
        A.remove(6)
if(5 in A):
    if(3 in A):
        A.remove(3)
    if(2 in A):
        A.remove(2)
if(3 in A):
    if(2 in A):
        A.remove(2)
if(9 in A):
    if(6 in A):
        A.remove(6)
if(7 in A):
    if(9 in A):
        A.remove(9)
    if(6 in A):
        A.remove(6)
num=[0,2,5,5,4,5,6,3,7,6]
dp=[0]
keta=[0]
tmp=0
tmp1=0
tmp_keta=-1
tmp1_keta=-1
for i in range(1,N+1):
    tmp=-1
    tmp_keta=-1
    for j in A:
        tmp1=-1
        tmp1_keta=-1
        if(i-num[j]>=0):
            if(dp[i-num[j]]>0):
                tmp1=dp[i-num[j]]+j*(10**keta[i-num[j]])
                tmp1_keta=keta[i-num[j]]+1
            elif(dp[i-num[j]]==0):
                tmp1=j
                tmp1_keta=1

            if(tmp1>tmp):
                tmp=tmp1
                tmp_keta=tmp1_keta
                
    dp.append(tmp)
    keta.append(tmp_keta)
print(dp[N])

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
Costs = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
A = sorted(list(map(int, input().split())), reverse=True)  # 大きい順に


# dp[i]:= マッチ棒をn本使って得られる最大桁数(-infはマッチ棒が使いきれないことを表す)
dp = [-float('inf')] * (N + 1)
dp[0] = 0

# 個数制限なしナップサックと同じ要領
for a in A:
    cost = Costs[a]
    for j in range(N + 1):
        if cost > j:
            continue
        dp[j] = max(dp[j], dp[j - cost] + 1)


# dpの復元
ans = ""
marker = N  # いま何本残っているか
while dp[marker]:  # 0本になるまで回す
    for a in A:  # 大きな数字から見ていく
        cost = Costs[a]
        
        # Python特有のバグ消し
        if marker - cost < 0:
            continue
        
        # marker本ある状態から、マッチ棒をcost本使う数字aを使わなければ、marker本使った場合の桁数-1になる場合、
        # 数字aを使ったことがわかる
        if dp[marker - cost] == dp[marker] - 1:
            ans += str(a)
            marker = marker - cost
            break

print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys

# import bisect
# import math
# import itertools

# import numpy as np


"""Template"""


class IP:
    """
    入力を取得するクラス
    """

    def __init__(self):
        self.input = sys.stdin.readline

    def I(self):
        """
        1文字の取得に使います
        :return: int
        """
        return int(self.input())

    def S(self):
        """
        1文字の取得(str
        :return: str
        """
        return self.input()

    def IL(self):
        """
        1行を空白で区切りリストにします(int
        :return: リスト
        """
        return list(map(int, self.input().split()))

    def SL(self):
        """
        1行の文字列を空白区切りでリストにします
        :return: リスト
        """
        return list(map(str, self.input().split()))

    def ILS(self, n):
        """
        1列丸々取得します(int
        :param n: 行数
        :return: リスト
        """
        return [int(self.input()) for _ in range(n)]

    def SLS(self, n):
        """
        1列丸々取得します（str
        :param n: 行数
        :return: リスト
        """
        return [self.input() for _ in range(n)]

    def SILS(self, n):
        """
        Some Int LineS
        横に複数、縦にも複数
        :param n: 行数
        :return: list
        """
        return [self.IL() for _ in range(n)]

    def SSLS(self, n):
        """
        Some String LineS
        :param n: 行数
        :return: list
        """
        return [self.SL() for _ in range(n)]


class Idea:
    def __init__(self):
        pass

    def HF(self, p):
        """
        Half enumeration
        半分全列挙です
        pの要素の和の組み合わせを作ります。
        ソート、重複削除行います
        :param p: list : 元となるリスト
        :return: list : 組み合わせられた和のリスト
        """
        return sorted(set(p[i] + p[j] for i in range(len(p)) for j in range(i, len(p))))

    def Bfs2(self, a):
        """
        bit_full_search2
        bit全探索の改良版
        全探索させたら2進数のリストと10進数のリストを返す
        :return: list２つ : １個目 2進数(16桁)  2個目 10進数
        """
        # 参考
        # https://blog.rossywhite.com/2018/08/06/bit-search/
        # https://atcoder.jp/contests/abc105/submissions/4088632
        value = []
        for i in range(1 << len(a)):
            output = []

            for j in range(len(a)):
                if self.bit_o(i, j):
                    """右からj+1番目のiが1かどうか判定"""
                    # output.append(a[j])
                    output.append(a[j])
            value.append([format(i, 'b').zfill(16), sum(output)])

        value.sort(key=lambda x: x[1])
        bin = [value[k][0] for k in range(len(value))]
        val = [value[k][1] for k in range(len(value))]
        return bin, val

    def S(self, s, r=0, m=-1):
        """
        ソート関係行います。色々な設定あります。
        :param s: 元となるリスト
        :param r: reversするかどうか 0=False 1=True
        :param m: （2次元配列）何番目のインデックスのソートなのか
        :return: None
        """
        r = bool(r)
        if m == -1:
            s.sort(reverse=r)
        else:
            s.sort(reverse=r, key=lambda x: x[m])

    def bit_n(self, a, b):
        """
        bit探索で使います。0以上のときにTrue出します
        自然数だからn
        :param a: int
        :param b: int
        :return: bool
        """
        return bool((a >> b & 1) > 0)

    def bit_o(self, a, b):
        """
        bit探索で使います。1のときにTrue出すよ
        oneで1
        :param a: int
        :param b: int
        :return: bool
        """
        return bool(((a >> b) & 1) == 1)

    def ceil(self, x, y):
        """
        Round up
        小数点切り上げ割り算
        :param x: int
        :param y: int
        :return: int
        """
        return -(-x // y)

    def ave(self, a):
        """
        平均を求めます
        :param a: list
        :return: int
        """
        return sum(a) / len(a)

    def gcd(self, x, y):
        if y == 0:
            return x
        else:
            return self.gcd(y, x % y)


"""ここからメインコード"""


def main():
    # 1文字に省略
    r, e = range, enumerate
    ip = IP()
    id = Idea()

    """この下から書いてね"""
    n, m = ip.IL()
    A = ip.IL()
    K = (0, 2, 5, 5, 4, 5, 6, 3, 7, 6)

    id.S(A)
    DP = [0] * (n + 1)

    for i in range(n):
        for a in A:
            if i + 1 - K[a] < 0:
                continue
            DP[i + 1] = max(DP[i + 1], DP[i + 1 - K[a]] * 10 + a)
        if DP[i + 1] == 0:
            DP[i + 1] = -1

    print(DP[n])


main()

Submission status: Accepted

Solution code:
import sys
N,M=map(int,input().split())
A=list(map(int,input().split()))
n=[0,2,5,5,4,5,6,3,7,6]
num=[0]*8
for a in A:
    num[n[a]]=max(num[n[a]],a)
nums=[]
for i in range(8):
    if num[i]: nums.append((i,num[i]))
#print(nums)
dp=[0]*(N+1)
for x,y in nums:
    try: dp[x]=1
    except IndexError: break
if nums[0][0]==N:
    print(nums[0][1])
    sys.exit()
for i in range(nums[0][0]+1,N+1):
    t=dp[i]
    for x,y in nums:
        if i-x>0:
            if dp[i-x]:
                t=max(t,dp[i-x]+1)
    if t:dp[i]=t
#print(dp)
nums.sort(key=lambda x:-x[1])
match=N
digit=dp[N]
for _ in range(dp[N]):
    if digit==1:
        for x,y in nums:
            if x==match:
                print(y)
                break
        break
    for x,y in nums:
        if dp[match-x]==digit-1:
            print(y,end='')
            match-=x
            digit-=1
            break

Submission status: Accepted

Solution code:
import sys

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

if __name__ == '__main__':
    n, m = map(int, input().split())
    a = sorted(input().split(), reverse=True)

    dp = [-10007] * (n + 1)
    dp[0] = 0
    for i in a:
        step = mp[int(i)]
        for j in range(step, n + 1):
            dp[j] = max(dp[j - step] + 1, dp[j])

    i = n
    while i > 0:
        for x in a:
            step = mp[int(x)]
            if i >= step and dp[i - step] == dp[i] - 1:
                sys.stdout.write(x)
                i -= step
                break
    print()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
A = [int(a) for a in input().split()]
L = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
A.sort(reverse = True)

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

Submission status: Accepted

Solution code:
from operator import itemgetter
N, M = map(int, input().split())
A = list(map(int, input().split()))
B = [None, 2, 5, 5, 4, 5, 6, 3, 7, 6]
D = []
set_D = set()
A.sort(reverse=True)
for a in A:
    if B[a] in set_D:
        continue
    else:
        set_D.add(B[a])
        D.append([a, B[a]])

D.sort(key=itemgetter(0), reverse=True)
dp = [-10**10]*(N+1)
dp[0] = 0
for i in range(1, N+1):
    for elem in set_D:
        if i < elem or dp[i-elem] is None:
            continue
        dp[i] = max(dp[i], dp[i-elem]+1)
ans = ''
while N > 0:
    for i in range(len(D)):
        if N-D[i][1] < 0:
            continue
        if dp[N-D[i][1]] == dp[N]-1:
            ans += str(D[i][0])
            N -= D[i][1]
            break
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N, M = (int(i) for i in input().split())
A = [int(i) for i in input().split()]
num = [0,2,5,5,4,5,6,3,7,6]

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

for i in range(N+1):
    for j in range(M):
        n = num[A[j]]
        if i - n >= 0 and DP[i-n] != -1:
            DP[i] = max(DP[i], DP[i-n] * 10 + A[j])

print(DP[N])

Submission status: Accepted

Solution code:
# D
N, M = map(int, input().split())
A_list = list(map(int, input().split()))
needs_list = [6, 2, 5, 5, 4, 5, 6, 3, 7, 6]

# DP
DP = [-1]*(N+8)
DP[0] = 0
for i in range(N):
    for a in A_list:
        j = i+needs_list[a]
        DP[j] = max(DP[j], DP[i]*10+a)
print(DP[N])

Submission status: Accepted

Solution code:
import sys

N, M = (int(i) for i in input().split())
A = [int(i) for i in input().split()]
A.sort()
A.reverse()

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

A_num = [(num[a], -a) for a in A]
A_num.sort()

min_A = -A_num[0][1]
min_num = A_num[0][0]
keta_max = N//min_num

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

for i in range(N+1):
    for j in range(M):
        n = num[A[j]]
        if i - n >= 0 and DP[i-n] != -1:
            DP[i] = max(DP[i], DP[i-n] * 10 + A[j])

print(DP[N])

Submission status: Accepted

Solution code:
INF = 10**10
arr = [INF,2,5,5,4,5,6,3,7,6]
N,M = map(int,input().split())
src = sorted(list(map(int,input().split())))

dp = [-INF]*(N+1)
dp[0] = 0
for i in range(N):
    for j in src:
        if i + arr[j] <= N:
            dp[i+arr[j]] = max(dp[i+arr[j]],dp[i] + 1)
dim = dp[N]
ans  = ''
while(dim > 0):
    for i in src[::-1]:
        if N >= arr[i] and dp[N-arr[i]] + 1 == dp[N]:
            ans += str(i)
            N -= arr[i]
            dim -= 1
            break
print(ans)

Submission status: Accepted

Solution code:
n,m,*a=map(int,open(0).read().split())
d=[0]*-~n
for i in range(1,n+1):
 for j,k in zip(range(9),(2,5,5,4,5,6,3,7,6)):
  if i-k>=0and(i-k<1or d[i-k])and j+1in a:d[i]=max(d[i],d[i-k]*10+j+1)
print(d[n])

Submission status: Accepted

Solution code:
L = [6, 2, 5, 5, 4, 5, 6, 3, 7, 6]

N, M = map(int, input().split())
A = [int(a) for a in input().split()]
B = [(A[i], L[A[i]]) for i in range(M)]

X = [0] + ([-1] * N)
for i in range(1, N+1):
  for b in B:
    if b[1] <= i:
      X[i] = max(X[i], X[i-b[1]] * 10 + b[0])

print(X[N])

Submission status: Accepted

Solution code:
a,b=list(map(int,input().split()))
X={1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}
A=list(map(int,input().split()))
B=[v for k,v in X.items() if k in A]
#print(B)
DP=[0]+[[] for i in range(10**4+1)]
L=[[] for i in range(10**4+1)]
for i in range(10):
    if i in B:
        DP[i]=1
        L[i].append(i)
#print(DP)
for i in range(1,10**4+1):
    if [DP[i-j] for j in B if i-j>=0 and not DP[i-j]==[]]==[]:
        DP[i]=[]
    else:
#        print(i,[DP[i-j] for j in B if i-j>=0 and not DP[i-j]==[]])
        M=[DP[i-j] for j in B if i-j>=0 and not DP[i-j]==[]]
        DP[i]=max([DP[i-j] for j in B if i-j>=0 and not DP[i-j]==[]])+1
        l=[0]
        for t in B:
            if not DP[i-t]==[] and DP[i]==DP[i-t]+1:
                l=l+[k for k,v in X.items() if v==t and k in A]
                L[i]=L[i-t]+[max(l)]
L[a].sort(reverse=True)
s='0'
for i in L[a]:
    s+=str(i)
print(int(s))

Submission status: Accepted

Solution code:
n, m = map(int, input().strip().split())
a = list(map(int, input().strip().split()))

dp = [None] * (n+1)
dp[0] = 0
x = (0,2,5,5,4,5,6,3,7,6)
for i in range(2, n+1):
    for v in a:
        if i-x[v] >= 0 and dp[i-x[v]] != None:
            if not dp[i]:
                dp[i] = dp[i-x[v]]*10+v
            else:
                dp[i] = max(dp[i], dp[i-x[v]]*10+v)

print(dp[n])

Submission status: Accepted

Solution code:
import math


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

MAX_N = int(1e4)
dp = [-1 for i in range(MAX_N + 20)]
dp[0] = 0

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

for i in range(N + 1):
    for j in A:
        tmp = dp[i]
        if tmp == -1:
            continue
        if tmp == 0:
            dp[i + mc[j - 1]] = max(dp[i + mc[j - 1]], j)
        else:
            dp[i + mc[j - 1]] = max(dp[i + mc[j - 1]], tmp * 10 + j)

ans = dp[N]
print(ans)

Submission status: Accepted

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

cost = [cost[A] for A in a]

dp = [-float('inf')] * (N + 1)
dp[0] = 0
for i in range(1, N + 1):
    for j in range(len(cost)):
        if cost[j] <= i:
            dp[i] = max(dp[i], dp[i - cost[j]] * 10 + a[j])

print(dp[N])

Submission status: Accepted

Solution code:
n, m = map(int,input().split())
alist = list(map(int, input().split()))
matches = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
alist.sort(reverse=True)

dp = [-1 for _ in range(n + 1)]
dp[0] = 0
for a in alist:
    match = matches[a]
    for i in range(n - match + 1):
        if dp[i] == -1:
            continue
        dp[i + match] = max(dp[i + match], dp[i] * 10 + a)

print(dp[-1])

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
a = [int(m) for m in input().split()]
a.sort(reverse=True)
dp = []
for i in range(10 * n):
    dp.append(0)

b = [0,2,5,5,4,5,6,3,7,6]
for i in range(1, n + 1):
    for j in range(len(a)):
        if i - b[a[j]] >= 0:
            if (dp[i - b[a[j]]] == 0 and i - b[a[j]] == 0) or dp[i - b[a[j]]] != 0:
                dp[i] = max(dp[i], dp[i - b[a[j]]] + a[j])
        else:
            pass
    if i != n:
        dp[i] *= 10

print(dp[n])

Submission status: Accepted

Solution code:
# D
n,m = map(int, input().split())
b = [0,2,5,5,4,5,6,3,7,6]
a = [0]+list(map(int, input().split()))
f = [-1]*10010
f[0]=0
for i in range(1,n+1):
    for j in range(1,m+1):
        x = a[j]
        if(i-b[x]<0):
            continue
        f[i] = max(f[i],f[i-b[x]]*10 + x)
print(f[n])

Submission status: Accepted

Solution code:
from collections import defaultdict as dd

n,m=map(int,input().split())
*a,=map(int,input().split())
dp=[-1]*(n+1)
ans = [0] * (n + 1)

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

d={i:cost[i] for i in a}

dp[0] = 0
for i in range(1,n+1):
    for j in range(10)[::-1]:
        if not j in d:
            continue
        if cost[j] > i:
            continue
        if dp[i] < dp[i - cost[j]] + 1:
            dp[i] = dp[i - cost[j]] + 1
            ans[i] = j

S = ""
pos = n

while pos != 0:
    S += str(ans[pos])
    pos -= cost[ans[pos]]

print(S)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
A = [int(a) for a in input().split()]    
L = [2, 5, 5, 4, 5, 6, 3, 7, 6]
B = [[A[i], L[A[i]-1]] for i in range(M)]

X = [0] + [-1] * N
for i in range(1, N+1):
    for b in B:
        if b[1] <= i:
            X[i] = max(X[i], X[i-b[1]]*10 + b[0])

print(X[N])

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# coding: utf-8

import copy

def main():
    n, m = list(map(int, input().split()))
    num = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
    la = list(map(int, input().split()))
    la.sort()
    dp = [-1 for _ in range(n+10)]
    dp[0] = 0
    for i in range(n):
        if dp[i] == -1:
            continue
        for a in la:
            l = num[a]
            dp[i+l] = max(dp[i+l], dp[i]*10+a)
    print(dp[n])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,m,*a=map(int,open(0).read().split())
d=[0]*-~n
for i in range(1,n+1):
 for j,k in zip((1,2,3,4,5,6,7,8,9),(2,5,5,4,5,6,3,7,6)):
  if i-k>=0and(i-k<1or d[i-k])and j in a:d[i]=max(d[i],d[i-k]*10+j)
print(d[n])

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

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

n,mmm = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]


bar = list(set([table[i] for i in a]))
bar.sort()
minbar=min(bar)

maxnum = ['0']*10
for i in bar:
    mbmax = max([j for j in a if table[j] == i])
    maxnum[i]=str(mbmax)
#print(maxnum,bar)
ans = ['0']*(n+10)
for i in range(8):
    if i in bar:
        ans[i]=maxnum[i]
#print(ans)
for i in range(n+1):
    if ans[i] == '0':
        continue
    for j in bar:
        if maxnum[j] > ans[i][0]:
            tmp = maxnum[j]+ans[i]
        else:
            tmp = ans[i]+maxnum[j]
        if len(tmp) < len(ans[i+j]):
            continue
        elif len(tmp) > len(ans[i+j]):
            ans[i+j] = tmp
        else:
            ans[i+j] = max(ans[i+j],tmp)

#print(ans)
print(ans[n])

Submission status: Accepted

Solution code:
M = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]

max_vs = [''] * 10001
n, m = [int(v) for v in input().split()]
a = [int(v) for v in input().split()]
for i in range(1, n + 1):
        for v in a:
                if M[v] > i:
                        continue
                elif M[v] == i:
                        if max_vs[i] == '' or int(max_vs[i]) < v:
                                max_vs[i] = str(v)
                else:
                        if max_vs[i - M[v]] != '':
                                if (max_vs[i] == '') or (len(max_vs[i]) < len(str(v) + max_vs[i - M[v]])) or (len(max_vs[i]) == len(str(v) + max_vs[i - M[v]]) and max_vs[i] < str(v) + max_vs[i - M[v]]):
                                        max_vs[i] = str(v) + max_vs[i - M[v]]
print(max_vs[n])

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))
cost = [-1, 2, 5, 5, 4, 5, 6, 3, 7, 6]
can_cost = sorted([cost[a] for a in A])
D = {}
for a in A:
    c = cost[a]
    D[c] = max(a, D.setdefault(c, -1))

min_cost = can_cost[0]
min_cost_num = D[min_cost]


def f2(v, l, num):
    L = list(str(v))
    min_cost = cost[int(num)]
    num = D.setdefault(min_cost + l, -1)
    if num == -1:
        return -1

    min_cost_num = D[min_cost]
    L[L.index(str(min_cost_num))] = str(num)
    L.sort(reverse=True)
    return int("".join(L))


def f(v, l):
    L = list(str(v))
    set_L = set(L)
    L2 = [f2(v, l, num) for num in set_L]
    return max(L2)

def g(K, r):
    temp = int("".join([str(min_cost_num)] * K))
    dp = [[-1 for _ in range(min(r, K) + 1)] for __ in range(r + 1)]
    dp[0][0] = temp

    for k in range(min(r, K)):
        for n in range(r):
            v = dp[n][k]
            if v == -1:
                continue
            for l in range(1, r - n + 1):
                dp[n + l][k + 1] = max(dp[n + l][k + 1], f(v, l))
    return max(dp[r])

K = N // min_cost
r = N - K * min_cost
res = g(K, r)
while res == -1:
    K -= 1
    r += min_cost
    res = g(K, r)
print(res)

Submission status: Accepted

Solution code:
#coding:utf-8
N,M  = map(int,input().split())
A = list(map(int,input().split()))
b = 0
c = [0,2,5,5,4,5,6,3,7,6]
bagS = [[] for i in range(N+1)]

def check2(A,B):

    if len(A) > len(B):
        return A
    elif len(A) < len(B):
        return B
    for a,b in zip(A,B):
        if  a- b > 0:
            return A
        elif a-b < 0:
            return B
    return A


while b != N:

    for a in A:
        if b+ c[a] <= N:
  
            bagS[b+c[a]] = check2(bagS[b+c[a]],sorted((bagS[b]+[a]),reverse=True))

    for i in range(b+1,N+1):
        if bagS[i]:
            b = i
            break
p = 0
for i in bagS[N]:
    p = p*10+i
print(p)

Submission status: Accepted

Solution code:
from operator import itemgetter
tik = [[1,2],[7,3],[4,4],[5,5],[3,5],[2,5],[9,6],[8,7],[6,6]]
dic = {"1":2,"7":3,"4":4,"5":5,"3":5,"2":5,"9":6,"8":7,"6":6}

n,k = map(int, input().split())
x = list(map(int, input().split()))
dp = [0]+[-1]*(n+10)
q = []
for i in range(k):
    q.append([x[i],dic[str(x[i])]])

q = sorted(q, key=itemgetter(1), reverse=False)

s = []
p=0
t = 0
for i in range(n):
    for j in range(k):
        if i+q[j][1] <=n:
            if dp[i]!=-1:
            
                if  dp[i]==0:
                    ko = q[j][0]
                    dp[i+q[j][1]] = max(q[j][0],dp[i+q[j][1]])

                else:
                    ko = dp[i]+q[j][0]
                    dp[i+q[j][1]] = max(dp[i]*10+q[j][0], dp[i+q[j][1]])
        #if i+q[j][1] ==n:
            #print(dp[20])
s = list(str(dp[n]))
s.sort()
s = s[::-1]
print(''.join(s))

Submission status: Accepted

Solution code:
def inv(x, ava):
    if x == 2:
        if 1 in ava:
            return 1
        else:
            return -1
    if x == 3:
        if 7 in ava:
            return 7
        else:
            return -1
    if x == 4:
        if 4 in ava:
            return 4
        else:
            return -1
    if x == 5:
        if 5 in ava:
            return 5
        if 3 in ava:
            return 3
        if 2 in ava:
            return 2
        else:
            return -1
    if x == 6:
        if 9 in ava:
            return 9
        if 6 in ava:
            return 6
        else:
            return -1
    if x == 7:
        if 8 in ava:
            return 8
        else:
            return -1
n, m = map(int, input().split())
ava = list(map(int, input().split()))
dp = [[] for _ in range(n+1)]
number = [inv(x,ava) for x in range(2,8)]
avapre = []
for i in range(6):
    if number[i] != -1:
        avapre.append(i+2)
avapresort = sorted(avapre,key = lambda x: number[x-2],reverse=True)
dp = [0 for _ in range(n+1)]
for i in range(1, n+1):
    if i < avapre[0]:
        dp[i] = -1
    else:
        dp[i] = -1
        for pre in avapre:
            if i - pre >= 0:
                dp[i] = max(dp[i], dp[i-pre]+1)
i = n
while(i > 0):
    for pre in avapresort:
        if i - pre >= 0 and dp[i] == dp[i-pre] + 1:
            print(number[pre-2], end='')
            i -= pre
            break
print()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))
cost = [-1, 2, 5, 5, 4, 5, 6, 3, 7, 6]
can_cost = sorted([cost[a] for a in A])
D = {}
for a in A:
    c = cost[a]
    D[c] = max(a, D.setdefault(c, -1))

min_cost = can_cost[0]
min_cost_num = D[min_cost]


def f2(v, l, num):
    L = list(str(v))
    min_cost = cost[int(num)]
    num = D.setdefault(min_cost + l, -1)
    if num == -1:
        return -1

    min_cost_num = D[min_cost]
    L[L.index(str(min_cost_num))] = str(num)
    L.sort(reverse=True)
    return int("".join(L))


def f(v, l):
    L = list(str(v))
    set_L = set(L)
    L2 = [f2(v, l, num) for num in set_L]
    return max(L2)

def g(K, r):
    temp = int("".join([str(min_cost_num)] * K))
    dp = [[-1 for _ in range(min(r, K) + 1)] for __ in range(r + 1)]
    dp[0][0] = temp

    for k in range(min(r, K)):
        for n in range(r):
            v = dp[n][k]
            if v == -1:
                continue
            for l in range(1, r - n + 1):
                dp[n + l][k + 1] = max(dp[n + l][k + 1], f(v, l))
    return max(dp[r])

K = N // min_cost
r = N - K * min_cost
res = g(K, r)
if g(K, r) == -1:
    res = g(K - 1, r + min_cost)
print(res)

Submission status: Accepted

Solution code:
# 基本はDPだけど時間短縮のため途中は必ず一番効率のいいやつを使う

N, M = map(int, input().split())
A = [int(a) for a in input().split()]    
L = [2, 5, 5, 4, 5, 6, 3, 7, 6]
B = [[A[i], L[A[i]-1]] for i in range(M)]
best = sorted(B, key = lambda x: x[1]*10-x[0])[0]
adj = max((N - 200),0)//best[1]
N -= best[1] * adj

X = [0] + [-10**9] * N
for i in range(1, N+1):
    if i > 50 and i < N-50:
        X[i] = X[i-best[1]]*10 + best[0]
    else:
        for b in B:
            if b[1] <= i:
                X[i] = max(X[i], X[i-b[1]]*10 + b[0])

ans = str(X[N])
ans = ans[:10] + str(best[0]) * adj + ans[10:]

print(ans)

Submission status: Accepted

Solution code:
n,m,*a=map(int,open(0).read().split())
d=[0]*-~n
for i in range(1,n+1):
 for j,k in zip((1,2,3,4,5,6,7,8,9),(2,5,5,4,5,6,3,7,6)):
  if j in a and i-k>=0and(i-k<1or d[i-k]):d[i]=max(d[i],d[i-k]*10+j)
print(d[n])