Submission #994859

---

Source Code Expand

#include <algorithm>
#include <cassert>
#include <cctype>
#include <cstdlib>
#include <cmath>
#include <cstdio>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <utility>

#define reps(i,f,n) for(int i=f; i<int(n); ++i)
#define rep(i,n) reps(i,0,n)

using namespace std;

typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;

const ll INF = 1001001001001001ll;

signed main()
{
    ll n, a;
    cin >> n >> a;
    
    if(a <= 1000000){
        vi dp(100000 * 45);
        rep(t, dp.size()) dp[t] = t;
        
        int mae = -1;
        
        reps(t, 2, dp.size()){
            reps(s, mae, t-a){
               ll tmp = dp[s] * (t-s-a);
               if(tmp > dp[t]){
                   mae = s;
                   dp[t] = tmp;
               }
            }
            
            if(dp[t] >= n){
                cout << t << endl;
                return 0;
            }
            
            // cout << "dp[" << t << "] = " << dp[t] << ", mae = " << mae << endl;
        }
    }
    else{
        vi dp(2000000, INF);
        dp[1] = 0;
        
        reps(i, 1, dp.size()){
            for(int j=i*2; j<dp.size(); j+=i){
                dp[j] = min(dp[j], dp[i] + (i/j) + a);
            }
        }
        
        ll ans = INF;
        reps(i, 1, dp.size()){
            ans = min(ans, dp[i] + (n+i-1)/i);
        }
        
        cout << ans << endl;
    }
}

Submission Info

Judge Result