q051.rs

use itertools::Itertools;
use superslice::Ext;

// 部分列からちょうどk個選び、p以下の和のみ列挙
// 部分列の長さが0またはk=0の場合は{0}を返す。どのk個を選んでもpを超える場合は{}を返す。
fn sums(a_slice: &[i64], p: i64, k: usize) -> Vec<i64> {
    let mut sums: Vec<_> = a_slice.iter().combinations(k)
        .map(|v| v.into_iter().sum::<i64>() )
        .filter(|&s| s <= p )
        .collect();
    sums.sort();
    sums
}

fn main() {
    proconio::input! {
        n: usize,
        k: usize,
        p: i64,
        a: [i64; n],
    };
    let mut ans = 0;
    for k1 in 0..=k.min(n/2) {
        let k2 = k-k1; // k1 + k2 = k
        let sum1s = sums(&a[..n/2], p, k1); // 数列の前半からk1個選ぶ
        let sum2s = sums(&a[n/2..], p, k2); // 数列の後半からk2個選ぶ
        for sum1 in sum1s {
            let pos2 = sum2s.upper_bound(&(p-sum1)); // 数列の前半の和がs1のとき、後半はp-s1以下
            ans += pos2;
        }
    }
    println!("{}", ans);
}