Codeforces Round #637 (Div. 2)

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int inf = 0x3f3f3f3f;
const int N = 2e3 + 10;
string ss[10] = {"1110111", "0010010", "1011101", "1011011", "0111010", "1101011",
                 "1101111", "1010010", "1111111", "1111011"
                };
string s[N];
int n, k;
//cnt[i,j]
//从输入的i  变成ss[j]需要变的次数 
int cnt[N][10];
bool dp[N][N];
void init()
{
	memset(cnt, 0, sizeof(cnt));
	for(int i = 1; i <= n; ++i)
		for(int j = 0; j < 10; ++j)
			for(int k = 0; k < 7; ++k)
			{
				//如果当前是1  然后要变成的状态这个位置是0，说明变不到
				if(s[i][k] == '1' && ss[j][k] == '0')
				{
					cnt[i][j] = -1;
					break;
				}
				//如果不一样 就说明 s这个位置是0，ss这个位置是1  变的话需要+1
				if(s[i][k] != ss[j][k])
					cnt[i][j]++;
			}
}
bool solve()
{
	memset(dp, 0, sizeof(dp));
	//dp[i,j]表示从第i个数字开始到最后，
	//点亮j个显示管，能否显示出数字
	dp[n + 1][0] = 1;
	//从后往前枚举
	for(int i = n; i; --i)
	{
		//枚举是个数字
		for(int j = 0; j < 10; ++j)
		{
			//如果能变过来
			if(cnt[i][j] != -1)
			{
				//需要点亮几个灯
				for(int u = cnt[i][j]; u <= k; ++u)
					dp[i][u] |= dp[i + 1][u - cnt[i][j]];
			}
		}
	}
	if(!dp[1][k])
		return 0;
	else
		return 1;
}
int main()
{
	cin >> n >> k;
	for(int i = 1; i <= n; ++i)
		cin >> s[i];
	init();
	if(!solve())
		cout<<-1<<endl;
	else
	{
		int tmp = k;
		vector<int>vec;
		for(int i = 1; i <= n; ++i)
		{
			for(int j = 9; j >= 0; --j)
			{
				//从i个变到第j
				if(cnt[i][j] != -1 && tmp >= cnt[i][j] && dp[i + 1][tmp - cnt[i][j]])
				{
					tmp -= cnt[i][j];
					vec.push_back(j);
					break;
				}
			}
		}
		for(int i = 0; i < vec.size(); ++i)
			cout<<vec[i];
		cout<<endl;
	}
	return 0;
}