SHARE
TWEET

Untitled

a guest May 22nd, 2019 59 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp> // Common file
  3. #include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
  4. using namespace std;
  5. using namespace __gnu_pbds;
  6. typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
  7.  
  8. const int maxn = 50;
  9. int n, A;
  10. long long dp[maxn + 3][2500 + 3][maxn + 3];
  11. long long arr[maxn + 3];
  12.  
  13. long long solve(long long index, long long sum, long long numberOfChosen)
  14. {
  15.     if(index == n)
  16.     {
  17.         return (numberOfChosen != 0 && sum % A == 0 && A * numberOfChosen == sum);
  18.     }
  19.     if(dp[index][sum][numberOfChosen] != -1)
  20.         return dp[index][sum][numberOfChosen];
  21.     long long ans = 0;
  22.     ans += solve(index + 1, sum, numberOfChosen);
  23.     ans += solve(index + 1, sum + arr[index], numberOfChosen + 1);
  24.     return dp[index][sum][numberOfChosen] = ans;
  25. }
  26.  
  27. int main()
  28. {
  29.     cin >> n >> A;
  30.     for(int i = 0; i < n; i++)
  31.         cin >> arr[i];
  32.     memset(dp, -1, sizeof dp);
  33.     cout << solve(0, 0, 0);
  34.     return 0;
  35. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top