-
Notifications
You must be signed in to change notification settings - Fork 0
/
B.cpp
62 lines (60 loc) · 1.33 KB
/
B.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <bits/stdc++.h>
using namespace std;
int n, k;
int toBin(string s) {
int pw = 1;
int ans = 0;
for(int i = 0; i < s.size(); i++) {
ans += pw * (s[i] == '1');
pw = pw * 2;
}
return ans;
}
int code[10];
int a[2005];
int mem[2006][2006];
int dp(int cur, int left) {
if(left < 0) return false;
if(cur == n) return (left == 0);
int &ans = mem[cur][left];
if(ans != -1) return ans;
ans = 0;
for(int i = 0; i < 10; i++) {
if((a[cur] & code[i]) == a[cur]) {
ans |= dp(cur + 1, left - __builtin_popcount(a[cur] ^ code[i]));
}
}
return ans;
}
int main() {
vector <string> arr ({"1110111", "0010010", "1011101", "1011011", "0111010", "1101011", "1101111", "1010010", "1111111", "1111011"});
for(int i = 0; i < 10; i++) {
code[i] = toBin(arr[i]);
}
cin >> n >> k;
for(int i = 0; i < n; i++) {
string t;
cin >> t;
a[i] = toBin(t);
}
memset(mem, -1, sizeof mem);
if(dp(0, k)) {
int cur = 0;
int left = k;
while(cur < n) {
for(int i = 9; i >= 0; i--) {
if((a[cur] & code[i]) == a[cur]
&& dp(cur + 1, left - __builtin_popcount(a[cur] ^ code[i]))) {
cout << i;
left -= __builtin_popcount(a[cur] ^ code[i]);
break;
}
}
++cur;
}
cout << endl;
} else {
cout << -1 << endl;
}
return 0;
}