Problem: 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.

Submission attempts (in order):
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

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

chosen = {}

n, m = li()
a = list(li())

for ai in a:
    chosen[str(ai)] = num_cost[ai]

dp = ["ng"]*(n+1)
dp[0] = ""
for i in range(n):
    if dp[i] == "ng":
        continue

    for num, cost in chosen.items():
        if i + cost <= n and dp[i+cost] == "ng":
            dp[i+cost] = "".join(sorted(num+dp[i]))

        elif i + cost <= n:
            if len(dp[i+cost]) < len(dp[i]) + 1:
                dp[i+cost] = "".join(sorted(num+dp[i]))

            elif len(dp[i+cost]) > len(dp[i]) + 1:
                dp[i+cost] = dp[i+cost]

            else:
                dp[i+cost] = max(dp[i+cost],
                                 "".join(sorted(num+dp[i])))

print(dp[n])

import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

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

n,m = li()
a = list(li())

use = {}
for ai in a:
    if dic[ai] not in use.keys():
        use.update({dic[ai]: ai})
    else:
        dic[ai] = max(dic[ai], ai)
        

desc = {}
edge = {}
for idx, num in enumerate(sorted(use.values(), reverse=True)):
    desc.update({idx: num})
    edge.update({idx: dic[num]})
    
        

INF = float('inf')
dp = [[-INF]*len(use) for _ in range(n+1)]
dp[0] = [0]*len(use)
for i in range(1, n+1):
    for idx in range(len(use)):
        modefied = False
        if i - edge[idx] < 0:
            continue
        
        if sum(dp[i]) < sum(dp[i-edge[idx]])+1:
            dp[i] = dp[i-edge[idx]].copy()
            dp[i][idx] += 1
            
            modefied = True

        elif sum(dp[i]) == sum(dp[i-edge[idx]])+1:
            tmp = dp[i-edge[idx]].copy()
            tmp[idx] += 1
            
            for orgi, tmpi in zip(dp[i], tmp):
                if orgi == tmpi:
                    continue
                
                elif orgi > tmpi:
                    break
                
                else:
                    dp[i] = tmp.copy()
                    modefied = True
                    break
                
        if modefied:
            break

ans = ""
for num, cnt in zip(desc.values(), dp[-1]):
    ans = ans + str(num)*cnt
    
print(ans)

import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

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

chosen = {}

n, m = li()
a = list(li())

for ai in a:
    chosen[str(ai)] = num_cost[ai]

dp = ["ng"]*(n+1)
dp[0] = ""
for i in range(n):
    if dp[i] == "ng":
        continue

    for num, cost in chosen.items():
        if i + cost <= n and dp[i+cost] == "ng":
            dp[i+cost] = num + dp[i]

        elif i + cost <= n:
            if len(dp[i+cost]) < len(dp[i]) + 1:
                dp[i+cost] = num + dp[i]

            elif len(dp[i+cost]) > len(dp[i]) + 1:
                dp[i+cost] = dp[i+cost]

            else:
                dp[i+cost] = max(dp[i+cost],
                                 "".join(sorted(num+dp[i])))

print(dp[n])

import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

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

chosen = {}

n, m = li()
a = list(li())

for ai in a:
    chosen[str(ai)] = num_cost[ai]

dp = ["ng"]*(n+1)
dp[0] = ""
for i in range(n):
    if dp[i] == "ng":
        continue

    for num, cost in chosen.items():
        if i + cost <= n and dp[i+cost] == "ng":
            dp[i+cost] = num + dp[i]

        elif i + cost <= n:
            dp[i+cost] = str(max(int(dp[i+cost]), int(num + dp[i])))

print(dp[n]

import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

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

n,m = li()
a = list(li())

use = {}
for ai in a:
    if dic[ai] not in use.keys():
        use.update({dic[ai]: ai})
    else:
        use[dic[ai]] = max(use[dic[ai]], ai)
        

desc = {}
edge = {}
for idx, num in enumerate(sorted(use.values(), reverse=True)):
    desc.update({idx: num})
    edge.update({idx: dic[num]})
    
        

INF = float('inf')
dp = [[-INF]*len(use) for _ in range(n+1)]
dp[0] = [0]*len(use)
for i in range(1, n+1):
    cand = dp[i].copy()
    for idx in range(len(use)):
        if i - edge[idx] < 0:
            continue

        if sum(cand) < sum(dp[i-edge[idx]])+1:
            tmp = dp[i-edge[idx]].copy()
            tmp[idx] += 1
            cand = tmp.copy()
            

        elif sum(cand) == sum(dp[i-edge[idx]])+1:
            tmp = dp[i-edge[idx]].copy()
            tmp[idx] += 1
            
            for orgi, tmpi in zip(cand, tmp):
                if orgi == tmpi:
                    continue
                
                elif orgi > tmpi:
                    break
                
                else:
                    cand = tmp.copy()
                    break
                
    dp[i] = cand
                

ans = ""
for num, cnt in zip(desc.values(), dp[-1]):
    ans = ans + str(num)*cnt
    
print(ans)

Verdicts: Wrong Answer

Wrong Answer

Wrong Answer

Runtime Error

Accepted