fork download
copy 
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <cstring>
  4.  
  5. using namespace std;
  6.  
  7. typedef long long ll;
  8.  
  9. const int LIM_X = 1e6 + 16;
  10. const int LIM_N = 11;
  11.  
  12. int x, n;
  13. int p[LIM_N];
  14. ll f[LIM_X][LIM_N];
  15. ll magic(int v = x, int t = 0)
  16. {
  17.     if (v < 0) return 0;
  18.     if (v == 0) return 1;
  19.     if (t >= n) return 0;
  20.  
  21.     ll &res = f[v][t];
  22.     if (res != -1) return res;
  23.  
  24.     res = magic(v - p[t], t + 0) + magic(v - 0, t + 1);
  25.     return res;
  26. }
  27.  
  28. int main()
  29. {
  30.     ios::sync_with_stdio(NULL);
  31.     cin.tie(NULL);
  32.  
  33.     cin >> x >> n;
  34.     for (int i = 0; i < n; ++i)
  35.         cin >> p[i];
  36.  
  37.     sort(p, p + n);
  38.     n = unique(p, p + n) - p;
  39.  
  40.     memset(f, -1, sizeof(f));
  41.     cout << magic();
  42.     return 0;
  43. }
Success #stdin #stdout 0.01s 89408KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/8Gg6tG
language:
C++14 (gcc 8.3)
created:
2 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!