fork download
copy 
  1. //Author: Václav Volhejn (-Wave-)
  2. #include <iostream>
  3. #include <fstream>
  4. #include <vector>
  5. #include <cmath>
  6. #include <algorithm>
  7. #include <string>
  8. #include <map>
  9. using namespace std;
  10. #define rep(i,a,n) for (int i=a;i<n;i++)
  11. #define per(i,a,n) for (int i=n-1;i>=a;i--)
  12. #define ll long long
  13.  
  14. const bool distribute = true;
  15.  
  16. ll fact(int n) {
  17.     return n ? (fact(n - 1) * n) : 1;
  18. }
  19. const int MAXK = 26;
  20. map<ll, ll> m[MAXK];
  21. ll s;
  22.  
  23. int main() {
  24.     istream *in = distribute ? (&cin) : (new ifstream("in.txt"));
  25.     int n, k;
  26.     *in >> n >> k >> s;
  27.     ll input[n];
  28.     rep(i, 0, n) *in >> input[i];
  29.  
  30.     rep(mask, 0, pow(3, n / 2)) {
  31.         int c = mask;
  32.         int used = 0;
  33.         bool ok = true;
  34.         ll sum = 0;
  35.         rep(i, 0, n / 2) {
  36.             if(c % 3 == 1) sum += input[i];
  37.             if(c % 3 == 2) {
  38.                 used++;
  39.                 if((used > k) || (input[i] > 18)) {
  40.                     ok = false;
  41.                     break;
  42.                 }
  43.                 sum += fact(input[i]);
  44.             }
  45.             c /= 3;
  46.         }
  47.         if(ok) {
  48.             if(!m[used].count(sum))
  49.                 m[used][sum] = 0;
  50.             m[used][sum]++;
  51.         }
  52.     }
  53.     ll res = 0;
  54.     rep(mask, 0, pow(3, n - n / 2)) {
  55.         int c = mask;
  56.         int used = 0;
  57.         bool ok = true;
  58.         ll sum = 0;
  59.         rep(i, n / 2, n) {
  60.             if(c % 3 == 1) sum += input[i];
  61.             if(c % 3 == 2) {
  62.                 used++;
  63.                 if((used > k) || (input[i] > 18)) {
  64.                     ok = false;
  65.                     break;
  66.                 }
  67.                 sum += fact(input[i]);
  68.             }
  69.             c /= 3;
  70.         }
  71.         if(ok) {
  72.             rep(i, 0, k - used + 1) {
  73.                 if(!m[i].count(s - sum)) continue;
  74.                 res += m[i][s - sum];
  75.             }
  76.         }
  77.     }
  78.     cout << res << endl;
  79.     return 0;
  80. }
Success #stdin #stdout 1.14s 3280KB
comments (?)
stdin
copy 
25 9 137
4 3 1 4 1 2 2 1 1 1 4 4 3 4 4 3 2 1 3 2 4 2 4 1 4
stdout
copy 
2310192318
https://ideone.com/IMONbz
language:
C++ (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!