fork(2) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define pll pair<ll,ll>
  4. #define ll long long
  5. #define lli long long int
  6. #define ull unsigned long long
  7. #define ld long double
  8. #define pii pair<int,int>
  9. #define lower_boundIDX(x,val) lower_bound(all(x),val)-x.begin()
  10. #define upper_boundIDX(x,val) upper_bound(all(x),val)-x.begin()
  11. #define mem(a,val)  memset(a,val,sizeof(a))
  12. #define all(x) x.begin(),x.end()
  13. #define countbit(x)  __builtin_popcount(x)
  14. #define Obit(x)  __builtin_ctz(x)
  15. #define minHeap priority_queue<int,vector<int> ,greater<int>>
  16. #define maxHeap priority_queue<int>
  17. #define need_for_speed ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  18. #define debug(x) cout<<"# "<<x<<'\n';
  19. const int  MOD = 1000000007;
  20. const int MAX = 2e5+7;
  21.  
  22. vector<pii> vpp[2001];
  23. vector<int> sb,ans(2001);
  24. vector<int> ppp{1110111,0010010,1011101, 1011011, 0111010,1101011,1101111,1010010,1111111, 1111011};
  25. int n,kk,x;
  26. int dp[2001][2001];
  27.  
  28. int solve(int i,int k)
  29. {
  30.  
  31.  
  32.    if(k<0) return 0;
  33.    if(i==n && k==0) return 1;
  34.    if(i!=n && k==0) return 0;
  35.    int flag = 0;
  36.    if(dp[i][k]!=-1) return dp[i][k];
  37.  
  38.  
  39.    for(int j=0;j<vpp[i].size();j++)
  40.    {
  41.      pii pppp = vpp[i][j];
  42.      int tp = abs(sb[i]-pppp.first);
  43.      if(tp<=k)
  44.      {
  45.      	if(solve(i+1,k-tp)){ ans[i] = max(ans[i],pppp.second); flag = 1; }
  46.      }
  47.    }
  48.  
  49.    if(!flag) dp[i][k] = 0;
  50.    else dp[i][k] = 1;
  51.    return dp[i][k];
  52. }
  53.  
  54. int main()
  55. {
  56.  
  57.   need_for_speed;
  58.   cin>>n>>kk;
  59.   memset(dp,-1,sizeof(dp));
  60.   for(int i=0;i<n;i++)
  61.   {
  62.   	cin>>x;
  63.   	sb.push_back(countbit(x));
  64.   	for(int j=0;j<ppp.size();j++) vpp[i].push_back(make_pair(countbit(x&ppp[j]),j));
  65.   }
  66.   solve(0,kk);
  67.   if(dp[n][kk]) for(int i=0;i<n;i++) cout<<ans[i];
  68.   else cout<<"-1"<<'\n';
  69. }
  70.  
Success #stdin #stdout 0.01s 19308KB
comments (?)
stdin
copy 
2 5
0010010
0010010
stdout
copy 
99
https://ideone.com/qBBfH5
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!