Submission #994824

---

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];
	int   max_cookie = t[0][0].cookie;
	int   max_x      = t[0][0].x;
	for(auto& st : t[i] ) {
	    if( st.cookie >= N ) {
		cout << i << endl;
		return 0;
	    }
	    max_cookie = max(max_cookie, st.cookie);
	    max_x = max(max_x, st.x);
//	    if( max_state.cookie > st.cookie and max_state.x > st.x ) continue;
	    if( max_cookie > st.cookie and max_x > st.x+10 ) 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