fork(1) download
copy 
  1. #include<iostream>
  2. #include<cstring>
  3. #include<string>
  4. #include<algorithm>
  5. #include<cstdio>
  6. #define ll long long int
  7. #define mk make_pair
  8. using namespace std;
  9.  
  10. int n;
  11. char s[111][20];
  12. ll a[111];
  13. pair<ll,ll> dp[1<<11][111];
  14.  
  15. pair<ll,ll> solve(int index,ll mask,ll sum)
  16. {
  17.     // base case
  18.     if(index==n)
  19.         return mk(sum,0);
  20.  
  21.     // if already found return the ans
  22.     if(dp[mask][index].first!=-1)
  23.         return dp[mask][index];
  24.  
  25.     pair<ll,ll> temp;
  26.     // not picking current number
  27.     dp[mask][index]=solve(index+1,mask,sum);
  28.  
  29.  
  30.     // checking if it is possible to pick current number
  31.     int l=strlen(s[index]);
  32.     ll new_mask=mask,flag=0;
  33.     for(int i=0;i<l;i++)
  34.     {
  35.         if((mask&(1<<(s[index][i]-'0')))==0)
  36.         {
  37.             new_mask=new_mask|(1<<(s[index][i]-'0'));
  38.         }
  39.         else
  40.         {
  41.             flag=1;
  42.             break;
  43.         }
  44.     }
  45.     if(!flag)
  46.     {
  47.         temp=solve(index+1,new_mask,sum+a[index]);
  48.         temp.second+=1;
  49.         if(temp.first>dp[mask][index].first)
  50.             dp[mask][index]=temp;
  51.         else if(temp.first==dp[mask][index].first)
  52.             dp[mask][index].second=max(dp[mask][index].second,temp.second);
  53.     }
  54.     return dp[mask][index];
  55. }
  56.  
  57.  
  58. int main()
  59. {
  60.     while((cin>>n))
  61.     {
  62.         int i,j;
  63.         for(i=0;i<n;i++)
  64.             cin>>a[i];
  65.         for(i=0;i<n;i++)
  66.             sprintf(s[i],"%lld",a[i]);
  67.         for(i=0;i<(1<<11);i++)
  68.         {
  69.             for(j=0;j<=n;j++)
  70.                 {
  71.                     dp[i][j].first=-1;
  72.                     dp[i][j].second=0;
  73.                 }
  74.         }
  75.         pair<ll,ll> ans=solve(0,0,0);
  76.         cout<<ans.second<<"\n";
  77.     }
  78.     return 0;
  79. }
  80.  
Success #stdin #stdout 0.01s 6288KB
comments (?)
stdin
copy 
3
7 17 10
2
12 29
3
1 2 12
stdout
copy 
2
1
1
https://ideone.com/PuMKLw
language:
C++ 4.3.2 (gcc-4.3.2)
created:
9 years ago
visibility:
secret

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!