Codeforces Round #356 (Div. 1) B. Bear and Tower of Cubes

,

嘘っぽい定数倍高速化で通そうとしたが、だめでした。

problem

各辺の長さが整数の立方体をその体積の合計が$x$を越えないように貪欲に積み上げた結果の体積を$f(x)$とする。 $\max \{ (f(x), x) \mid x \le m \}$を答えよ。

solution

Recursion on $m$. For each $m$, how many times is the maximal block $a$ used, is $m \bmod a^3$ or $(m \bmod a^3) - 1$, using the monotonicity of the function.

Let $a = \max \{ a \mid a^3 \le m \}$, the maximal block. Think whether the block $a$ is used or not. Assume it is not used, the result is equivalent to one for $m’ = a^3 -1$. But under this assumption, you can also use $p - 1$ blocks of $a$ if $m = p \dot a^3 + q$, and use the same blocks for $m’ = a^3 -1$. So you always use at least $(m \bmod a^3) - 1$ blocks with side $a$, and also use blocks for $m’ = a^3-1$ or use blocks for $m’ = m \bmod a^3$ and one block of $a$.

implementation

#include <iostream>
#include <unordered_map>
#include <tuple>
#include <cmath>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
typedef long long ll;
using namespace std;
template <class T> bool setmax(T & l, T const & r) { if (not (l < r)) return false; l = r; return true; }

ll cube(ll a) { return a * a * a; }
ll cbrt(ll x) {
    ll y = pow(x, 1/3.) - 3;
    while (cube(y+1) <= x) ++ y;
    return y;
}

unordered_map<ll,pair<ll,ll> > memo;
pair<ll,ll> f(ll m) {
    if (m == 0) return { 0, 0 };
    if (memo.count(m)) return memo[m];
    ll a = cbrt(m);
    auto use = [=](ll k) {
        ll y, x; tie(y, x) = f(min(cube(a)-1, m - k * cube(a)));
        y += k;
        x += k * cube(a);
        return make_pair(y, x);
    };
    pair<ll,ll> ans = { 0, 0 };
    setmax(ans, use(m / cube(a)));
    setmax(ans, use(m / cube(a) - 1));
    return memo[m] = ans;
}

int main() {
    ll m; cin >> m;
    ll y, x; tie(y, x) = f(m);
    cout << y << ' ' << x << endl;
    return 0;
}