Codeforces Round #356 (Div. 2) D. Bear and Tower of Cubes

Problem Statement:
Codeforces Round #356 (Div. 2) D. Bear and Tower of Cubes

Summary:
Given m < 10^15, find the largest (k, X) such that a[1]+a[2]+...+a[k] = X <= m, each a[i] is a perfect cube, and for a given X,  a[i] is the largest cube such that a[1] + ... + a[i] <= X.



Solution:
The editorial has a very nice solution: http://codeforces.com/blog/entry/45310. I am discussing the solution here mostly for my own future reference.
The idea in the solution is a complete search on choices of cubes. Let Max(m) be the recursion that returns k the maximum length of cube tower that can be constructed and X the maximum sum we can get from such tower such that X <= m.
Let a be an integer such that a^3 <= m < (a+1)^3. The first cube can be of length 1 to a. If the length of the first cube is chosen to be a, then we recursively compute Max(m-a^3).
Otherwise, if the first cube is chosen to be a-1, then current X must be at most a^3-1, which means the next recursion call is Max((a-1)^3-1-(a-1)^3). We do not consider any other cases below s < a-1, since Max(S) <= Max(T) where S < T, and choosing s < a-1 will lead us to call Max with smaller argument then if we choose a-1.
Hence Max(m) = max{Max(m-a^3) + (1,  a^3),  Max(a^3-1-(a-1)^3) + (1, (a-1)^3)}.

Another cool thing about this solution is that we can make bounds on the runtime complexity:
Since each call Max(m) will lead to call to Max(m-a^3) and Max(a^3-1-(a-1)^3), where m is a polynomial of degree 3 in terms of a. Notice that both m-a^3 and a^3-1-(a-1)^3 has degree at most 2 in terms of a, hence there is a reduction from m = O(a^3) to O(a^2) which means each call on Max reduces its argument by power of 2/3. From here we can empirically compute k that reduces m = 10^15 to 1, and we get k somewhere around k = 18 to 19 steps, and hence by expanding the recursion tree we know that Max() is called at most 2^(k+1)-1 times or at most 2^20-1.

Code:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <utility>
#include <map>
using namespace std;
int GetK(int64_t m) {
  int lo=1,hi=100000, mid;
  while(lo<=hi) {
    mid = (lo+hi)/2;
    int64_t cur = 1LL*mid*mid*mid;
    if (cur < m) {
      lo = mid+1;
    } else {
      hi = mid-1;
    }
  }
  int64_t cur = 1LL*lo*lo*lo;
  if (cur == m) return lo;
  return hi;
}

pair<int64_t, int64_t> MaxCubes(int64_t m) {
  if (m <= 0) return {0, 0};
  int k = GetK(m);
  int64_t k3 = 1LL*k*k*k;
  int64_t k_13 = 1LL*(k-1)*(k-1)*(k-1);
  pair<int64_t, int64_t> s = MaxCubes(m-k3);
  pair<int64_t, int64_t> t = MaxCubes(k3-1LL-k_13);
  s.first += 1;
  s.second += k3;
  t.first += 1;
  t.second += k_13;
  if (s.first == t.first) {
    return s.second > t.second ? s : t;
  }
  return s.first > t.first ? s : t;
}
int main(){
  int64_t m;
  cin >> m;
  pair<int64_t,int64_t> p = MaxCubes(m);
  cout << p.first << " " << p.second << endl;
  return 0;
}