Submission #1832336

---

Source Code Expand

# include <bits/stdc++.h>

# define fr first
# define sc second
# define ll long long
# define mk make_pair
# define pb push_back
# define sz(s) (int)s.size()
# define all(s) s.begin(), s.end()

using namespace std;

const int N = 2e7+10;
const ll inf = 1e15+7;

ll n, m, ans;
ll dp[N];
vector <int> v;

int main () {
    cin >> n >> m;
    ans = n;
    if(m + 1 >= n) {
        cout << n << endl;
        return 0;
    }
    for(ll i = 1; i <= m + 1; i++) {
        dp[i] = i;
        if(dp[i] >= n) {
            cout << i << endl;
            return 0;
        }
        if(i + (n + (dp[i] - 1)) / dp[i] + m < ans) ans = i + (n + (dp[i] - 1)) / dp[i] + m;
    }

    for(ll i = m + 2; i < ans && i < 20000000 ; i++) {
        if(v.empty() || dp[i - m - 1] > dp[v.back()])
            v.pb(i - m - 1);
//        while(sz(v) > 1) {
//            if(dp[v[0]] * (i - m - v[0]) <= dp[v[1]] * (i - m - v[1])) v.erase(v.begin());
//            else break;
//        }
        dp[i] = i;
        for(ll j = 0; j < sz(v); j++) {
            dp[i] = max(dp[i], dp[v[j]] * (i - m - v[j]));
        }
        if(dp[i] >= n) {
            cout << i << endl;
            break;
        }
        if(i + (n + (dp[i] - 1)) / dp[i] + m < ans) ans = i + (n + (dp[i] - 1)) / dp[i] + m;
    }
    cout << ans << endl;

}

Submission Info

Judge Result