难度： 绿

算法： 深度优先搜索，剪枝

搜索大家应该都会，直接讲优化：

这题优化比较多并且有点难想全。

注：在下文中，记

$$c_i=\sum\limits_{j=1}^{j=i} j^3,s_i=\sum\limits_{j=1}^{j=i} j^2 $$

利用公式，可以得到：

$$c_i=i^2(i+1)^2\div 4,s_i=i(i+1)(2i+1)\div 6$$

优化如下：

第一部分：可行性优化

1. 当剩余的材料不足以搭建完剩余层数的时候，舍去。

实现：搭建剩余 $i$ 层最少需要 $c_i$ 的材料。检查剩余材料是否大于 $c_i$ 即可。

2. 当剩余的材料无法被用完时，舍去。

实现：记 $r$ 为当前可用最大半径，$h$ 为当前可用最大高度，可得剩余 $i$ 层最多消耗的材料数：

$$\sum\limits_{j=0}^{j=i-1} (r-j)^2(h-j)$$

变形，得：

$$\sum_{j=0}^{j=i-1} (r-j)^3-(h-r)\sum_{j=0}^{j=i-1} (r-j)^2 $$

用 $c_i$ 和 $s_i$ 表示，有：

$$c_r-c_{r-i}-(h-r)(s_r-s_{r-i})$$

如果剩余材料数大于此值，舍去即可。

第二部分：最优性优化

最基础的，每次算到可行的值的时候，更新当前答案。如果过程中发现当前结果已经大于等于答案，舍去。

但这还远远不够，继续优化：

1. 已经使用的奶油数量加上剩余层数的最少需要的奶油数量大于当前最优答案时，舍去。

实现：剩余 $i$ 层的最少奶油消耗显然为 $s_i$。直接判断即可。

2. 已经使用的奶油数量加上使用完剩余材料最少需要的奶油数量大于当前最优答案时，舍去。

实现：因为一个圆柱的体积为 $\pi R^2h$，侧面积为 $2\pi Rh$。所以圆柱体积为侧面积的 $\frac{R}{2}$ 倍。

另外，记 $r$ 为当前可用最大半径，则圆柱体积至多为侧面积的 $\frac{r}{2}$ 倍，侧面积至少为圆柱体积的 $\frac{2}{r}$ 倍。所以说，需要涂抹的奶油数量至少为剩余材料的 $\frac{2}{r}$ 倍。

3. 注意到，以上两条优化都是基于当前最优答案的。为减少算法运行时间，我们应该让它尽快得出更接近最优答案的值，以排除更多的情况。换句话说，就是让最可能得到最优解的部分先执行。

实现：显然半径应该从大至小枚举，因为这样可以使得同样的材料对应的奶油最少（因为圆柱体积为侧面积的 $\frac{R}{2}$ 倍）。高度也应该从大到小枚举，因为这样更灵活。另外，发现半径是带平方的，高度只有一次，因此高度相对稳定，循环时应该把外层循环放半径，内层放高度。（已经过验证）

综上所述，就是这个题的我能想到的所有优化，可以通过数据加强版。若有遗漏，请补充。

代码如下：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m,b=0x3f3f3f;//b最优解
ll sq_sum(ll a){return a*(a+1)*(2*a+1)/6;}
ll cu_sum(ll a){return a*(a+1)/2*a*(a+1)/2;}
ll mac(ll a,ll b,ll k){
	ll pa=cu_sum(a)-cu_sum(a-k);
	ll pb=(a-b)*(sq_sum(a)-sq_sum(a-k));
	return pa-pb;
}
void dfs(ll e,ll w,ll r,ll h,ll s){//e剩余层数 w剩余材料 r可选择最大半径 h可选择最大高度 s当前总和
	if(w<cu_sum(e)) return ;
	if(w>mac(r,h,e)) return ;
	if(s+2*sq_sum(e)>=b) return ;
	if(e==0){
		if(w!=0) return ;
		b=min(b,s);
		return ;
	}
	if(s+(2*w)/r>=b) return ;
	for(ll i=r;i>=e;i--){
		for(ll j=h;j>=e;j--){
			dfs(e-1,w-i*i*j,i-1,j-1,s+2*i*j);
		}
	}
	return ;
}
int main(){
	scanf("%lld%lld",&n,&m);
	for(ll i=n;i>=m;i--){
		for(ll j=(n/i/i);j>=m;j--){
			dfs(m-1,n-i*i*j,i-1,j-1,i*i+2*i*j);
		}
	}
	if(b!=0x3f3f3f) printf("%lld\n",b);
	else printf("-1\n");
	return 0;
}