Submission #59666990

---

Source Code Expand

#include <bits/stdc++.h>
#include<atcoder/all>
#define rep(i,n) for(int i=0;i<(n);i++)
using namespace std;
using namespace atcoder;
#define all(a) a.begin(),a.end()
typedef long long ll;
typedef pair<ll,ll> P;
constexpr ll mod=998244353;
typedef modint1000000007 mi;

ll a[45];

vector<ll>val1[22],val2[22];

int main(){
    ll n,k,p;
    cin>>n>>k>>p;
    rep(i,n)cin>>a[i];
    for(int i=0;i<(1<<(n/2));i++){
        int pc=0;
        ll val=0;
        for(int j=0;j<n/2;j++){
            if(i&(1<<j)){
                pc++;
                val+=a[j];
            }
        }
        val1[pc].push_back(val);
    }
    for(int i=0;i<(1<<(n-n/2));i++){
        int pc=0;
        ll val=0;
        for(int j=0;j<n-n/2;j++){
            if(i&(1<<j)){
                pc++;
                val+=a[j+n/2];
            }
        }
        val2[pc].push_back(val);
    }
    rep(i,21){
        sort(all(val1[i]));
        sort(all(val2[i]));
    }

    ll ans=0;
    for(int i=0;i<=20;i++){
        int nk=k-i;
        if(0<=nk&&nk<=21){
            for(auto e:val1[i]){
                ans+=(upper_bound(all(val2[nk]),p-e)-val2[nk].begin());
            }
        }
    }
    cout<<ans<<endl;
}

Submission Info

Judge Result