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. ll dp[N];
  56. ll v[101];
  57.  
  58. ll get(ll sum) {
  59.     if(sum==0){
  60.         return 1;
  61.     }
  62.     if (dp[sum] != 0)return dp[sum];
  63.     fr0(i, n) {
  64.         if (v[i] <= sum) {
  65.             dp[sum]=(dp[sum]+get(sum-v[i]))%MOD;
  66.         }
  67.         else break;
  68.     }
  69.     return dp[sum];
  70. }
  71.  
  72. void solve() {
  73.     cin >> n >> k;
  74.     vinp(v, n);
  75.     memset(dp,0, k+1);
  76.     sort(v,v+n);
  77.     cout << get(k);
  78. }
  79.  
  80. int main() {
  81.     Bustany();
  82.     ll t = 1;
  83.     //    cin >> t;
  84.     while (t--) {
  85.         solve();
  86.     }
  87. }
Success #stdin #stdout 0.01s 5276KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/kUemNL
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!