Submission #994699

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

struct state {
    int cookie;
    int x;
    bool operator < (const state& st) const {
	if( cookie == st.cookie )
	    return x < st.x;
	return cookie < st.cookie;
    }
    bool operator > (const state& st) const {
	if( cookie >= st.cookie and x >= st.x )
	    return true;
	else
	    return false;
    }

};

ll N,A;
vector<vector<state>> t;


int main () {

    cin >> N >> A;

    assert(N <= 1000001 and A <= 1000001);

    t = vector<vector<state>>(N+A+10);

    t[0].push_back(state{0,1});
    for(int i=0; i<=N; i++) { // 時刻 N まで
	sort(t[i].begin(), t[i].end());
	reverse(t[i].begin(), t[i].end());
	state max_state = t[0][0];
	for(auto& st : t[i] ) {
	    if( st.cookie >= N ) {
		cout << i << endl;
		return 0;
	    }
	    if( t[0] > t[i] ) continue;
	    // 食べない場合
	    t[i+1].push_back(state{st.cookie + st.x,st.x});
	    // 食べた場合
	    if( i+A < N and st.cookie >= 2)
		t[i+A].push_back(state{0, st.cookie});
	}
    }
    
    return 0;
}

Submission Info

Judge Result