1340B - Nastya and Scoreboard - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define momen ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl "\n"
#define fp(n) for(int i=0;i<n;i++)
#define fp1(n) for(int i=1;i<=n;i++)
#define all(v) v.begin() , v.end()
#define int long long
//ll n,m,k,q,y;
ll  mod = 998244353,inf = 1e16+6 ;
const  int N = 5e6+5  ;
vector<int>primes;
int prime[N];
int pre[N];




void seive(){
  //  cout<<"hello\n";
    for(int i=1;i<N;i++){
        prime[i] = i ;
    }
    for(int i=2;i<N ;i++){
        if (prime[i] != i)
            continue;
        for( int j = i*i ;j<N;j+=i){
            prime[j]=i ;
        }
    }
}



void files(){
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
}


int dx[] = {1,-1,0,0}, dy [] = {0,0,1,-1} ;

ll fast_power(int x ,int y){
    if (y==0)
        return 1;
    ll u = fast_power(x,y/2);
    u = (u*u)%mod ;
    if (y&1)
        u*=x ;
    return u%mod ;
}

int n , k ;
int dp[2005][2005] ;
vector<string>v ;
vector<string > numbers ={  "1110111", "0010010", "1011101", "1011011", "0111010", "1101011", "1101111", "1010010", "1111111", "1111011" } ;



int isvalid(string s , int x) {
    string t = numbers[x] ;
    int c  = 0;
    for(int i = 0 ;i<t.size() ;i++){
        if (s[i]=='1' && t[i] =='0')
            return -1 ;
        else if (s[i] != t[i])
            c++;
    }
    return c ;
}
bool m = 0;
string ans ;

int fn(int i ,int rem){
    if (i ==n && rem ==0)
        return -2;
    if (i == n || rem<0  )
        return -3 ;

    int& ret = dp[i][rem] ;
    if (~ret){
        return ret ;
    }
    int t;
    ret = -3 ;
    for(int j = 9 ;j>=0 ;j-- ){
        int x = isvalid(v[i] , j) ;
        if (x >=0 && x <=rem){
            t = fn(i+1 , rem-x);
            if (t != -3){
                ret = j ;
                ans+= to_string (j) ;
                m = 1; 
                return ret ;
            }
        }
    }
    return ret ;
}



void build(int i ,int rem){
    if (i == n)
        return ;
    int nxt = fn(i ,rem ) ;
    int cost = isvalid(v[i] , nxt) ;
    ans+=to_string(nxt) ;
    build(i+1 , rem - cost) ;
}

void solve(){
    cin>>n>>k;
    memset(dp ,-1 ,sizeof dp) ;
    fp(n) {
        string s ;cin>>s ;
        v.push_back(s);
    }
    fn(0 , k) ;
    if (!m)
        cout<<-1;
    else{
        reverse(ans.begin() ,ans.end());
        cout<<ans ;
    }
}


signed main() {
    momen
    int t=1 ;
    //seive();
    //pree() ;
    //cin >> t ;
    //string s ;
    for(int i=1 ;i<=t ;i++){
        solve() ;
    }
}