fork download
copy 
  1. #include <iostream>
  2. #include <cmath>
  3. #include <vector>
  4. #include <string.h>
  5. #include <bits/stdc++.h>
  6. #include <cstdlib>
  7. #include <time.h>
  8. #include <fstream>
  9. #include <iterator>
  10. #include <utility>
  11. #include <algorithm>
  12. #include <set>
  13. #include <map>
  14. #include <bitset>
  15.  
  16. using namespace std;
  17.  
  18. #define ll long long
  19. #define ull unsigned ll
  20. #define ld long double
  21. typedef vector<int> vi;
  22. typedef multiset<int> mi;
  23. typedef multiset<ll> mll;
  24. typedef vector<ll> vll;
  25. typedef vector<bool> vb;
  26. typedef vector<string> vs;
  27. typedef vector<vector<int>> _2vi;
  28. typedef vector<vector<ll>> _2vll;
  29. #define all(v) ((v).begin()), ((v).end())
  30. #define sz(v) ((ll)((v).size()))
  31.  
  32. #define vinp(v, n)                \
  33.     for (ull i = 0; i < (n); i++) \
  34.     cin >> (v)[i]
  35. #define printv(v)      \
  36.     for (auto i : (v)) \
  37.     cout << i << " "
  38. #define fr0(i, n) for (ll(i) = 0; (i) < (n); (i)++)
  39. #define fr1(i, n) for (ll(i) = 1; (i) < (n); (i)++)
  40. #define fr(i, x, n) for (ll(i) = (x); (i) < (n); (i)++)
  41. #define _CRT_SECURE_NO_WARNING
  42. const ll MOD = 1000000007;
  43.  
  44. void Bustany() {
  45.     ios_base::sync_with_stdio(false);
  46.     cin.tie(NULL);
  47.     cout.tie(NULL);
  48. #ifndef ONLINE_JUDGE
  49.     freopen("./in.txt", "r", stdin), freopen("./out.txt", "w", stdout);
  50. #endif
  51. }
  52.  
  53. ll n, k;
  54. const ll N = 1e6 + 5;
  55.  
  56. void solve() {
  57.     cin >> n >> k;
  58.     vll v(n);
  59.     vinp(v, n);
  60.     vll dp(k+1,0);
  61.     dp[0] = 1;
  62.     sort(all(v));
  63.     fr0(i, k + 1) {
  64.         fr0(j, n) {
  65.             if (i >= v[j]) {
  66.                 if (dp[i - v[j]] != 0)
  67.                     dp[i] = ((dp[i]) + (dp[i - v[j]])) % MOD;
  68.             } else break;
  69.         }
  70.     }
  71.     cout << dp[k] % MOD << endl;
  72. }
  73.  
  74. int main() {
  75.     Bustany();
  76.     ll t = 1;
  77.     //    cin >> t;
  78.     while (t--) {
  79.         solve();
  80.     }
  81. }
Success #stdin #stdout 0.01s 5276KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/hBRJzs
language:
C++ (gcc 8.3)
created:
8 days 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!