Quiz
AC
解き方
- 前半後半で半分に分ける(N=16ずつ)
- 前半のみで、各荷物を使うかどうか0/1で全パターン試す。216 = 65536
- 後半も同様
- 解説では二分探索と書かれていたがmapでも解けた
半分全列挙
- 半分毎に処理すれば間に合う時に使う
- O(2N)では間に合わないが、O(2N/2)なら間に合う(し、メモリにも乗る)
- いい感じに分割するという点では平方分割と似ている?
code
map<ll,ll> f(VI A){
ll N = A.size();
map<ll,ll> mp;
rep(f,1<<N){
ll sum=0;
rep(i,N){
if(f>>i&1){
sum += A[i];
}
}
mp[sum]++;
}
return mp;
}
int main(){
ll N,X;
cin>>N>>X;
VI A, B;
rep(i,N){
ll w;cin>>w;
if(i<N/2){
A.push_back(w);
}else{
B.push_back(w);
}
}
auto mp0 = f(A);
auto mp1 = f(B);
ll ans=0;
for(auto pa : mp0){
ll v = pa.first;
ll cnt = pa.second;
ll rest = X-v;
if(rest<0)continue;
if(mp1.count(rest)==0)continue;
ans += cnt * mp1[rest];
}
p(ans);
return 0;
}