fork download
  1. #include <iostream>
  2. #include <map>
  3.  
  4. using namespace std;
  5.  
  6. long int solve(long int n, map<int, long int> mp) {
  7. if(n<=1)
  8. return n;
  9.  
  10. if(mp.size())
  11. return mp[n];
  12.  
  13. long int ans = max(n, solve(n/2, mp)+solve(n/3, mp) + solve(n/4, mp));
  14.  
  15. mp.insert(pair<int, long int> (n, ans));
  16. return ans;
  17. }
  18.  
  19. int main() {
  20.  
  21. long int n;
  22. cin >> n;
  23.  
  24. // long int dp[n+1] = {0};
  25.  
  26. map<int, long int> mp;
  27.  
  28. // memset(map, 0, sizeof(map));
  29.  
  30. cout << solve(n, mp) << endl;
  31. return 0;
  32. }
Success #stdin #stdout 0s 4392KB
stdin
12
stdout
13