Problem:


Score : 400 points

Problem Statement

Find the largest integer that can be formed with exactly N matchsticks, under the following conditions:

Every digit in the integer must be one of the digits A_1, A_2, ..., A_M (1 \leq A_i \leq 9).

The number of matchsticks used to form digits 1, 2, 3, 4, 5, 6, 7, 8, 9 should be 2, 5, 5, 4, 5, 6, 3, 7, 6, respectively.

Constraints

All values in input are integers.

2 \leq N \leq 10^4

1 \leq M \leq 9

1 \leq A_i \leq 9

A_i are all different.

There exists an integer that can be formed by exactly N matchsticks under the conditions.

Input

Input is given from Standard Input in the following format:

N M
A_1 A_2 ... A_M

Output

Print the largest integer that can be formed with exactly N matchsticks under the conditions in the problem statement.

Sample Input 1

20 4
3 7 8 4

Sample Output 1

777773

The integer 777773 can be formed with 3 + 3 + 3 + 3 + 3 + 5 = 20 matchsticks, and this is the largest integer that can be formed by 20 matchsticks under the conditions.

Sample Input 2

101 9
9 8 7 6 5 4 3 2 1

Sample Output 2

71111111111111111111111111111111111111111111111111

The output may not fit into a 64-bit integer type.

Sample Input 3

15 3
5 4 6

Sample Output 3

654



Sample input:
20 4
3 7 8 4


Sample output:
777773

Submission status: Wrong Answer

Solution code:
# 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()
    c = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]  # マッチ棒の本数との変換
    f = [0] + [-1] * 10010  # DP
    
    id.S(a, 1)
    
    # マッチ棒の本数分だけ回す
    for i in r(n):
        # 入力の1番目(k)は不必要
        i += 1
        for x in a:
            if i - c[x] >= 0:
                f[i] = max(f[i], f[i - c[x]] * 10 + x)
                break

    print(f[n])
    print(f)


main()

Submission status: Wrong Answer

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()
    c = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
    f = [-1] * (n + 10)
    f[0] = 0

    for i in r(n):
        i += 1
        for x in a:
            if i - c[x] >= 0:
                f[i] = max(f[i], f[i - c[x]] * 10 + x)

    print(f[n])
    print(f)


main()

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, OrderedDict
from copy import deepcopy
from functools import lru_cache, reduce
from math import ceil, floor
from sys import setrecursionlimit

import heapq
import itertools
import operator


def get_int():
    return int(input())


def get_str():
    return input().strip()


def get_int_list():
    return [int(i) for i in input().split()]


def get_char_list():
    return list(input().strip())


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


# inputs
N, M = 0, 0
A = [0]


def hoge():
    d = dict()
    def labeler(label, iter):
        enumerate()


def set_inputs():
    global N, M, A
    N, M = get_int_list()
    A = get_int_list()


@lru_cache(maxsize=None)
def dp(i):
    if i < min(COST[a] for a in A):
        return 0
    return max(dp(i - COST[a]) + 1 for a in A)


def main():
    setrecursionlimit(100000)
    set_inputs()

    candidates = sorted(A, reverse=True)
    ret = []
    n = N
    for i in range(dp(N)):
        for a in candidates:
            cond = True
            if i == dp(N) - 1:
                cond = COST[a] == n
            if dp(n - COST[a]) == dp(n) - 1 and cond:
                ret.append(a)
                n -= COST[a]
                break
    print(''.join(str(r) for r in ret))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
a=list(map(int,input().split()))
k=[0,2,5,5,4,5,6,3,7,6]
l=[]
for i in range(m):
  l.append((k[a[i]],a[i]))
l.sort()
print(l)
x=n//l[0][0]
y=n%l[0][0]
z=0
for i in range(m):
  if l[i][0]==l[0][0]+y:
    if l[i][1]>z:
      z=l[i][1]
if z>l[0][1]:
  ans=int(str(z)+str(l[0][1])*(x-1))
else:
  ans=int(str(l[0][1])*(x-1)+str(z))
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Feb 16 19:31:10 2019
ABC118D
@author: maezawa
"""
import copy

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

nmatch = [2,5,5,4,5,6,3,7,6]
rmatch = list(reversed(nmatch))
nmdic = dict([(i+1,nmatch[i]) for i in range(9)])
#nums = [[],[],[1],[7],[4],[2,3,5],[6,9],[8]]
nums = [[] for _ in range(10)]
for  i in a:
    nums[nmdic[i]].append(i)
        
#print(nmdic)
#print(nums)

dp = [[-1,[]] for _ in range(n+1)]
dp[0] = [0, []]
#print(dp)

for i in range(1, n+1):
    cnds = []
    for j in range(2, 8):
        if nums[j] == []:
            continue
        if i-j < 0:
            continue
        if dp[i-j][0] == -1:
            continue
        cndo = dp[i-j][0]+1
        cndos = copy.copy(dp[i-j][1])
        cndos.append(max(nums[j]))
        cnds.append([cndo, cndos])
        #print(i, i-j, cnds, cndos)
    if cnds == []:
        continue
    dp[i] = max(cnds, key=lambda x: x[0])

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

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
A = sorted([i for i in input().split()], reverse=True)

# dp[i] = i本使ってできる最大の数

def mx(a, b):
    if len(a) != len(b):
        if len(a) > len(b):
            return a
        else:
            return b
    if a >= b:
        return a
    else:
        return b

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

# xを作るために使うマッチの本数
def f(x):
    return h[x]

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

for i in range(N+1):
    for a in A:
        if i - f(a) < 0:
            continue
        dp[i] = mx(dp[i-f(a)] + a, dp[i])
print(dp[N][1:])

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
A = sorted([i for i in input().split()], reverse=True)

# dp[i] = i本使ってできる最大の数

def mx(a, b):
    if len(a) != len(b):
        if len(a) > len(b):
            return a
        else:
            return b
    if a >= b:
        return a
    else:
        return b

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

# xを作るために使うマッチの本数
def f(x):
    return h[x]

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

for i in range(N+1):
    for a in A:
        if i - f(a) < 0:
            continue
        dp[i] = mx(dp[i-f(a)] + a, dp[i])
print(dp[N].strip())

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
A = sorted([i for i in input().split()], reverse=True)

# dp[i] = i本使ってできる最大の数

def mx(a, b):
    if len(a) != len(b):
        if len(a) > len(b):
            return a
        else:
            return b
    if a >= b:
        return a
    else:
        return b

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

# xを作るために使うマッチの本数
def f(x):
    return h[x]

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

for i in range(N+1):
    for a in A:
        if i - f(a) < 0:
            continue
        dp[i] = mx(dp[i-f(a)] + a, dp[i])
print(dp[N])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from copy import copy

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

ms = [2,5,5,4,5,6,3,7,6]
dic = defaultdict(lambda: 0)
for a in A:
    dic[ms[a-1]] = max(dic[ms[a-1]], a)

sd = sorted(dic.items())

dp = [None] * (N+1)
dp[0] = defaultdict(lambda: 0)

for i in range(sd[0][0], N+1):
    for l,a in sd:
        if i-l < 0: break
        if dp[i-l] is None: continue
        dp[i] = copy(dp[i-l])
        dp[i][a] += 1
        break

ans = ''
for a,n in sorted(dp[-1].items(), reverse=True):
    ans += str(a) * n
print(ans)

Submission status: Wrong Answer

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]
B = [(i, num[i]) for i in A]
ans = {}
for i in range(N + 1):
    x = '0'
    for j, k in B:
        if i - k < 0:
            continue
        if i == k:
            x = str(max(int(x), int(j)))
            continue
        an = ans[i - k]
        if an == '0':
            continue
        if x > an[0]:
            y = str(j) + an
        else:
            y = an + str(j)
        x = str(max(int(x), int(y)))
    ans[i] = x
print(ans[N])

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
a = list(map(int,input().split()))
def f(ai):
    aset = [0,2,5,5,4,5,6,3,7,6]
    return aset[ai]
mina = 8
for i in range(len(a)):
    if f(mina)==f(a[i]) and mina<a[i]:
        mina = a[i]
    if f(mina)>f(a[i]):
        mina = a[i]
array = [mina for i in range(int(n/f(mina)))]
n = n%f(mina)
for i in range(len(array)):
    if n==0:
        break
    m = f(array[i])
    for j in range(m+1,n+m+1):
        for k in a:
            if j==f(k) and array[i]<k:
                array[i] = k
    n-=f(array[i])-m
if n>0:
    for i in range(len(array)-1,-1,-1):
        if n==0:
            break
        m = f(array[i])
        for j in range(n+m,m,-1):
            for k in a:
                if j==f(k):
                    array[i]=k
                if f(array[i])==f(k) and array[i]<k:
                    array[i]=k
            if j==f(array[i]):
                break
        n-=f(array[i])-m
for i in range(len(array)):
    print(array[i],end="")
print()

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
a = list(map(int,input().split()))
def f(ai):
    aset = [0,2,5,5,4,5,6,3,7,6]
    return aset[ai]
mina = 8
for i in range(len(a)):
    if f(mina)==f(a[i]) and mina<a[i]:
        mina = a[i]
    if f(mina)>f(a[i]):
        mina = a[i]
array = [mina for i in range(int(n/f(mina)))]
n = n%f(mina)
for i in range(len(array)):
    if n==0:
        break
    m = f(array[i])
    for j in range(m+1,n+m+1):
        for k in a:
            if j==f(k) and array[i]<k:
                array[i] = k
    n-=f(array[i])-m
if n>0:
    for i in range(len(array)-1,-1,-1):
        if n==0:
            break
        m = f(array[i])
        for j in range(n+m,m,-1):
            print(j)
            for k in a:
                if j==f(k):
                    array[i]=k
                if f(array[i])==f(k) and array[i]<k:
                    array[i]=k
            if j==f(array[i]):
                break
        n-=f(array[i])-m
for i in range(len(array)):
    print(array[i],end="")
print()

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
a = list(map(int,input().split()))
def f(ai):
    aset = [0,2,5,5,4,5,6,3,7,6]
    return aset[ai]
mina = 8
for i in range(len(a)):
    if f(mina)==f(a[i]) and mina<a[i]:
        mina = a[i]
    if f(mina)>f(a[i]):
        mina = a[i]
array = [mina for i in range(int(n/f(mina)))]
n = n%f(mina)
for i in range(len(array)):
    if n==0:
        break
    m = f(array[i])
    for j in range(m+1,n+m+1):
        for k in a:
            if j==f(k) and array[i]<k:
                array[i] = k
    n-=f(array[i])-m
if n>0:
    for i in range(len(array)-1,-1,-1):
        if n==0:
            break
        m = f(array[i])
        print("----------")
        for j in range(n+m,m,-1):
            print(j)
            for k in a:
                if j==f(k):
                    array[i]=k
                if f(array[i])==f(k) and array[i]<k:
                    array[i]=k
            if j==f(array[i]):
                break
        n-=f(array[i])-m
for i in range(len(array)):
    print(array[i],end="")
print()

Submission status: Wrong Answer

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)
print(A)
dp = [0] + ([-1]*N)
print(dp)
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)
print(dp[-1])

Submission status: Wrong Answer

Solution code:
n,m,*a=map(int,open(0).read().split())
d=[0]*n*9
for i in range(n):d[i+1]=max(j+d[i-int('0144345265'[j])]*10for j in a)
print(d[n])

Submission status: Wrong Answer

Solution code:
n,m,*a=map(int,open(0).read().split())
d=[0]*n+[-1]*9
for i in range(n+1):d[i]=max(d[i-int("0255456376"[j])]*10+j for j in a)
print(d[n])

Submission status: Wrong Answer

Solution code:
s = list(map(int, input().split()))
t = list(map(int, input().split()))

n=s[0]
num=[2,5,5,4,5,6,3,7,6]
aru=[0,0,0,0,0,0,0,0,0,0]
for i in range(len(t)):
    aru[t[i]]+=1

use=[0,0,0,0,0,0,0,0,0]
k1=[2,3,4,5,5,5,6,6,7]
k2=[1,7,4,2,3,5,6,9,8]
for i in range(9):
    if(aru[k2[i]]==1):
        use[k1[i]]=k2[i]

maxd=0
[maxset,settemp]=[[],[]]

for ii in range(5**5):
    i=[(ii%(5**(k+1)))//(5**k) for k in range(5)]
    flag=0
    for i1 in range(5):
        if(i[i1]>0 and use[i1+3]==0):
            flag+=1
    if(flag==0):
        d = 3*i[0]+4*i[1]+5*i[2]+6*i[3]+7*i[4]
        total = d
        for i1 in range(6):
            j=(5-i1)+2
            if((n-total)>=0 and (n-total)%j==0 and use[j]!=0):
                d+=(n-total)//j
                if((n-total)//j > 0):
                    settemp=[use[j] for i2 in range((n-total)//j)]
                else:
                    settemp=[]
                for i3 in range(5):
                    if(i[i3]>0):
                        settemp.extend([use[i3+3] for i2 in range(i[i3])])
        if(maxd<=len(settemp)):
            maxd=len(settemp)
            settemp.sort(reverse=True)
            maxset=settemp
        elif(maxd==len(settemp)):
            settemp.sort(reverse=True)
            for i1 in range(len(settemp)):
                if(maxset[i1]>settemp[i1]):
                    break
                elif(maxset[i1]<settemp[i1]):
                    maxset=settemp
                    maxd=len(settemp)
                    break

ans=""
for i in range(len(maxset)):
    ans+=str(maxset[i])
print(ans)

Submission status: Wrong Answer

Solution code:
import time
n, m = map(int, input().split())
numbers = list(map(int, input().split()))
costs = [0,2,5,5,4,5,6,3,7,6]
f = [-1]*10010
f[0] = 0
for i in range(1, n+1):
    for x in numbers:
        if i-costs[x] >= 0:
            f[i] = max(f[i], f[i-costs[x]]*10+x)
print(f)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
A=list(input().split())
c=[0,2,5,5,4,5,6,3,7,6]

dp=['']*(n+1)
dp[0]=''
for i in range(1,n+1):
    max=''
    for j in range(m):
        if i-c[int(A[j])]>=0 and i-c[int(A[j])]!=1 and i-c[int(A[j])]!=2:
            if len(dp[i-c[int(A[j])]]+A[j])>len(max):
                max=dp[i-c[int(A[j])]]+A[j]
            elif len(dp[i-c[int(A[j])]]+A[j])==len(max) and dp[i-c[int(A[j])]]+A[j]>max:
                max=dp[i-c[int(A[j])]]+A[j]
    dp[i]=max
    #print(dp)
print(dp[n])

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

def solve():
    N, M  = map(int, input().split())
    A = sorted(list(map(int, input().split())), reverse=1)
    I = [0,2,5,5,4,5,6,3,7,6]
    dp_a = [0 for _ in range(8)]
    for i in range(2, N%420+1):
        dp_a[i%8] = max((10*dp_a[j%8]+a for j,a in ((i-I[a], a) for a in A) if j >= 0 and (dp_a[j%8] != 0 or I[a] == i)), default=0)
    res = str(dp_a[i%8]) + str(min(A, key=lambda a: I[a]))*(N//420)
    return str(res)
if __name__ == '__main__':
    print(solve())

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
o_need = [2, 5, 5, 4, 5, 6, 3, 7, 6]
need = [o_need[i-1] for i in A]
z = zip(need, A)
z = sorted(z)
need, A = map(list, zip(*z))
r = N % need[0]
q = N // need[0]
Bn = [need[0]]*q
Ba = [A[0]]*q
dig = len(Bn)-1
digmax = dig
cnt = 1
cntmax = len(A)-1
digback = 1
while sum(Bn) != N:
  #print(Ba)
  Bn[dig] = need[cnt]
  Ba[dig] = A[cnt]
  cnt += 1
  if cnt == cntmax+1:
    cnt = 0
    if dig == digmax:
      dig -= digback
      digback += 1
    else:
      dig += 1

Ba.sort(reverse=True)
print(''.join(list(map(str, Ba))))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
import copy
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, M, A):
    c = [
        -1,
        2, # 1 
        5, # 2
        5, # 3
        4, # 4
        5, # 5
        6, # 6
        3, # 7
        7, # 8
        6, # 9
        ]
    
    if 2 in A and 5 in A:
        A.remove(2)
    if 3 in A and 5 in A:
        A.remove(3)
    if 2 in A and 3 in A:
        A.remove(2)
    if 6 in A and 9 in A:
        A.remove(6)



    dp = [None] * (N+1) 
    dp[N] = (0, Counter())
    for i in range(N, 0, -1):
        # print(i)
        if dp[i] is None:
            continue
        
        for a in A:
            if i - c[a] < 0:
                continue
            
            if dp[i-c[a]] is None:
                c_ = copy.deepcopy(dp[i][1])
                c_[a] += 1
                dp[i-c[a]] =  (dp[i][0]+1, c_)
            
            elif dp[i][0]+1 > dp[i-c[a]][0]:
                c_ = copy.deepcopy(dp[i][1])
                c_[a] += 1
                dp[i-c[a]] =  (dp[i][0]+1, c_)

    ans = ""
    for r in  sorted(dp[0][1], reverse=True):
        ans += str(r) * dp[0][1][r]
    return ans


def main():
    # N = read_int()
    N, M = read_int_n()
    A = read_int_n()
    print(slv(N, M, A))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
import copy
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, M, A):
    c = [
        -1,
        2, # 1 
        5, # 2
        5, # 3
        4, # 4
        5, # 5
        6, # 6
        3, # 7
        7, # 8
        6, # 9
        ]
    
    if 2 in A and 5 in A:
        A.remove(2)
    if 3 in A and 5 in A:
        A.remove(3)
    if 2 in A and 3 in A:
        A.remove(2)
    if 6 in A and 9 in A:
        A.remove(6)



    dp = [None] * (N+1) 
    dp[N] = (0, Counter())
    for i in range(N, 0, -1):
        print(i)
        if dp[i] is None:
            continue
        
        for a in A:
            if i - c[a] < 0:
                continue
            
            if dp[i-c[a]] is None:
                c_ = copy.deepcopy(dp[i][1])
                c_[a] += 1
                dp[i-c[a]] =  (dp[i][0]+1, c_)
            
            elif dp[i][0]+1 > dp[i-c[a]][0]:
                c_ = copy.deepcopy(dp[i][1])
                c_[a] += 1
                dp[i-c[a]] =  (dp[i][0]+1, c_)

    ans = ""
    for r in  sorted(dp[0][1], reverse=True):
        ans += str(r) * dp[0][1][r]
    return ans


def main():
    # N = read_int()
    N, M = read_int_n()
    A = read_int_n()
    print(slv(N, M, A))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
A=[int(i) for i in input().split()]
Match=[0,2,5,5,4,5,6,3,7,6]
A.sort(reverse=True)
dp=[0]*(N+1)
dp[0]=1
for i in range(1,N+1):
  for a in A:
    if i>=Match[a]:
      dp[i]|=dp[i-Match[a]]<<1

for k in range(N)[::-1]:
  if dp[N]&(1<<k):
    S=k
    break
ans=[]
m=0
for k in range(S):
  if N-Match[A[m]]>=0:
    if dp[N-Match[A[m]]]&(1<<(S-k-1)):
      ans.append(str(A[m]))
      N-=Match[A[m]]
  else:
    for l in range(m+1,len(A)):
      if N-Match[A[l]]>=0:
        if dp[N-Match[A[l]]]&(1<<(S-k-1)):
          m=l
          ans.append(str(A[m]))
          N-=Match[A[m]]
          break
print("".join(ans))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
import copy
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, M, A):
    c = [
        -1,
        2, # 1 
        5, # 2
        5, # 3
        4, # 4
        5, # 5
        6, # 6
        3, # 7
        7, # 8
        6, # 9
        ]
    
    if 2 in A and 5 in A:
        A.remove(2)
    if 3 in A and 5 in A:
        A.remove(3)
    if 2 in A and 3 in A:
        A.remove(2)
    if 6 in A and 9 in A:
        A.remove(6)



    dp = [None] * (N+1) 
    dp[N] = (0, Counter())
    for i in range(N, 0, -1):
        if dp[i] is None:
            continue
        
        for a in A:
            if i - c[a] < 0:
                continue
            
            if dp[i-c[a]] is None:
                c_ = copy.copy(dp[i][1])
                c_[a] += 1
                dp[i-c[a]] =  (dp[i][0]+1, c_)
            
            elif dp[i][0]+1 > dp[i-c[a]][0]:
                c_ = copy.copy(dp[i][1])
                c_[a] += 1
                dp[i-c[a]] =  (dp[i][0]+1, c_)
    # print(0, dp[0])

    ans = ""
    for r in  sorted(dp[0][1], reverse=True):
        ans += str(r) * dp[0][1][r]
    return ans


def main():
    # N = read_int()
    N, M = read_int_n()
    A = read_int_n()
    print(slv(N, M, A))


if __name__ == '__main__':
    main()