fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. ///******************************** C o n t a i n e r ********************************///
  4. typedef long long ll;
  5. typedef vector<int> vi;
  6. typedef vector<ll> vl;
  7. ///********************************** M a r c o ***********************************///
  8. #define F first
  9. #define S second
  10. #define mem(a,b) memset(a, b, sizeof(a))
  11. ///**************************************************** C o d e ****************************************************///
  12. ///-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=///
  13.  
  14. vector<pair<int,int> > ans;
  15. int siz,n,k,i,dp[10][10004]; 
  16. vi op;            ///op for cost and siz = size of op
  17.  
  18. int rec(int curi,int curs)
  19. {
  20.     if(curi==siz or !curs) return !curs;                ///base case
  21.     if(dp[curi][curs]!=-1) return dp[curi][curs];       ///memorization
  22.     int a=0;
  23.     for(int k=curs/op[curi];k>=0;k--){
  24.         if(k*op[curi]<=curs) a+=rec(curi+1,curs-k*op[curi]);
  25.         else break;
  26.         if(a){ans.push_back({op[curi],k}); break;}
  27.     }
  28.     dp[curi][curs]=a;
  29.     return dp[curi][curs];
  30. }
  31.  
  32. main()
  33. {
  34.     vector<string> v(8);
  35.     string s;
  36.     cin>>n>>k;
  37.     int a;
  38.     map<int ,int> m;
  39.     vi cnt;
  40.     mem(dp,-1);
  41.     while(k--) cin>>a,m[a]++;
  42.     for(i=1;i<10;i++){
  43.         if(m[i]){
  44.             if(i==1) v[2]="1",op.push_back(2);
  45.             else if(i==7) v[3]="7",op.push_back(3);
  46.             else if(i==3 or i==5 or i==2){
  47.                 if(m[1] and m[7]) v[5]="71";
  48.                 else if(m[5]) v[5]="5";
  49.                 else if(m[3]) v[5]="3";
  50.                 else v[5]="2";
  51.                 op.push_back(5);
  52.             }
  53.             else if(i==4){
  54.                 if(m[1]) v[4]="11";
  55.                 else v[4]="4";
  56.                 op.push_back(4);
  57.             }
  58.             else if(i==6 or i==9){
  59.                 if(m[1]) v[6]="111";
  60.                 else if(m[7]) v[6]="77";
  61.                 else if(m[9]) v[6]="9";
  62.                 else v[6]="6";
  63.                 op.push_back(6);
  64.             }
  65.             else{
  66.                 if(m[7] and m[1]) v[7]="711";
  67.                 else if(m[7] and m[4]) v[7]="74";
  68.                 else if(m[5] and m[1]) v[7]="51";
  69.                 else if(m[3] and m[1]) v[7]="31";
  70.                 else if(m[2] and m[1]) v[7]="21";
  71.                 else v[7]="8";
  72.                 op.push_back(7);
  73.             }
  74.         }
  75.     }
  76.     sort(op.begin(),op.end()); siz=op.size();
  77.     int x=rec(0,n);
  78.     for(auto i:ans){
  79.         int y=i.S;
  80.         while(y--) s+=v[i.F];
  81.     }
  82.     sort(s.rbegin(),s.rend());
  83.     cout<<s<<endl;
  84. }
  85.  
  86.  
  87. ///Thank you.
  88.  
  89.  
  90. ///Brainless_Loco Terminates Here!
  91.  
Success #stdin #stdout 0s 4280KB
comments (?)
stdin
copy 
101 9
9 8 7 6 5 4 3 2 1
stdout
copy 
71111111111111111111111111111111111111111111111111
https://ideone.com/2RVjQB
language:
C++ (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!