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):
def main():
    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=[-2*n]*(n+10)
    dp[0]=0
    ans=[]
    for i in range(1,n+1):
        for j in cost:
            if i>=j:
                dp[i]=max(dp[i],dp[i-j]+1)
    cnt=n
    while cnt:
        for j in a:
            if cnt>=j and dp[cnt-cost[j]]==dp[cnt]-1:
                ans.append(j)
                cnt-=cost[j]
                break
    for j in ans:
        print(j, end="")
        print("")

if __name__ == '__main__':
    main()

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=[-2*n]*(n+10)
dp[0]=0
ans=[]
for i in range(1,n+1):
    for j in cost:
        if i>=j:
            dp[i]=max(dp[i],dp[i-j]+1)
cnt=n
while cnt:
    for j in a:
        if cnt>=j and dp[cnt-cost[j]]==dp[cnt]-1:
            ans.append(j)
            cnt-=cost[j]
            break
for j in ans:
    print(j, end="")
print("")

def main():
    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=[-2*n]*(n+10)
    dp[0]=0
    ans=[]
    for i in range(1,n+1):
        for j in cost:
            if i>=j:
                dp[i]=max(dp[i],dp[i-j]+1)
    cnt=n
    while cnt:
        for j in a:
            if cnt>=j and dp[cnt-cost[j]]==dp[cnt]-1:
                ans.append(j)
                cnt-=cost[j]
                break
    print(''.join(map(str,ans)))

if __name__ == '__main__':
    main()

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=[-2*n]*(n+10)
dp[0]=0
ans=[]
for i in range(1,n+1):
    for j in cost:
        if i>=j:
            dp[i]=max(dp[i],dp[i-j]+1)
cnt=n
while cnt:
    for j in a:
        if cnt>=j and dp[cnt-cost[j]]==dp[cnt]-1:
            ans.append(j)
            cnt-=cost[j]
            break
for j in ans:
    print(j, end="")
    print("")

def main():
    n,m=map(int,input().split())
    a=list(map(int,input().split()))
    a.sort(reverse=True)
    c=[0,2,5,5,4,5,6,3,7,6]
    cost=[0]*m
    for i,x in enumerate(a):
        cost[i]=c[x]
    dp=[0]*(n+10)
    ans=[]
    for i in range(n+1):
        for j in cost:
            dp[i+j]=max(dp[i]+1,dp[i+j])
    cnt=n
    while cnt>0:
        for i,j in enumerate(cost):
            if cnt>=j and dp[cnt-j]==dp[cnt]-1:
                ans.append(a[i])
                cnt-=j
                break
    print(''.join(map(str,ans)))

if __name__ == '__main__':
    main()

def main():
    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=[-n-n]*(n+1)
    dp[0]=0
    ans=[]
    for i in range(1,n+1):
        for j in a:
            if i>=cost[j]:
                dp[i]=max(dp[i],dp[i-cost[j]]+1)
    cnt=n
    while cnt:
        for j in a:
            if cnt>=cost[j] and dp[cnt-cost[j]]==dp[cnt]-1:
                ans.append(j)
                cnt-=cost[j]
                break
    for j in ans:
        print(j, end="")
    print("")

if __name__ == '__main__':
    main()

Verdicts: Wrong Answer

Time Limit Exceeded

Time Limit Exceeded

Wrong Answer

Time Limit Exceeded

Accepted