fork download
copy 
  1. #include <iostream>
  2. #include<bits/stdc++.h>
  3. #define ll long long int
  4. using namespace std;
  5.  
  6. std::unordered_map<long long int,long long int> dp;
  7. dp[1] = 0;
  8. dp[0] = 0;
  9. ll solve(ll n, ll k, ll a, ll b){
  10. 	ll ans=0;
  11. 	ll p = n;
  12. 	if(dp[n]!=0) return dp[n];
  13. 	while(n>1){
  14. 		if(n%k != 0){
  15. 			n--;
  16. 			ans+= a;
  17. 		}
  18. 		else{
  19. 			if(solve(n/k,k,a,b)+b > solve(n-1,k,a,b)+a){
  20. 				ans+= a;
  21. 				n--;
  22. 			}
  23. 			else{
  24. 				ans+=b;
  25. 				n/=k;
  26. 			} 
  27. 		}
  28. 	}
  29. 	dp[p] = ans;
  30. 	return dp[n];
  31. }
  32.  
  33. int main() {
  34. 	// your code goes here
  35. 	ll n,k,a,b;
  36. 	cin>>n>>k>>a>>b;
  37. 	cout<<solve(n,k,a,b);
  38. 	return 0;
  39. }
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.cpp:7:1: error: ‘dp’ does not name a type
 dp[1] = 0;
 ^~
prog.cpp:8:1: error: ‘dp’ does not name a type
 dp[0] = 0;
 ^~
stdout
copy 
Standard output is empty
https://ideone.com/jnnl7O
language:
C++14 (gcc 8.3)
created:
6 years 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!