fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long int
  4. #define pb emplace_back
  5. #define mp make_pair
  6. #define fi first
  7. #define se second
  8. #define all(v) v.begin(), v.end()
  9. #define ms(a,x)  memset(a, x, sizeof(a));                
  10. #define mod 1000000007
  11. int exp(int x,int y){int res=1;x=x%mod;while(y>0){if(y&1)res=(res*x)%mod;y=y>>1;x=(x*x)%mod;}return res;}
  12. int modinv(int x){return exp(x,mod-2);}
  13. int add(int a,int b){a%=mod,b%=mod;a=((a+b)%mod+mod)%mod;return a;}
  14. int sub(int a,int b){a%=mod,b%=mod;a=((a-b)%mod+mod)%mod;return a;}
  15. int mul(int a,int b){a%=mod,b%=mod;a=((a*b)%mod+mod)%mod;return a;}
  16.  
  17. int dp[1000009];
  18. int solve(int n, int k, vector<int> &a)
  19. {
  20.   if (k < 0)
  21.     return 0;
  22.  
  23.   if (k == 0)
  24.     return 1;
  25.  
  26.   if (dp[k] != -1)
  27.     return dp[k];
  28.  
  29.   int ans = 0;
  30.  
  31.   for (int i = 0; i < n; i++)
  32.   {
  33.     ans = add(ans, solve(n, k - a[i], a));
  34.   }
  35.  
  36.   return dp[k] = ans % mod;
  37. }
  38.  
  39. signed main()
  40. {
  41.  
  42.  
  43.  
  44.   int t = 1;
  45.   //cin>>t;
  46.   while (t--)
  47.   {
  48.  
  49.     int n, i, x, k;
  50.     int h[100009] = {0};
  51.     ms(dp, -1);
  52.  
  53.     cin >> n >> k;
  54.  
  55.  
  56.     vector<int> a(n, 0), v;
  57.  
  58.     for (i = 0; i < n; i++)
  59.       cin >> a[i];
  60.  
  61.     sort(all(a));
  62.  
  63.     x = solve(n, k, a);
  64.  
  65.     cout << x;
  66.   }
  67. }
Success #stdin #stdout 0.01s 11424KB
comments (?)
stdin 
3 2000
1 1500 1000
stdout 
1504
https://ideone.com/Sgr2iL
language:
C++14 (gcc 8.3)
created:
4 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!