fork(1) download
copy 
  1. #include<bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4. using namespace std;
  5. using namespace __gnu_pbds;
  6. typedef long long ll;
  7. typedef long double ld;
  8. typedef pair<int, int> pii;
  9. typedef pair<ll, ll> pll;
  10. typedef vector<int> vi;
  11. typedef vector<ll> vl;
  12. typedef vector<pii> vii;
  13. typedef vector<pll> vll;
  14. #define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
  15. #define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>
  16. #define all(x) (x).begin(),(x).end()
  17. #define pb push_back
  18. #define ff first
  19. #define ss second
  20. #define mp make_pair
  21.  
  22. const int bity = 23;
  23. const int N = (1 << bity);
  24.  
  25. int main(){
  26.     ios_base::sync_with_stdio(0);
  27.     cin.tie(0);
  28.  
  29.     int n; cin >> n;
  30.  
  31.     vi t(n);
  32.     for(int i = 0; i < n; i++) cin >> t[i];
  33.  
  34.     vector<vi> pom(bity + 2);
  35.     for(int i = 1; i <= bity + 1; i++){
  36.         pom[i].resize(1 << (i - 1), 0);
  37.     }
  38.  
  39.     for(int i = 0; i < n; i++){
  40.         int p = t[i], msb = 0;
  41.         for(int j = bity + 1; j > 0; j--){
  42.             if(p & (1 << (j - 1))){
  43.                 msb = j; break;
  44.             }
  45.         }
  46.         if(msb > 0){
  47.             int zero = (~p) & ((1 << (msb - 1)) - 1);
  48.             pom[msb][zero] = 1;
  49.         }
  50.     }
  51.  
  52.     for(int msb = 1; msb <= bity + 1; msb++){
  53.         int mx = 1 << (msb - 1);
  54.         for(int b = 1; b < msb; b++){
  55.             for(int mask = mx - 1; mask >= 0; mask--){
  56.                 if(mask & (1 << (b - 1))){
  57.                     pom[msb][mask ^ (1 << (b - 1))] += pom[msb][mask];
  58.                 }
  59.             }
  60.         }
  61.     }
  62.  
  63.     vi dp(N, 0);
  64.     dp[0] = 1;
  65.     for(int i = 1; i < N; i++){
  66.         int msb = 0;
  67.         for(int j = bity + 1; j > 0; j--){
  68.             if(i & (1 << (j - 1))){
  69.                 msb = j; break;
  70.             }
  71.         }
  72.         int wcz = i ^ (1 << (msb - 1));
  73.         if(wcz < (1 << (msb - 1))){
  74.             if(pom[msb][wcz] && dp[wcz]) dp[i] = 1;
  75.         }
  76.     }
  77.  
  78.     int wyn = 0;
  79.     for(int i = 1; i < N; i++){
  80.         if(dp[i]) wyn = max(wyn, __builtin_popcount(i));
  81.     }
  82.     cout << wyn;
  83.  
  84.     return 0;
  85. }
  86.  
Success #stdin #stdout 0.43s 101544KB
comments (?)
stdin
copy 
6
2 1 3 7 6 7
stdout
copy 
2
https://ideone.com/VWMhse
language:
C++ (gcc 8.3)
created:
2 days 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!