fork download
copy 
  1. #pragma GCC optimize("Ofast")
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. using ll = long long;
  5. #define int long long
  6.  
  7. vector<ll> memory(6 + 1, -1); // Not Calculated Yet
  8.  
  9. bool f(ll target, ll coins[], ll n)
  10. {
  11.     if (target == 0)
  12.         return true;
  13.     else if (target < 0)
  14.         return false;
  15.     else if (memory[target] != -1)
  16.         return memory[target];
  17.     else {
  18.         bool isThisValid = false;
  19.         for (int i = 0; i < n; i++)
  20.             if (f(target - coins[i], coins, n))
  21.                 isThisValid = true;
  22.         memory[target] = isThisValid;
  23.         return memory[target];
  24.     }
  25. }
  26.  
  27. void Solve()
  28. {
  29.     ll target = 1; // 2+2+2=6 //3+3=6
  30.     ll coins[] = { 2, 3 };
  31.     ll n = 2; // total coins
  32.     cout << f(target, coins, n) << '\n';
  33. }
  34.  
  35. int32_t main()
  36. {
  37.     ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  38.     int t = 1;
  39.     // cin >> t;
  40.     for (int i = 1; i <= t; i++) {
  41.         Solve();
  42.     }
  43.     return 0;
  44. }
  45. // Coded by Tahsin Arafat (@TahsinArafat)
  46. // Coded for CPS Academy
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/ZOGgSs
language:
C++ (gcc 8.3)
created:
1 day 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!