fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main(){
  5.     ios::sync_with_stdio(false);
  6.     cin.tie(0);
  7.     int t;
  8.     cin >> t;
  9.     while(t--){
  10.         int n;
  11.         cin >> n;
  12.         vector<unsigned long long> a(n);
  13.         int Z =0;
  14.         vector<unsigned long long> b;
  15.         for(auto &x: a){
  16.             cin >> x;
  17.             if(x ==0) Z++;
  18.             else b.push_back(x);
  19.         }
  20.         // DP: map from OR to max size
  21.         unordered_map<unsigned long long, int> dp;
  22.         dp[0] =0;
  23.         for(auto x: b){
  24.             unordered_map<unsigned long long, int> tmp;
  25.             for(auto &[or_key, s]: dp){
  26.                 unsigned long long new_or = or_key | x;
  27.                 int new_size = s +1;
  28.                 auto it = tmp.find(new_or);
  29.                 if(it == tmp.end() || it->second < new_size){
  30.                     tmp[new_or] = new_size;
  31.                 }
  32.             }
  33.             for(auto &[k, v]: tmp){
  34.                 auto it = dp.find(k);
  35.                 if(it == dp.end() || it->second < v){
  36.                     dp[k] = v;
  37.                 }
  38.             }
  39.         }
  40.         // Now find the maximum value
  41.         long long max_val = (long long)Z; // empty subset
  42.         for(auto &[k, s]: dp){
  43.             // Calculate popcount
  44.             int cnt = __builtin_popcountll(k);
  45.             long long val = (long long)Z + (long long)s - (long long)cnt;
  46.             if(val > max_val){
  47.                 max_val = val;
  48.             }
  49.         }
  50.         cout << max_val << "\n";
  51.     }
  52. }
  53.  
Success #stdin #stdout 0s 5208KB
comments (?)
stdin
copy 
4
3
0 0 0
4
1 0 1 2
1
5
8
7 1 48 14 13 8 7 6
stdout
copy 
3
2
0
3
https://ideone.com/y6j2dK
language:
C++14 (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!