525E - Anya and Cubes - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int N = 105;

ll n, k, S;
ll factorial[19];



void solve(int idx, ll sum, int ex, vector<int> &v,  map<ll, vector<int>> &m) {
    if (idx == v.size()) return void(m[sum].push_back(ex));
    
    solve(idx + 1, sum, ex, v, m);
    solve(idx + 1, sum + v[idx], ex, v, m);
    if (v[idx] < 19 && sum + factorial[v[idx]] <= S)
        solve(idx + 1, sum + factorial[v[idx]], ex + 1, v, m);
}


int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    
    cin >> n >> k >> S;
    vector<int> a(n); 
    for (int i = 0; i < n; i++) cin >> a[i];
    vector<int> v1(a.begin(), a.begin() + n/2), v2(a.begin() + n/2, a.end());
    
    factorial[0] = 1;
    for (int i = 1; i < 19; i++) 
        factorial[i] = factorial[i - 1] * i;
        
    map<ll, vector<int>> m1, m2; // map for finding the elements with the number of ! with it.
    
    solve(0, 0, 0, v1, m1);
    solve(0, 0, 0, v2, m2);
    m1[0] = {0};
    m2[0] = {0};
    
    for (auto u : m2) 
        sort(m2[u.first].begin(), m2[u.first].end()); 
    
    ll ans = 0;
    for (auto u : m1) {
        ll target = S - u.first;
        if (m2.find(target) != m2.end()) {
            for (auto l : m1[u.first]) {
                auto it = upper_bound(m2[target].begin(), m2[target].end(), k - l);
                ans += it - m2[target].begin(); 
            }
        }
    }
    //here
    cout << ans << "\n";
    
    return 0;
}