meet_in_the_middle_1628.cpp (1105B)
1 #include <algorithm> 2 #include <iostream> 3 #include <numeric> 4 #include <unordered_map> 5 #include <vector> 6 7 void add_to_map(size_t i, size_t e, long long s, 8 const std::vector<long long>& a, 9 std::unordered_map<long long, long long>& m) { 10 if (i == e) { m[s]++; return; } 11 add_to_map(i+1, e, s, a, m); 12 add_to_map(i+1, e, s+a[i], a, m); 13 } 14 15 long long f(size_t i, size_t e, long long t, long long s, 16 const std::vector<long long>& a, 17 const std::unordered_map<long long, long long>& m) { 18 if (t < 0 || t > s) return 0; 19 if (i == e) return m.find(t) == m.end() ? 0 : m.at(t); 20 return f(i+1, e, t, s-a[i], a, m) + f(i+1, e, t-a[i], s-a[i], a, m); 21 } 22 23 int main() { 24 size_t n, p; 25 long long x, s{0}; 26 std::cin >> n >> x; 27 std::vector<long long> a(n); 28 for (size_t i = 0; i < n; i++) 29 std::cin >> a[i]; 30 31 std::sort(a.begin(), a.end(), std::greater<long long>()); 32 s = std::accumulate(a.begin(), a.end(), 0LL); 33 if (x > s) { 34 std::cout << "0\n"; 35 return 0; 36 } 37 38 p = a.size()/2; 39 std::unordered_map<long long, long long> m; 40 add_to_map(p, a.size(), 0, a, m); 41 std::cout << f(0, p, x, s, a, m) << "\n"; 42 }