A. Marcin and Training Camp ～bitで見た時のsubset～ is_subset

is_subset

/* b is subset of a

a = 11001010
b = 01001000
=> true

*/ 
bool is_subset(ll a, ll b){
  ll c = (~b | a);
  if(c==~0LL){
    // 11111111
    return true;
  }else{
    return false;
  }
}

A. Marcin and Training Camp

• Quiz
  • https://codeforces.com/contest/1210/problem/B
• AC
  • https://codeforces.com/contest/1210/submission/91174274
• 解説
  • editorialの通り。N=7000なので7000x7000x60だとTLE
  • bitで見たときにbがaのsubsetである判定をO(1)でする必要がある

/* b is subset of a

a = 11001010
b = 01001000
=> true

*/ 
bool is_subset(ll a, ll b){
  ll c = (~b | a);
  if(c==~0LL){
    // 11111111
    return true;
  }else{
    return false;
  }
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N; 
    cin>>N;
    
    VI A(N);
    rep(i,N)cin>>A[i];

    VI B(N);
    rep(i,N)cin>>B[i];

    map<ll, VI> mp;
    rep(i,N){
      mp[A[i]].push_back(B[i]);
    }

    map<ll,bool> used;

    ll sum=0;
    VI M; // members
    for(auto pa : mp){
      if(pa.second.size()==1) continue;

      ll a = pa.first;
      sum += SUM(pa.second);
      
      M.push_back(a);
      used[a]=true;
    }

    // take in lonely member
    rep(i,N){
      ll a = A[i];
      if(used[a]) continue;
      bool humble = false;
      for(ll v : M){
        if(is_subset(v, a)) humble=true;
      }
      if(humble) sum+=B[i];
    }
    p(sum);
    
    return 0;
}