我看题解区的大佬都是用单调队列优化的,但本蒟蒻不信邪,写了一个 $n^2log_n$ 的代码,可是居然AC了
原来的check:

bool check(int x){
	memset(dp,128,sizeof(dp));
	dp[0]=0;
	int low=max(1ll,d-x),high=d+x;
	for(int i=1;i<=n;i++){
		for(int j=i-1;j>=0;j--){
			if(w[j]+high<w[i]) break;
			if(w[j]+low>w[i]) continue;
			dp[i]=max(dp[i],dp[j]+p[i]);
			if(dp[i]>=k) return 1;
		}
	}return 0;
}

但我把这个内层循坏的遍历顺序从 $i-1到0$ 改成了 $0到i-1$ ,按道理来说是不会错的,但再交一遍,就会TLE,只有50pts 修改后的check:

bool check(int x){
	memset(dp,128,sizeof(dp));
	dp[0]=0;
	int low=max(1ll,d-x),high=d+x;
	for(int i=1;i<=n;i++){
		for(int j=0;j<i;j++){
			if(w[j]+high<w[i]) continue;
			if(w[j]+low>w[i]) break;
			dp[i]=max(dp[i],dp[j]+p[i]);
			if(dp[i]>=k) return 1;
		}
	}return 0;
}

这说明数据是不是比较水