Can I further optimize this solution for HackerRank's “Making Candies”? My C++ solution for HackerRank's &quot;Making Candies&quot; problem, reproduced below, is as optimized as I can make it and appears similar to what others say are optimal solutions. However, six of the test cases still fail due to timing out. I would be interested to know if there are any significant opportunities to optimize my code that I missed.
I'm guessing that I'm either missing some way to simplify the computation (perhaps part of it can be precomputed and stored in a lookup table?), or there's some way to compute the answer without using a loop.
std::ios::sync_with_stdio(false);

long m, w, p, n;

std::cin &gt;&gt; m &gt;&gt; w &gt;&gt; p &gt;&gt; n;

for (long candies = 0, passes = 0, total = LONG_MAX; ; ++passes) {
    const auto production = __int128{m} * w;

    const long goal = n - candies;

    const long passes_needed = goal/production + !!(goal%production);

    const long subtotal = passes + passes_needed;

    if (passes_needed &lt;= 2) {
        std::cout &lt;&lt; subtotal;
        return 0;
    }

    if (total &lt; subtotal) {
        std::cout &lt;&lt; total;
        return 0;
    }

    total = subtotal;

    candies += production;

    if (candies &gt;= p) {
        const auto d = std::div(candies, p);

        long budget = d.quot; candies = d.rem;

        const long diff = w - m;

        if (diff &lt; 0) {
            const long w_hired = std::min(budget, -diff);

            budget -= w_hired;
            w += w_hired;
        } else if (diff &gt; 0) {
            const long m_purchased = std::min(budget, diff);

            budget -= m_purchased;
            m += m_purchased;
        }

        const long half = budget &gt;&gt; 1;

        m += half + (budget &amp; 1);
        w += half;
    }
}
Unlearn bad behavior taught by competitive coding sites
Competitive coding sites unfortunately teach some bad coding habits. You did not include your whole program, the #includes are missing for example. If you did #include &lt;bits/stdc++.h&gt;, don't.
The call to std::ios::sync_with_stdio() is only useful if your program is I/O bound, and it won't make a difference if you are just writing the final result to std::cout.
Use of integer types
__int128 is not a standard C++ type, and I don't think it is necessary at all to use it. The problem states that n is limited to \$10^{12}\$, so you only need 64-bit variables and some care to avoid values wrapping around.
A long is only guaranteed to be at least 32-bits in size. So reading in the initial values is already broken since they might be larger than that. Also, none of the values should ever become negative, so the appropriate type to use here is std::uint64_t.
Speeding up the algorithm
Yes, you can optimize your solution further. Consider the case where the desired number of candies n = 1000000000000, the cost is so high you can never buy/hire (p = n), and you start with m = 1 and w = 1. Then your loop will just do n iterations, adding 1 to candies each time.
What you should do is calculate how many iterations it would take to get enough money to buy/hire something new, and then advance that many iterations in one step. So:
const auto passes_needed_to_buy = candies &lt; p ? (p - candies) / production : 0;

Of course, if this value is more than passes_needed, then you know you will never be able to buy anything before you produced enough candy.