Submission #994216

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define DEBUG 1000000
struct st{
  ll d,x,p;
  st(ll d,ll x,ll p):d(d),x(x),p(p){};
};
int main(){
  ll n,a;
  cin>>n>>a;
  if(n>DEBUG||a>DEBUG) {
    cout << n << endl;
    return 0;
  }
  ll i,j,k,inf=1<<28,g[n+1];
  map<int,ll> gm[n+1];
  fill(g,g+n+1,inf);
  k=n;
  queue<st> q;
  gm[1][0]=0;
  q.push(st(0,0,1));
  while(!q.empty()){
    st s=q.front();q.pop();
    //cout << s.d << ":" << s.x << ":" << s.p << endl;
    if(s.x>n||s.p>n) continue;
    if((gm[s.p].find(s.x)!=gm[s.p].end()&&gm[s.p][s.x]<s.d)&&s.d) continue;
    
    if(gm[s.p].find(s.x)!=gm[s.p].end()){
      gm[s.p][s.x]=min(gm[s.p][s.x],s.d);
    }else gm[s.p][s.x]=s.d;

    g[s.p]=min(g[s.p],gm[s.p][s.x]);
    if(g[s.p]>=k) continue; 
    k=min(k,g[s.p]+(n-1)/s.p+1);
    if(s.d+1<k) q.push(st(s.d+1,s.x+s.p,s.p));
    if(s.d+a<k&&s.x) q.push(st(s.d+a,0,s.x));
    
  }
  cout << k << endl;
  return 0;
}

Submission Info

Judge Result