ismaeil

big data kattis

Jun 15th, 2021 (edited)
385
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.82 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define LSOne(a) ((a) & -(a))
  5. typedef vector< int > vi;
  6. #define OO int(1e9)
  7.  
  8. const int N = 15;
  9.  
  10. int numDiffPF[15000]; // num of distinct primes
  11. int memo[N][1 << N];
  12. int n ,a[N];
  13.  
  14. void modified_sieve(int upperbound)
  15. {
  16.     for(int i = 2 ; i < upperbound ; i++)
  17.         if( !numDiffPF[i] )
  18.             for(int j = i ; j < upperbound ; j += i)
  19.                 numDiffPF[j] += 1;
  20. }
  21.  
  22. int calc(int i ,int Mask)
  23. {
  24.     if( i == n ) return !Mask ? 0 : -OO;
  25.    
  26.     int &re = memo[i][Mask];
  27.     if( re + 1 ) return re;
  28.    
  29.     /// --- Pruning The DP A Bit --- ///
  30.         /// --- store the valid elements only and ignour the taken ones --- ///
  31.         /// --- and that make for loop that try all subsets faster alot --- ///
  32.             vi b;
  33.             int size = 0;
  34.             int tmp = Mask;
  35.             while( tmp )
  36.             {
  37.                 int lsone = LSOne(tmp);
  38.                 b.push_back(lsone);
  39.                 tmp -= lsone;
  40.                 size += 1;
  41.             }
  42.    
  43.     /// --- Try All SubSets In The New Valid Smaller Set --- ///
  44.         re = -OO;
  45.         for(int pick = 0 ; pick < (1 << size) ; pick += 1)
  46.         {
  47.             int tmpMask = pick;  // Mask For Cur Taken SubSet Of Elements
  48.             int newMask = Mask;  // Get New BitMask For The Next Elements
  49.            
  50.             // get num of distinct primes factors from it
  51.             int sum = 0;
  52.            
  53.             // Iterate Over Taken Element And Update newMask and Sum --- ///
  54.             while( tmpMask )
  55.             {
  56.                 int lsone = LSOne(tmpMask);
  57.                 tmpMask -= lsone;
  58.                
  59.                 int j = __builtin_ctz(lsone);
  60.                 sum += a[ __builtin_ctz(b[j]) ];
  61.                
  62.                 // Turn Of bits that was valid and now taken
  63.                 newMask ^= b[j];
  64.             }
  65.            
  66.             // Update DP
  67.             re = max(re ,calc(i + 1 ,newMask) + numDiffPF[sum]);
  68.         }
  69.    
  70.     return re;
  71. }
  72.  
  73. int main()
  74. {
  75.     modified_sieve(15000);
  76.    
  77.     scanf("%d" ,&n);
  78.     for(int i = 0 ; i < n ; i++)
  79.         scanf("%d" ,&a[i]);
  80.    
  81.     memset(memo ,-1 ,sizeof memo);
  82.     printf("%d" ,calc(0 ,(1 << n) - 1));
  83. }
  84.  
Add Comment
Please, Sign In to add comment