Advertisement
ismaeil

E. Generate a String

Mar 16th, 2020
205
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.68 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define OO 1e18
  4.  
  5. using namespace std;
  6.  
  7. const int N = 1e7 + 500;
  8. ll Memo[N];
  9. ll n ,x ,y;
  10.  
  11. ll minTime( int n ){
  12.     if( Memo[n] != -1 ) return Memo[n];
  13.     if( n < 0 ) return +OO;
  14.  
  15.     if( n % 2 ){
  16.         ll c1 = x + minTime( n-1 );
  17.         ll c2 = y + minTime( (n-1)/2 ) + x;
  18.         return ( Memo[n] = min(c1,c2) );
  19.     }else{
  20.         ll c1 = x + minTime( n-1 );
  21.         ll c2 = y + minTime( n/2 );
  22.         return ( Memo[n] = min(c1,c2) );
  23.     }
  24. }
  25.  
  26. int main()
  27. {
  28.     cin >> n >> x >> y;
  29.     memset(Memo , -1 , sizeof(Memo));
  30.     Memo[0] = 0; Memo[1] = x;
  31.     ll Ans = minTime(n);
  32.     cout << Ans << endl;
  33.     return 0;
  34. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement