Submission #994850

---

Source Code Expand

//嘘解法
//自明な部分点
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>
using namespace std;

int n, a;
int dp[1000001];	//dp[i] = 初期状態(x=1, 0枚)からi枚焼くまでの最小時間

int f(int i, int j) {
	return j + a + dp[(i + j - 1) / j];
}

signed main() {
	int i, j;
	
	cin >> n >> a;

	for (i = 0; i < 4; i++) { dp[i] = i; }
	
	int pos = 0;
	for (i = 4; i <= n; i++) {
		dp[i] = dp[i-1] + 1;
		
		int mini = 1145141919;
		for (j = max(1, pos - 50); j < min(i - 1, pos + 50); j++) {
			int cst = f(i, j);
			if (cst < mini) {
				mini = cst;
				pos = j;
			}
		}
		dp[i] = min(dp[i], f(i, pos));
	}
	
//	for (i = 0;i <= n; i++) cout << dp[i] << " ";
//	cout << endl;
	
	cout << dp[n] << endl;
	return 0;
}

Submission Info

Judge Result