Submission #994864

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;
using D = double;
using uint = unsigned int;

#ifdef WIN32
    #define LLD "%I64d"
#else
    #define LLD "%lld"
#endif

#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second

const int MAX = 300006;

ll n, a;
ll s[MAX + 5];

ll go(ll b)
{
    ll time = 0;
    ll speed = b;
    ll ans = n;
    while (speed <= n)
    {
        ans = min(ans, time + (n + speed - 1) / speed);
        speed *= 2;
        time += a + 2;
    }
    return ans;
}

inline ll f(ll n)
{
    return min({n, go(2 * a), go(2 * a + 1), go(2 * a + 2), go(2 * a + 3), go(a)});
}

inline ll g(ll n)
{
    pair<ll, int> ans = {n, 1};
    for (int i = 1; i <= n; i++) ans = min(ans, {s[i] + (n + i - 1) / i, i});
    if (n == 25) cout << ans.se << endl;
    return ans.fi;
}

inline ll g2(ll n)
{
    ll ans = n;
    for (int i = 1; i <= MAX; i++) ans = min(ans, s[i] + go(i));
    return ans;
}

int main()
{
    cin >> n >> a;
//     cout << f(n) << endl;
    
    s[1] = 0;
    for (int i = 2; i <= MAX; i++)
    {
        s[i] = i + a;
        for (int j = 1; j * j <= i; j++) if (i % j == 0)
        {
            s[i] = min(s[i], (i + j - 1) / j + s[j] + a);
            if (j > 1) s[i] = min(s[i], (i + (i / j) - 1) / (i / j) + s[i / j] + a);
        }
//         cout << i << ' ' << s[i] << endl;
    }
    cout << g2(n) << endl;
    
//     for (n = 1; n <= 1000; n++) if (g2(n) != g(n))
//     {
//         cout << n << ' ' << g2(n) << ' ' << g(n) << endl;
//     }
    
    return 0;
}

Submission Info

Judge Result