rt

情况说明：

截止目前，本题共5篇题解。其中四篇题解跑这组hack数据均输出错误答案，一篇题解输出正确答案但是本人本地跑了4~5s（题解作者也写了吸氧才能过，存在超时问题）。

理论依据：

由于本题最优情况到达魔王殿的方法所耗时间可能很长，精心构造完全可以卡掉正常dp。由于原题数据过水，所以时间这维（dp[i][j]中的i）开（n+10000）就能过，部分题解还存在误导性思维（不会被卡）。

hack数据说明：

考虑将n=1000分为200段，每段5个。分别落石周期分别9、8、7、5、1。每个周期都有1个时刻不落石，故最优情况是0伤通过。构造数据使得启动时刻为2500最优，每个段都是如此。此时通过时间为2500*（1000/5）*1000=5e8,可以卡掉常规dp。

其他：

由于本人能力有限，无法给出应对这组hack数据的的正解代码，只知道大部分题解无法通过这组hack数据，还望其他大佬能给出真正的正解。也希望管理员能及时处理，谢谢！

hack数据

由于hack数据过长，且无法直接发文件，为此发了生成hack数据的代码，望理解。

#include<bits/stdc++.h>
using namespace std;
int main()
{
    freopen("hacker.out","w",stdout);
    puts("1000");
    for(int i=1;i<=200;i++){
    	puts("9 1 1 1 1 1 1 0 1 1");
    	puts("8 1 1 1 1 0 1 1 1");
    	puts("7 1 1 0 1 1 1 1");
    	puts("5 1 1 0 1 1");
    	puts("1 0");
	}
	return 0;
}