Aizu Online Judge in C++ #DPL_4_B : Coin Combination Problem II

Aizu Online Judge（AOJ）の過去問から、その提出コードの解答例です。

・問題 "Coin Combination Problem II"
https://onlinejudge.u-aizu.ac.jp/problems/DPL_4_B
・コインの組み合わせ II

僕が作成、提出したコードは、以下のとおりです。

Aizu Online Judge in C++ #DPL_4_B : Coin Combination Problem II

/*
Aizu Online Judge in C++ #DPL_4_B : Coin Combination Problem II
https://onlinejudge.u-aizu.ac.jp/problems/DPL_4_B
 提出コードの解答例
 https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
ll a[44],l,r;
ll k,n;
vector<ll> p[22];
int main(void){
    cin>>n>>k>>l>>r;
    ll N=(n+1)/2;
    for(ll i=0;i<n;i++){
        cin>>a[i];
    }
    for(ll i=0;i<(1<<N);i++){
        ll sum=0;
        for(ll j=0;j<N;j++){
            if(i&(1<<j)){
                sum+=a[j];
            }
        }
        p[__builtin_popcount(i)].push_back(sum);
    }
    for(ll i=0;i<=N;i++){
        sort(p[i].begin(),p[i].end());
    }
    ll cnt=0;
    for(ll i=0;i<(1<<(n-N));i++){
        ll sum=0;
        ll K=k-__builtin_popcount(i);
        if(K<0 || K>N){
            continue;
        }
        for(ll j=0;j<n-N;j++){
            if(i&(1<<j)){
                sum+=a[N+j];
            }
        }
        cnt+=distance(lower_bound(p[K].begin(),p[K].end(),l-sum),
                      upper_bound(p[K].begin(),p[K].end(),r-sum));
    }
    cout<<cnt<<endl;
    return 0;
}

設問の出典は、プログラミング問題のオンライン採点システム「Aizu Online Judge（AOJ）」です。
http://judge.u-aizu.ac.jp/onlinejudge/