fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define print(a)          \
  5.     for (auto x : a)      \
  6.         cout << x << " "; \
  7.     cout << endl
  8. #define print_upto(a, n)        \
  9.     for (int i = 0; i < n; i++) \
  10.         cout << a[i] << " ";    \
  11.     cout << endl
  12. #define take(x, n)              \
  13.     for (int i = 0; i < n; i++) \
  14.         cin >> x[i];
  15.  
  16. #define watch(x) cout << (#x) << " is " << (x) << "\n"
  17. #define watch2(x, y) cout << (#x) << " is " << (x) << " and " << (#y) << " is " << (y) << "\n"
  18. #define watch3(x, y, z) cout << (#x) << " is " << (x) << " and " << (#y) << " is " << (y) << " and " << (#z) << " is " << (z) << "\n"
  19.  
  20. #define ll long long
  21. #define ff first
  22. #define ss second
  23. #define null NULL
  24. #define all(c) (c).begin(), (c).end()
  25. #define nl "\n"
  26.  
  27. #define ld long double
  28. #define eb emplace_back
  29. #define pb push_back
  30. #define pf push_front
  31. #define mod 1000000007
  32.  
  33. typedef vector<ll> vl;
  34. typedef vector<vl> vvl;
  35. typedef pair<ll, ll> pll;
  36. typedef map<ll, ll> mll;
  37.  
  38. ll n, x;
  39. ll a[105];
  40.  
  41. ll f(ll i, ll sum, vector<vector<ll>> &dp)
  42. {
  43.     if (sum == x)
  44.         return 1;
  45.     else if (sum > x || i == n + 1)
  46.         return 0;
  47.  
  48.     if (dp[i][sum] != -1)
  49.         return dp[i][sum];
  50.  
  51.     ll ans = 0;
  52.     ans = (ans + f(i, sum + a[i], dp)) % mod;
  53.     ans = (ans + f(i + 1, sum, dp)) % mod;
  54.  
  55.     return dp[i][sum] = ans;
  56. }
  57.  
  58. int main()
  59. {
  60.  
  61.     // Use ctrl+shift+b ( second option )
  62.     ios_base::sync_with_stdio(false);
  63.     cin.tie(0);
  64.     cout.tie(0);
  65.  
  66.     ll t = 1;
  67.     // cin >> t;
  68.  
  69.     while (t--)
  70.     {
  71.         cin >> n >> x;
  72.  
  73.         for (ll i = 1; i <= n; i++)
  74.         {
  75.             cin >> a[i];
  76.         }
  77.  
  78.         vector<vector<ll>> dp(n + 1, vector<ll>(x + 1, -1));
  79.  
  80.         cout << f(1, 0, dp) << nl;
  81.     }
  82.  
  83.     return 0;
  84. }
  85.  
  86. // #include <bits/stdc++.h>
  87. // using namespace std;
  88.  
  89. // int main()
  90. // {
  91. //     int mod = 1e9 + 7;
  92. //     int n, target;
  93. //     cin >> n >> target;
  94. //     vector<int> x(n);
  95. //     for (int &v : x)
  96. //         cin >> v;
  97.  
  98. //     vector<vector<int>> dp(n + 1, vector<int>(target + 1, 0));
  99. //     dp[0][0] = 1;
  100. //     for (int i = 1; i <= n; i++)
  101. //     {
  102. //         for (int j = 0; j <= target; j++)
  103. //         {
  104. //             dp[i][j] = dp[i - 1][j];
  105. //             int left = j - x[i - 1];
  106. //             if (left >= 0)
  107. //             {
  108. //                 (dp[i][j] += dp[i][left]) %= mod;
  109. //             }
  110. //         }
  111. //     }
  112. //     cout << dp[n][target] << endl;
  113. // }
Success #stdin #stdout 0s 4292KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/qP2xv7
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!