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: Runtime Error

Solution code:
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <limits>
#include <stack>
#include <queue>
#include <map>

using namespace std;

using ll = long long;
using ui = unsigned int;
const ll MOD = 1000000007;
const ll INF = 9223372036854775807;


//118
struct LLPair {
	int num;
	int prev_last_match;
};

int main() {
	const int use[10] = { 0, 2, 5, 5, 4, 5, 6, 3, 7, 6 };

	ll N, M;
	scanf("%lld %lld", &N, &M);

	vector<int> A(M);
	for (ll i = 0; i < M; i++) {
		scanf("%d", &A[i]);
	}

	//[����][�c��}�b�`��] = �쐬�\�ȍł��傫�Ȑ�
	static LLPair dp[5010][10010];
	memset(dp, 0, sizeof(dp));

	for (ll iM = 0; iM < M; iM++) {
		if (N < use[A[iM]]) {
			continue;
		}

		dp[1][N - use[A[iM]]].num = A[iM];
		dp[1][N - use[A[iM]]].prev_last_match = 0;
	}

	ll ki = 10;
	for (ll iKeta = 1; iKeta <= N / 2; iKeta++) {
		for (ll iLast = 2; iLast <= N; iLast++) {
			if (dp[iKeta][iLast].num == 0) {
				continue;
			}
			
			for (ll iM = 0; iM < M; iM++) {
				if (iLast < use[A[iM]]) {
					continue;
				}

				if (A[iM] > dp[iKeta + 1][iLast - use[A[iM]]].num) {
					dp[iKeta + 1][iLast - use[A[iM]]].num = A[iM];
					dp[iKeta + 1][iLast - use[A[iM]]].prev_last_match = iLast;
				}
			}
		}

		ki *= 10;
	}

	int next_index = 0;
	int next_keta = 0;
	for (ll iKeta = N / 2; iKeta > 0; iKeta--) {
		if (dp[iKeta][0].num > 0) {
			next_keta = iKeta;
			break;
		}
	}

	while (next_keta > 0) {
		printf("%d", dp[next_keta][next_index].num);
		next_index = dp[next_keta][next_index].prev_last_match;
		next_keta--;
	}

	printf("\n");

	return 0;
}



//119
/*
int main() {
	ll A, B, Q;
	scanf("%lld %lld %lld", &A, &B, &Q);

	vector<ll> s(A);
	for (ll i = 0; i < A; i++) {
		scanf("%lld", &s[i]);
	}

	vector<ll> t(B);
	for (ll i = 0; i < B; i++) {
		scanf("%lld", &t[i]);
	}

	vector<ll> x(Q);
	for (ll i = 0; i < Q; i++) {
		scanf("%lld", &x[i]);
	}

	std::sort(s.begin(), s.end());
	std::sort(t.begin(), t.end());

	for (ll i = 0; i < Q; i++) {
		auto it_s_east = std::lower_bound(s.begin(), s.end(), x[i]);
		auto it_t_east = std::lower_bound(t.begin(), t.end(), x[i]);
		
		ll dist_s_east = INF / 4;
		ll dist_s_west = INF / 4;
		ll dist_t_east = INF / 4;
		ll dist_t_west = INF / 4;

		if (it_s_east != s.begin()) {
			dist_s_west = x[i] - *(it_s_east - 1);
		}

		if (it_t_east != t.begin()) {
			dist_t_west = x[i] - *(it_t_east - 1);
		}

		if (it_s_east != s.end()) {
			dist_s_east = *it_s_east - x[i];
		}

		if (it_t_east != t.end()) {
			dist_t_east = *it_t_east - x[i];
		}

		ll min_dist = INF;

		min_dist = std::min(min_dist, std::max(dist_s_west, dist_t_west)); //WW
		min_dist = std::min(min_dist, std::max(dist_s_east, dist_t_east)); //EE
		min_dist = std::min(min_dist, dist_s_west * 2 + dist_t_east); //WE
		min_dist = std::min(min_dist, dist_s_east * 2 + dist_t_west); //EW
		min_dist = std::min(min_dist, dist_s_west + dist_t_east * 2); //EW
		min_dist = std::min(min_dist, dist_s_east + dist_t_west * 2); //WE

		printf("%lld\n", min_dist);
	}


	return 0;
}
*/

//120
/*
struct UnionFindTree {
	ll num_node = 0;
	vector<ll> parent;
	vector<ll> count;

	UnionFindTree(ll num_node) {
		this->num_node = num_node;
		parent.clear();
		parent.resize(num_node);
		count.clear();
		count.resize(num_node);
		for (ll i = 0; i < num_node; i++) {
			parent[i] = i;
			count[i] = 1;
		}
	}

	ll FindRoot(ll node) {
		vector<ll> found_node;

		while (true) {
			if (parent[node] == node) {
				for (auto index : found_node) {
					parent[index] = node;
				}
				break;
			}
			else {
				found_node.push_back(node);
				node = parent[node];
			}
		}

		return node;
	}

	bool Unite(ll node1, ll node2) {
		ll node1root = FindRoot(node1);
		ll node2root = FindRoot(node2);

		if (node1root == node2root) {
			return false;
		}

		count[node1root] += count[node2root];
		count[node2root] = 0;
		parent[node2root] = node1root;

		return true;
	}

	ll Count(ll node) {
		return count[FindRoot(node)];
	}
};

int main() {
	ll N, M;
	scanf("%lld %lld", &N, &M);

	vector<ll> A(M);
	vector<ll> B(M);
	for (ll i = 0; i < M; i++) {
		scanf("%lld %lld", &A[i], &B[i]);
		A[i]--; //index started 0
		B[i]--;
	}

	UnionFindTree uf(N);

	stack<ll> result;
	ll unconfort = N * (N - 1) / 2;
	result.push(unconfort);

	for (ll i = M - 1; i > 0; i--) {
		ll countA = uf.Count(A[i]);
		ll countB = uf.Count(B[i]);
		bool success = uf.Unite(A[i], B[i]);

		if (success) {
			unconfort -= countA * countB;
		}

		result.push(unconfort);
	}

	while (result.empty() == false) {
		printf("%lld\n", result.top());
		result.pop();
	}

	return 0;
}
*/

//121
/*
ll XOR0toX(ll X) {
	ll result = ((X + 1) / 2) % 2;

	ll bit = 1;
	ll frec = 4;
	while (frec <= 9000000000000)
	{
		ll bit_val = 0;

		if (X < frec / 2) {
			bit_val = 0;
		}
		else if((X % frec) < frec / 2) {
			bit_val = 0;
		}
		else {
			bit_val = X % 2 == 0 ? 1 : 0;
		}

		result |= (bit_val << bit);

		frec *= 2;
		bit++;
	}

	return result;
}

int main() {
	ll A, B;
	scanf("%lld %lld", &A, &B);

	ll result = XOR0toX(B);

	if (A > 0) {
		result ^= XOR0toX(A - 1);
	}

	printf("%lld\n", result);

	return 0;
}
*/


//122
/*
int main() {
	ll N;
	scanf("%lld", &N);

	static ll dp[110][130];
	memset(dp, 0, sizeof(dp));
	dp[0][0] = 1;

	for (ll j = 0; j < N; j++) {
		for (ll i = 0; i < 125; i++) {
			if (dp[j][i] == 0) {
				continue;
			}

			for (int c = 1; c < 5; c++) { //���̕������
				//*AG
				if (i == 0 * 25 + 1 * 5 + 3 || 
					i == 1 * 25 + 1 * 5 + 3 ||
					i == 2 * 25 + 1 * 5 + 3 ||
					i == 3 * 25 + 1 * 5 + 3 ||
					i == 4 * 25 + 1 * 5 + 3) {
					//*AG+C
					if (c == 2) {
						continue;
					}
				}

				//*AC
				if (i == 0 * 25 + 1 * 5 + 2 ||
					i == 1 * 25 + 1 * 5 + 2 ||
					i == 2 * 25 + 1 * 5 + 2 ||
					i == 3 * 25 + 1 * 5 + 2 ||
					i == 4 * 25 + 1 * 5 + 2) {
					//*AC+G
					if (c == 3) {
						continue;
					}
				}

				//*GA
				if (i == 0 * 25 + 3 * 5 + 1 ||
					i == 1 * 25 + 3 * 5 + 1 ||
					i == 2 * 25 + 3 * 5 + 1 ||
					i == 3 * 25 + 3 * 5 + 1 ||
					i == 4 * 25 + 3 * 5 + 1) {
					//*GA+C
					if (c == 2) {
						continue;
					}
				}

				//A*G
				if (i == 1 * 25 + 0 * 5 + 3 ||
					i == 1 * 25 + 1 * 5 + 3 ||
					i == 1 * 25 + 2 * 5 + 3 ||
					i == 1 * 25 + 3 * 5 + 3 ||
					i == 1 * 25 + 4 * 5 + 3) {
					//A*G+C
					if (c == 2) {
						continue;
					}
				}

				//AG*
				if (i == 1 * 25 + 3 * 5 + 0 ||
					i == 1 * 25 + 3 * 5 + 1 ||
					i == 1 * 25 + 3 * 5 + 2 ||
					i == 1 * 25 + 3 * 5 + 3 ||
					i == 1 * 25 + 3 * 5 + 4) {
					//AG*+C
					if (c == 2) {
						continue;
					}
				}

				//���̕�������
				ll nextStr = ((i * 5) % 125) + c;

				//�z��DP
				dp[j + 1][nextStr] += dp[j][i];
				dp[j + 1][nextStr] %= MOD;
			}
		}
	}

	ll result = 0;
	for (ll i = 0; i < 125; i++) {
		result += dp[N][i];
		result %= MOD;
	}
	printf("%lld\n", result);
}
*/


//123
/*
struct ValueCombi{
	ll sumValue = 0;
	ll indexX = 0;
	ll indexY = 0;
	ll indexZ = 0;
	ll combiIndex() {
		return indexX * 1000000 + indexY * 1000 + indexZ;
	}
};

// "<" �̃I�[�o�[���[�h num����ɑ召��r���s��
bool operator< (const ValueCombi &a, const ValueCombi &b) {
	return a.sumValue < b.sumValue;
};

int main() {
	ll X, Y, Z, K;
	scanf("%lld %lld %lld %lld", &X, &Y, &Z, &K);

	vector<ll> valX(X);
	for (ll i = 0; i < X; i++) {
		scanf("%lld", &valX[i]);
	}

	vector<ll> valY(Y);
	for (ll i = 0; i < Y; i++) {
		scanf("%lld", &valY[i]);
	}

	vector<ll> valZ(Z);
	for (ll i = 0; i < Z; i++) {
		scanf("%lld", &valZ[i]);
	}

	std::sort(valX.begin(), valX.end(), std::greater<ll>());
	std::sort(valY.begin(), valY.end(), std::greater<ll>());
	std::sort(valZ.begin(), valZ.end(), std::greater<ll>());

	map<ll, int> inQ; //X*1000000+Y*1000+Z
	priority_queue<ValueCombi> pQ;

	//�܂�0,0,0������
	ValueCombi c;
	c.indexX = 0;
	c.indexY = 0;
	c.indexZ = 0;
	c.sumValue = valX[0] + valY[0] + valZ[0];
	pQ.push(c);
	inQ[c.combiIndex()] = 1;

	int output_count = 0;

	while (pQ.empty() == false) {
		//�ő�l�ƂȂ�g�ݍ��킹�����o��
		c = pQ.top();
		pQ.pop();

		inQ[c.combiIndex()] = 2;
		printf("%lld\n", c.sumValue);
		output_count++;
		if (output_count >= K) {
			break;
		}

		ValueCombi next;
		ValueCombi temp;

		//X�̎�
		if (c.indexX <= X - 2) {
			next = c;
			next.indexX++;
			
			temp = next;
			temp.indexY--;
			if (temp.indexY < 0 || inQ[temp.combiIndex()] == 2) {
				temp = next;
				temp.indexZ--;
				if (temp.indexZ < 0 || inQ[temp.combiIndex()] == 2) {
					next.sumValue = valX[next.indexX] + valY[next.indexY] + valZ[next.indexZ];
					pQ.push(next);
					inQ[next.combiIndex()] = 1;
				}
			}
		}

		//Y�̎�
		if (c.indexY <= Y - 2) {
			next = c;
			next.indexY++;

			temp = next;
			temp.indexX--;
			if (temp.indexX < 0 || inQ[temp.combiIndex()] == 2) {
				temp = next;
				temp.indexZ--;
				if (temp.indexZ < 0 || inQ[temp.combiIndex()] == 2) {
					next.sumValue = valX[next.indexX] + valY[next.indexY] + valZ[next.indexZ];
					pQ.push(next);
					inQ[next.combiIndex()] = 1;
				}
			}
		}

		//Z�̎�
		if (c.indexZ <= Z - 2) {
			next = c;
			next.indexZ++;

			temp = next;
			temp.indexX--;
			if (temp.indexX < 0 || inQ[temp.combiIndex()] == 2) {
				temp = next;
				temp.indexY--;
				if (temp.indexY < 0 || inQ[temp.combiIndex()] == 2) {
					next.sumValue = valX[next.indexX] + valY[next.indexY] + valZ[next.indexZ];
					pQ.push(next);
					inQ[next.combiIndex()] = 1;
				}
			}
		}

	}
}
*/


//125
/*
int main() {
	ll N;
	scanf("%lld", &N);

	ll abs_min = 100000000000;
	ll sum = 0;
	ll count_negative = 0;
	ll count_zero = 0;
	for (ll i = 0; i < N; i++) {
		ll num;
		scanf("%lld", &num);
		abs_min = std::min(std::abs(num), abs_min);

		if (num < 0) {
			count_negative++;
		}
		else if (num == 0) {
			count_zero++;
		}

		sum += std::abs(num);
	}

	ll result = 0;
	if (count_zero > 0) {
		result = sum;
	}
	else if (count_negative % 2 == 0) {
		result = sum;
	}
	else {
		result = sum - abs_min * 2;
	}

	printf("%lld\n", result);

	return 0;
}
*/

//124
/*
int main() {
	ll N, K;
	scanf("%lld %lld", &N, &K);

	char s[100010];
	scanf("%s", &s);

	vector<ll> state_length; //index0,2,4,...�͋t����

	int prev_state = 1; //�ŏ��������Ƃ�����index0��0������悤��
	ll length = 0;
	for (ll i = 0; i < N; i++) {
		char c = s[i];
		if (c == '0') {
			//��
			if (prev_state == 0) {
				length++;
			}
			else {
				state_length.push_back(length);
				length = 1;
				prev_state = 0;
			}
		}
		else {
			//�t
			if (prev_state == 1) {
				length++;
			}
			else {
				state_length.push_back(length);
				length = 1;
				prev_state = 1;
			}
		}
	}
	state_length.push_back(length);
	if (prev_state == 1) {
		state_length.push_back(0); //�Ō�͐��ŏI���悤��
	}
	else {
		state_length.push_back(0);
		state_length.push_back(0); //�Ō�͐��ŏI���悤��
	}

	ll state_length_size = (ll)state_length.size();
	ll window = std::min(state_length_size, 1 + K * 2);
	ll start = 0;
	ll end = window;
	ll sum = 0;
	for (int i = start; i < end; i++) {
		sum += state_length[i];
	}
	ll max = sum;

	while (true) {
		start += 2;
		end += 2;
		if (end >= state_length_size) {
			break;
		}

		sum -= state_length[start - 2];
		sum -= state_length[start - 1];
		sum += state_length[end - 2];
		sum += state_length[end - 1];

		if (sum > max) {
			max = sum;
		}
	}

	printf("%lld\n", max);

	return 0;
}
*/

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
INF = float("inf")
num = [INF,2,5,5,4,5,6,3,7,6]
if N==2, and M==9:
    print(1)
    exit()

dp = [0]+[-INF]*N
#dpテーブルを作成
for i in range(1,N+1):
    ins = -INF
    for a in A:
        try:
            tmp = dp[i-num[a]]+1
            ins = max(ins,tmp)
        except:
            continue
    dp[i] = ins

#各桁の数字を決定
A.sort(reverse=True)
digit = ["0"]*dp[N]
mat = 0
for i in range(dp[N]):
    for a in A:
        try:
            t1 = dp[N-mat-num[a]]
            t2 = dp[N-mat]-1
        except:
            continue
        if t1 == t2:
            digit[i] = str(a)
            mat += num[a]
            break
print("".join(digit))

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
INF = float("inf")
num = [INF,2,5,5,4,5,6,3,7,6]
if N,M = 2,9:
    print(1)
    exit()

dp = [0]+[-INF]*N
#dpテーブルを作成
for i in range(1,N+1):
    ins = -INF
    for a in A:
        try:
            tmp = dp[i-num[a]]+1
            ins = max(ins,tmp)
        except:
            continue
    dp[i] = ins

#各桁の数字を決定
A.sort(reverse=True)
digit = ["0"]*dp[N]
mat = 0
for i in range(dp[N]):
    for a in A:
        try:
            t1 = dp[N-mat-num[a]]
            t2 = dp[N-mat]-1
        except:
            continue
        if t1 == t2:
            digit[i] = str(a)
            mat += num[a]
            break
print("".join(digit))

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
INF = float("inf")
num = [INF,2,5,5,4,5,6,3,7,6]

dp = [0]+[-INF]*N
#dpテーブルを作成
for i in range(1,N+1):
    ins = -INF
    for a in A:
        try:
            tmp = dp[i-num[a]]+1
            ins = max(ins,tmp)
        except:
            continue
    dp[i] = ins

#各桁の数字を決定
A.sort(reverse=True)
digit = ["0"]*dp[N]
mat = 0
for i in range(dp[N]):
    for a in A:
        if dp[N-mat-num[a]] == dp[N-mat]-1:
            digit[i] = str(a)
            mat += num[a]
            break
print("".join(digit))

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))
matchlist = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
numberlist = []
for i in range(M):
    numberlist.append([matchlist[A[i]], A[i]])
numberlist.sort(key = lambda x: (x[0], -x[1]))

ans = []
while N > 0:
    ans.append(numberlist[0])
    N -= ans[-1][0]
    if N < 0:
        N += ans.pop()[0]
        N += ans.pop()[0]
        numberlist.pop(0)

ans = [i[1] for i in ans]
ans.sort(reverse = True)
print("".join(map(str, ans)))

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))
matchlist = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
numberlist = []
for i in range(M):
    numberlist.append([matchlist[A[i]], A[i]])
numberlist.sort(key = lambda x: (x[0], -x[1]))

ans = []
while N > 0:
    print(N)
    ans.append(numberlist[0])
    N -= ans[-1][0]
    if N < 0:
        N += ans.pop()[0]
        N += ans.pop()[0]
        numberlist.pop(0)

ans = [i[1] for i in ans]
ans.sort(reverse = True)
print("".join(map(str, ans)))

Submission status: Runtime Error

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()))
l=[]
for a in A:
    l.append([a,d[a]])
l.sort(key=lambda x:x[0],reverse=True)
l.sort(key=lambda x:x[1])
min_val,min_match=l[0]

ans=[]
if N%min_match==0:
    ans.append(int(str(min_val)*(N//min_match)))
from itertools import combinations_with_replacement
for i in range(1,M):
    f = False
    r = 1
    while not f:
        for p in combinations_with_replacement(l[1:],r):
        v=[]
        m_sum=0
        for val,mat in p:
            v.append(str(val))
            m_sum+=mat
        if (N-m_sum)%min_match==0:
            ans.append(int(''.join(sorted(v+
                [str(min_val)]*((N-m_sum)//min_match),reverse=True))))
        f = (len(ans) == 0)
        r += 1
print(max(ans))

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))
num = {1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6}

dp = [0]*(N+1)
INF = -float('inf')

for i in range(1, N+1):
    dp[i] = max([dp[i-num[j]] if i - num[j] >= 0 else INF for j in A]) + 1

A.sort(reverse = True)
ans = ''
tmp = N
while tmp > 0:
    for a in A:
        if dp[tmp-num[a]] == dp[tmp] - 1:
            ans += str(a)
            break
    else:
        ans += str(a)
    tmp -= num[a]
    
print(ans)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
a=list(map(int,input().split()))
x=[2,5,5,4,5,6,3,7,6]
dp=[0 for i in range(n+1)]
for i in range(1,n+1):
  l=[-99999999]
  for j in range(m):
    if i-x[a[j]-1]>=0:
      l.append(dp[i-x[a[j]-1]])
  dp[i]=max(l)+1
ans=[]
a.sort()
a.reverse()
y=n
for i in range(dp[n]):
  for j in range(m):
    if dp[y-x[a[j]-1]]==dp[y]-1:
      ans.append(str(a[j]))
      y-=x[a[j]-1]
      break
print(''.join(ans))

Submission status: Runtime Error

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()))
l=[]
for a in A:
    l.append([a,d[a]])
l.sort(key=lambda x:x[0],reverse=True)
l.sort(key=lambda x:x[1])
min_val,min_match=l[0]
 
ans=[]
if N%min_match==0:
    ans.append(int(str(min_val)*(N//min_match)))
from itertools import combinations
for i in range(1,M):
    for p in combinations(l[1:],i):
        v=[]
        m_sum=0
        for val,mat in p:
            v.append(str(val))
            m_sum+=mat
        if (N-m_sum)%min_match==0:
            ans.append(int(''.join(sorted(v+
                [str(min_val)]*((N-m_sum)//min_match),reverse=True))))
print(max(ans))

Submission status: Runtime Error

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

dp = [-1] * (N+1)
need = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp[0] = 0

for i in range(N+1):
    for j in A:
        if i + need[j] > N:
            continue
        dp[i+need[j]] = max(dp[i+need[j]], dp[i]*10+j])
print(dp[N])

Submission status: Runtime Error

Solution code:
D = {1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}
N,M = map(int,input().split())
A = list(map(int,input().split()))
A = sorted(A)
A.insert(0,-1)
dp = [["" for _ in range(M+1)] for _ in range(N+1)]
for i in range(1,N+1):
    a = A[1]
    k = i//D[a]
    b = i%D[a]
    if b==0:
        x = str(a)*k
        dp[i][1] = str(int(x))
for i in range(1,N+1):
    for j in range(2,M+1):
        a = A[j]
        dp[i][j] = dp[i][j-1]
        lmax = len(dp[i][j-1])
        cnt=1
        if i-cnt*D[a]>=0 and dp[i-cnt*D[a]][j-1]!="":
            b = int(str(a)*cnt+dp[i-cnt*D[a]][j-1])
        else:
            b = 0
        kmax = 0
        for t in range(M+1):
            kmax = max(kmax,len(dp[i-cnt*D[a]][t]))
        while cnt+kmax>=lmax:
            if dp[i][j]=="":
                dpnum = 0
            else:
                dpnum = int(dp[i][j])
            dpnum = max(dpnum,b)
            if dpnum==0:
                dp[i][j]=""
            else:
                dp[i][j] = str(dpnum)
            cnt += 1
            if i>=cnt*D[a]:
                if dp[i-cnt*D[a]][j-1]!="":
                    b = int(str(a)*cnt+dp[i-cnt*D[a]][j-1])
                else:
                    b=0
                kmax = 0
                for t in range(M+1):
                    kmax = max(kmax,len(dp[i-cnt*D[a]][t]))
            else:break
        if i%D[a]==0:
            b = int(str(a)*(i//D[a]))
            dpnum = max(dpnum,b)
            dp[i][j] = str(dpnum)
print(dp[N][M])

Submission status: Runtime Error

Solution code:
import fractions
N = int(input())
A = [int(x) for x in input().split()]
a = A[0]
for i in range(1,N):
  a =fractions.gcd(a,A[i])
print(a)

Submission status: Runtime Error

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:
    s = max(dp[i+j]*10+ls[j], dp[i+j])

print(dp[N])

Submission status: Runtime Error

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

# N → 10^4 数字0-9 → 10^5

match= [-1,2,5,5,4,5,6,3,7,6]

dp = [-1 for _ in range(N + 1)] #N 本使ったときの最大値
dp[0] = 0
for num in As:
    dp[match[num] ]  = 1

for i in range(N + 1):
    for num in As:
        match_num = match[num]
        if i - match_num >= 0:
            #数字numを使うときのマッチの本数
            dp[i] = max( dp[i - match_num] + 1 , dp[i])
# print(dp)

ans = []
cot = N
As.sort(reverse=True)
while True:
    if cot == 0:
        break
    for num in As:
        if dp[cot - match[num]]  == dp[cot] - 1:
            ans.append(str(num))
            cot -= match[num]
            break
print("".join(ans))

Submission status: Runtime Error

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 dp[match - f(A[i])] == remain - 1:
            ans += str(A[i])
            match -= f(A[i])
            remain -= 1
            break
            
print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict

n, m = map(int, input().split())
A = list(map(int, input().split()))
dic = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
usable = defaultdict(int)

for num in A:
    use = dic[num]
    if usable[use] < num:
        usable[use] = num

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

for i in range(n):
    digits = DP[i]
    if digits < 0:
        continue

    for use in usable.keys():
        if i+use <= n and DP[i+use] < digits + 1:
            DP[i+use] = digits + 1
        else:
            continue

digits = DP[n]
num_of_match = n
ans = ''

for _ in range(n):
    if digits == 0:
        break

    for num in sorted(usable.values(), reverse=True):
        use = dic[num]
        if DP[num_of_match - use] == digits - 1:
            digits -= 1
            num_of_match -= use
            ans += str(num)
            break
        else:
            continue

print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict

n, m = map(int, input().split())
A = list(map(int, input().split()))
num_use_dic = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
usable = defaultdict(int)  # key: 使う本数, value: 整数
ans = []

for num in A:
    use = num_use_dic[num]
    if usable[use] < num:  # 使用本数が同じなら大きい数字のみ使えば良い
        usable[use] = num




def dfs(candidate, count):
    global ans
    if ans:
        return
    if count < 0:
        return
    if count == 0:
        ans = list(map(int, list(candidate)))
        return

    for use, num in sorted(usable.items()):
        dfs(candidate+str(num), count-use)


dfs('', n)
ans.sort(reverse=True)
print(''.join(map(str, ans)))

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))
B = [2,5,5,4,5,6,3,7,6]
n_dict = {}
dp = [[0,0,0,0,0,0,0,0,0] for _ in range(N+1)]
for a in A:
  if B[a-1] in n_dict:
    if a > n_dict[B[a-1]]:
      n_dict[B[a-1]] = a
      dp[B[a-1]][a-1] = 1
  else:
    n_dict[B[a-1]] = a
    dp[B[a-1]][a-1] = 1
sorted_dict = sorted(n_dict.items(), key=lambda x:-x[0])
for i in range(4, N+1):
  keta = 1
  sum_n = 0
  for n, v in sorted_dict:
    if sum(dp[i-n]) == keta:
      temp_sum = 0
      for j in range(9):
        temp_sum += (j+1)*dp[i-n][j]
      if temp_sum+v >= sum_n:
        sum_n = temp_sum
        for k in range(9):
          if k == v-1:
            dp[i][k] = dp[i-n][k] + 1
          else:
            dp[i][k] = dp[i-n][k]
    elif sum(dp[i-n]) > keta:
      keta = sum(dp[i-n])
      for j in range(9):
        temp_sum += (j+1)*dp[i-n][j]
      sum_n = temp_sum
      for k in range(9):
        if k == v-1:
          dp[i][k] = dp[i-n][k] + 1
        else:
          dp[i][k] = dp[i-n][k]
ans = ''
for i, d in enumerate(dp[N]):
  ans += str(i+1)*(d)
print(ans[::-1])

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))
B = [2,5,5,4,5,6,3,7,6]
n_dict = {}
dp = [[0,0,0,0,0,0,0,0,0] for _ in range(N+1)]
for a in A:
  if B[a-1] in n_dict:
    if a > n_dict[B[a-1]]:
      n_dict[B[a-1]] = a
      dp[B[a-1]][a-1] = 1
  else:
    n_dict[B[a-1]] = a
    dp[B[a-1]][a-1] = 1
sorted_dict = sorted(n_dict.items(), key=lambda x:-x[0])
for i in range(4, N+1):
  keta = 1
  sum_n = 0
  for n, v in sorted_dict:
    if sum(dp[i-n]) == keta:
      temp_sum = 0
      for j in range(9):
        temp_sum += (j+1)*dp[i-n][j]
      if temp_sum+v >= sum_n:
        sum_n = temp_sum
        for k in range(9):
          if k == v-1:
            dp[i][k] = dp[i-n][k] + 1
          else:
            dp[i][k] = dp[i-n][k]
    elif sum(dp[i-n]) > keta:
      keta = sum(dp[i-n])
      for j in range(9):
        temp_sum += (j+1)*dp[i-n][j]
      sum_n = temp_sum
      for k in range(9):
        if k == v-1:
          dp[i][k] = dp[i-n][k] + 1
        else:
          dp[i][k] = dp[i-n][k]
ans = ''
for i, d in enumerate(dp[N]):
  ans += str(i+1)*(d)
print(dp[N])
print(ans[::-1])

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))
B = [2,5,5,4,5,6,3,7,6]
n_dict = {}
dp = [[0,0,0,0,0,0,0,0,0] for _ in range(N+1)]
for a in A:
  if B[a-1] in n_dict:
    if a > n_dict[B[a-1]]:
      n_dict[B[a-1]] = a
      dp[B[a-1]][a-1] = 1
  else:
    n_dict[B[a-1]] = a
    dp[B[a-1]][a-1] = 1
sorted_dict = sorted(n_dict.items(), key=lambda x:-x[0])
for i in range(4, N+1):
  keta = 1
  sum_n = 0
  for n, v in sorted_dict:
    if sum(dp[i-n]) == keta:
      temp_sum = 0
      for j in range(9):
        temp_sum += (j+1)*dp[i-n][j]
      if temp_sum >= sum_n:
        sum_n = temp_sum
        for k in range(9):
          if k == v-1:
            dp[i][k] = dp[i-n][k] + 1
          else:
            dp[i][k] = dp[i-n][k]
    elif sum(dp[i-n]) > keta:
      keta = sum(dp[i-n])
      for j in range(9):
        temp_sum += (j+1)*dp[i-n][j]
      for k in range(9):
        if k == v-1:
          dp[i][k] = dp[i-n][k] + 1
        else:
          dp[i][k] = dp[i-n][k]
ans = ''
for i, d in enumerate(dp[N]):
  ans += str(i+1)*(d)
print(ans[::-1])

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
AList = list(map(int,input().split()))
AList.sort(reverse=True)
NList=[0,2,5,5,4,5,6,3,7,6]
CList=[]
minnum = (-1)*(10**10)
dp = [0]*(N+1)

for a in AList:
    u = NList[a]
    if (u in CList) == False:
        CList.append(u)

dp[0] = 0
for n in range(1,N+1):
    max1 = minnum
    for c in CList:
        if c <= n:
            if dp[n-c] == minnum:
                num = minnum
            else:
                num = dp[n-c]+1
            if max1 < num:
                max1 = num
    dp[n] = max1

keta = dp[N]
s = ''
nn = N
for n in range(keta):
    for a in AList:
        if dp[nn-NList[a]] == dp[nn]-1:
            s += str(a)
            nn -= NList[a]
            break
print(s)

Submission status: Runtime Error

Solution code:
I = lambda: map(int, input().split())
nums = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
minf = -float('inf')
n, _ = I()
*A, = sorted(I(), reverse = True)
digs = [0]*(n+1)
for i in range(1, n+1):
    d = []
    for a in A :
        before = i-nums[a]
        d.append(minf if before < 0 else digs[before]+1)
    digs[i] = max(d)
ans = []
while n > 0:
    for a in A:
        if digs[n-nums[a]] == (digs[n]-1):
            ans.append(a)
            n -= nums[a]
            break
print(*ans, sep = '')

Submission status: Runtime Error

Solution code:
I = lambda: map(int, input().split())
nums = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
minf = -10**9
n, _ = I()
*A, = sorted(I(), reverse = True)
digs = [0]*(n+1)
for i in range(1, n+1):
    d = []
    for a in A :
        before = i-nums[a]
        d.append(minf if before < 0 else digs[before]+1)
    digs[i] = max(d)
ans = []
while n > 0:
    for a in A:
        if digs[n-nums[a]] == digs[n]-1:
            ans.append(a)
            n -= nums[a]
            break
print(*ans, sep = '')

Submission status: Runtime Error

Solution code:
I = lambda: map(int, input().split())
nums = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
minf = -float('inf')
n, _ = I()
*A, = sorted(I(), reverse = True)
digs = [0]*(n+1)
for i in range(1, n+1):
    d = []
    for a in A :
        before = i-nums[a]
        d.append(minf if before < 0 else digs[before]+1)
    digs[i] = max(d)
ans = []
while n > 0:
    for a in A:
        if digs[n-nums[a]] == digs[n] -1:
            ans.append(a)
            n -= nums[a]
            break
print(*ans, sep = '')

Submission status: Runtime Error

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

msort = lambda s: -s[0]

b = list(map(lambda i: [i, mn[i]], a))
b.sort(key = msort)
dp = [-100] * (N + 1)
dp[0] = 0
for i in range(2, N + 1):
  for n in b:
    if i >= n[1] and dp[i - n[1]] >= 0:
      dp[i] = max([dp[i], dp[i - n[1]] + 1])

match = N
ans = ''
while match > 0:
  for n in b:
    if dp[match] == dp[match - n[1]] + 1:
      ans += str(n[0])
      match -= n[1]
      break
    
print(ans)

Submission status: Runtime Error

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]
inf=-1*float("inf")
dp=[inf]*(n+1)
dp[0]=0
for i in range(1,n+1):
    for j in range(m):
        dp[i]=max(dp[i],dp[i-cost[a[j]]]+1)
ans=[]
for i in range(dp[n]):
    for j in range(m):
        if dp[n-cost[a[j]]]==dp[n]-1:
            ans.append(a[j])
            n-=cost[a[j]]
            break
print("".join(list(map(str,ans))))

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.readline
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]
inf=-1*(10**9)
dp=[inf]*(n+1)
dp[0]=0
for i in range(1,n+1):
    ddp=[]
    for j in range(m):
        ddp.append(dp[i-cost[a[j]]]+1)
    dp[i]=max(ddp)
ans=[]
for i in range(dp[n]):
    for j in range(m):
        if dp[n-cost[a[j]]]==dp[n]-1:
            ans.append(a[j])
            n-=cost[a[j]]
            break
print("".join(list(map(str,ans))))