test/aoj/3213.test.cpp

• View this file on GitHub
• Last update: 2020-12-20 13:43:34+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=3213

Depends on

• io/single.cpp
• tools/chminmax.cpp
• tools/defaultdict.cpp

Code

// verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=3213

#include <bits/stdc++.h>
using namespace std;

#define call_from_test
#include "../../io/single.cpp"
#include "../../tools/chminmax.cpp"
#include "../../tools/defaultdict.cpp"
#undef call_from_test

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);
  const char newl = '\n';

  int n,m;
  cin>>n>>m;
  m++; // [0, m] -> [0, m)

  auto as=read(n);
  auto bs=read(n);

  while(n<34){
    as.emplace_back(0);
    bs.emplace_back(0);
    n++;
  }
  assert(n==34);
  using ll = long long;

  const int h = n/2;
  const int sz = 1<<h;
  using P = pair<ll, ll>;
  vector<P> vp,vq;
  for(int t=0;t<2;t++){
    for(int bit=0;bit<sz;bit++){
      ll x=0,y=0;
      for(int i=0;i<h;i++){
        if((bit>>i)&1){
          x^=as[t*h+i];
          y+=bs[t*h+i];
        }
      }
      vp.emplace_back(x,y);
    }
    swap(vp,vq);
  }

  const ll INF = 1e18;
  const int LOG = 30;

  ll ans=0;
  for(int t=LOG-1;t>=0;t--){
    if((~m>>t)&1) continue;

    DefaultDict<ll, ll> dp(-INF);
    auto get_bit=[&](int b){return (b>>t)<<t;};
    for(auto[x,y]:vp)
      chmax(dp[get_bit(x)],y);

    for(auto[x,y]:vq)
      if(dp.count(get_bit(m^(1LL<<t)^x)))
        chmax(ans,dp[get_bit(m^(1LL<<t)^x)]+y);
  }

  cout<<ans<<newl;
  return 0;
}

#line 1 "test/aoj/3213.test.cpp"
// verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=3213

#include <bits/stdc++.h>
using namespace std;

#define call_from_test
#line 1 "io/single.cpp"

#line 3 "io/single.cpp"
using namespace std;
#endif

//BEGIN CUT HERE
template<typename T=int>
vector<T> read(size_t n){
  vector<T> ts(n);
  for(size_t i=0;i<n;i++) cin>>ts[i];
  return ts;
}
//END CUT HERE
#ifndef call_from_test
signed main(){
  return 0;
}
#endif
#line 1 "tools/chminmax.cpp"

#line 3 "tools/chminmax.cpp"
using namespace std;
#endif
//BEGIN CUT HERE
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
//END CUT HERE
#ifndef call_from_test
signed main(){
  return 0;
}
#endif
#line 1 "tools/defaultdict.cpp"

#line 3 "tools/defaultdict.cpp"
using namespace std;
#endif
//BEGIN CUT HERE
template<typename Key,typename T>
struct DefaultDict : map<Key, T>{
  using super = map<Key, T>;
  const T val;
  DefaultDict(T val_):val(val_){}
  T& operator[](const Key& key){
    if(!super::count(key))
      super::operator[](key)=val;
    return super::operator[](key);
  }
};
//END CUT HERE
#ifndef call_from_test
signed main(){
  return 0;
}
#endif
#line 10 "test/aoj/3213.test.cpp"
#undef call_from_test

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);
  const char newl = '\n';

  int n,m;
  cin>>n>>m;
  m++; // [0, m] -> [0, m)

  auto as=read(n);
  auto bs=read(n);

  while(n<34){
    as.emplace_back(0);
    bs.emplace_back(0);
    n++;
  }
  assert(n==34);
  using ll = long long;

  const int h = n/2;
  const int sz = 1<<h;
  using P = pair<ll, ll>;
  vector<P> vp,vq;
  for(int t=0;t<2;t++){
    for(int bit=0;bit<sz;bit++){
      ll x=0,y=0;
      for(int i=0;i<h;i++){
        if((bit>>i)&1){
          x^=as[t*h+i];
          y+=bs[t*h+i];
        }
      }
      vp.emplace_back(x,y);
    }
    swap(vp,vq);
  }

  const ll INF = 1e18;
  const int LOG = 30;

  ll ans=0;
  for(int t=LOG-1;t>=0;t--){
    if((~m>>t)&1) continue;

    DefaultDict<ll, ll> dp(-INF);
    auto get_bit=[&](int b){return (b>>t)<<t;};
    for(auto[x,y]:vp)
      chmax(dp[get_bit(x)],y);

    for(auto[x,y]:vq)
      if(dp.count(get_bit(m^(1LL<<t)^x)))
        chmax(ans,dp[get_bit(m^(1LL<<t)^x)]+y);
  }

  cout<<ans<<newl;
  return 0;
}

Back to top page