Advertisement
strawhat_8502

Untitled

Jun 28th, 2022
789
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.58 KB | None
  1.  
  2. /*--------------AUTHOR : LANGAOP----------- */
  3.  
  4. #include<bits/stdc++.h>
  5. #include<iostream>
  6. #include<iomanip>
  7. #include<vector>
  8. #include<string>
  9. #include<math.h>
  10. #include<map>
  11. #include<algorithm>
  12. #include<set>
  13. #include<unordered_map>
  14. #include <unordered_set>
  15. #define fast ios_base::sync_with_stdio(false),cin.tie(NULL)
  16. using namespace std;
  17.  
  18.  
  19.  
  20. #define ff first
  21. #define ss second
  22. #define pb push_back
  23. #define int long long int
  24. typedef long double lld;
  25. #define FOR(i,n) for(int i=0;i<n;i++)
  26. #define yes cout<<"YES"<<endl;
  27. #define no cout<<"NO"<<endl;
  28. #define MOD 1000000007
  29.  
  30. #define vi vector<int>
  31. #define pii pair<int, int>
  32. #define vii vector<pii>
  33. #define fr front()
  34. #define bk back()
  35. #define all(x) (x).begin(), (x).end()
  36. #define rall(x) (x).rbegin(), (x).rend()
  37.  
  38. typedef vector<char> vc;
  39. typedef vector<string> vs;
  40. typedef vector<pair<int, int> > vpii;
  41. typedef unordered_set<int> us;
  42. typedef map<int,int> mp;
  43.  
  44. //debugging
  45.  
  46. #ifndef ONLINE_JUDGE
  47. #define debug(x) cerr << #x <<" "; _print(x); cerr << endl;
  48. #else
  49. #define debug(x)
  50. #endif
  51.  
  52. void _print(int t) {cerr << t;}
  53. void _print(string t) {cerr << t;}
  54. void _print(char t) {cerr << t;}
  55. void _print(lld t) {cerr << t;}
  56. void _print(double t) {cerr << t;}
  57.  
  58. template <class T, class V> void _print(pair <T, V> p);
  59. template <class T> void _print(vector <T> v);
  60. template <class T> void _print(set <T> v);
  61. template <class T, class V> void _print(map <T, V> v);
  62. template <class T> void _print(multiset <T> v);
  63. template <class T, class V> void _print(pair <T, V> p) {cerr << "{"; _print(p.ff); cerr << ","; _print(p.ss); cerr << "}";}
  64. template <class T> void _print(vector <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
  65. template <class T> void _print(set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
  66. template <class T> void _print(multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
  67. template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
  68. template <class T, class V> void _print(multimap <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
  69.  
  70.  
  71. //Constants
  72. const long double pi= 3.141592653589793238;
  73. const int INF= 1e18;
  74. const int mod=1e9+7;
  75.  
  76. //MATHEMATICAL FUNCTIONS
  77.  
  78. int gcd(int a, int b){if (b == 0)return a;return gcd(b, a % b);} //gcd
  79. int lcm(int a, int b){return (a/gcd(a,b)*b);} //lcm
  80. //sieve
  81. vector<int> sieve(int n) {int*arr = new int[n + 1](); vector<int> vect; for (int i = 2; i <= n; i++)if (arr[i] == 0) {vect.push_back(i); for (int j = 2 * i; j <= n; j += i)arr[j] = 1;} return vect;}
  82.  
  83. //binary exponentation
  84. int expo(int a, int b, int mod) {int res = 1; while (b > 0) {if (b & 1)res = (res * a) % mod; a = (a * a) % mod; b = b >> 1;} return res;}
  85.  
  86. //CHECK
  87.  
  88. bool isprime(int n){if(n<=1)return false;if(n<=3)return true;if(n%2==0||n%3==0)return false;for(int i=5;i*i<=n;i=i+6)if(n%i==0||n%(i+2)==0)return false;return true;}
  89. bool ispoweroftwo(int n){if(n==0)return false;return (ceil(log2(n)) == floor(log2(n)));}
  90. bool isperfectsquare(int x){if (x >= 0) {int sr = sqrt(x);return (sr * sr == x);}return false;}
  91. int ceils(int x, int y) {return x / y + (x % y > 0);}
  92.  
  93.  
  94. // Operator overloads
  95. template<typename T1, typename T2> // cin >> pair<T1, T2>
  96. istream& operator>>(istream &istream, pair<T1, T2> &p) { return (istream >> p.first >> p.second); }
  97. template<typename T> // cin >> vector<T>
  98. istream& operator>>(istream &istream, vector<T> &v){for (auto &it : v)cin >> it;return istream;}
  99. template<typename T1, typename T2> // cout << pair<T1, T2>
  100. ostream& operator<<(ostream &ostream, const pair<T1, T2> &p) { return (ostream << p.first << " " << p.second); }
  101. template<typename T> // cout << vector<T>
  102. ostream& operator<<(ostream &ostream, const vector<T> &c) { for (auto &it : c) cout << it << " "; return ostream; }
  103.  
  104. //USEFUL
  105. void printarr(int arr[], int n){FOR(i,n) cout << arr[i] << " ";cout << "\n";}
  106.  
  107. void solve(){
  108.     int n,x;
  109.     cin>>n>>x;
  110.     vector<int> coins(n);
  111.     cin>>coins;
  112.     vector<int> dp(x+1,0);
  113.     dp[0]=1;
  114.     for(int i=0;i<n;i++){
  115.         for(int j=x;j>=1;j--){
  116.             if(j<coins[i]) continue;
  117.             else dp[j]=dp[j]+dp[j-coins[i]];
  118.         }
  119.     }
  120.     debug(dp);
  121.     cout<<dp[x]<<endl;      
  122. }
  123.  
  124. int32_t main()
  125. {
  126.     fast;
  127. //      #ifndef ONLINE_JUDGE
  128. //     freopen("input.txt", "r", stdin);
  129. //     freopen("output.txt", "w", stdout);
  130. // #endif
  131.    
  132.     int t;
  133.     t=1;
  134.     // cin>>t;
  135.     while(t--){
  136.  
  137.         // cout<<t;
  138.         solve();
  139.     }
  140.     return 0;
  141.    
  142. }
Advertisement
RAW Paste Data Copied
Advertisement