本問題は 半分全列挙 と呼ばれる手法で解くことができます。

1. お菓子を \(2\) 等分し、以下の配列を作る。
   • \(a[i]=\{\) そのグループ内でお菓子を \(i\) 個選んだ場合の満足度の合計の配列 \(\}\)
2. 全ての \(i\) について、一方のグループの \(a[i]\) ともう一方のグループの \(a[K-i]\) とを統合する。

1. について、 bit 全探索を利用して配列を構築することができます。
2. について、求めた配列を \(a,b\) とします。 \(a\) を降順、 \(b\) を昇順にソートする。 \(a\) を先頭から調べていくとき、足し合わせて \(X\) 以上となる \(b\) の要素の数を尺取り法を活用することで \(a\) の要素それぞれに対して求めることができます。

全体の時間計算量は \(O(N2^{N/2})\) です。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;
using ll=long long;

vector<vector<ll>> gen(vector<ll> &a){
  ll n=a.size();
  vector<vector<ll>> res(n+1);
  for(ll i=0;i<(1ll<<n);i++){
    ll cnt=0,sum=0;
    for(ll j=0;j<n;j++){
      if(i&(1ll<<j)){
        cnt++;
        sum+=a[j];
      }
    }
    res[cnt].push_back(sum);
  }
  return res;
}

ll meet(vector<ll> a,vector<ll> b,ll X){
  sort(a.rbegin(),a.rend());
  sort(b.begin(),b.end());
  ll res=0,j=0;
  for(ll i=0;i<a.size();i++){
    while(j<b.size() && a[i]+b[j]<X){j++;}
    res+=(b.size()-j);
  }
  return res;
}

int main(){
  ll N,K,X;
  cin >> N >> K >> X;
  vector<ll> a,b;
  for(ll i=0;i<N;i++){
    ll A;
    cin >> A;
    if(i%2){b.push_back(A);}
    else{a.push_back(A);}
  }
  auto ga=gen(a);
  auto gb=gen(b);
  ll res=0;
  for(ll i=0;i<ga.size();i++){
    ll j=K-i;
    if(!(0<=j && j<gb.size())){continue;}
    res+=meet(ga[i],gb[j],X);
  }
  cout << res << "\n";
  return 0;
}