记录编号	607747	评测结果	AAAAAAAAAA
题目名称	67.[NOI 1999]生日蛋糕	最终得分	100
用户昵称	梦那边的美好TE	是否通过	通过
代码语言	C++	运行时间	0.033 s
提交时间	2025-10-20 08:46:29	内存使用	3.85 MiB

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int ans=1e9,mins[50],minv[50],n,m; 
void dfs(int t,int s,int v,int R,int H){
	if(s+mins[t]>=ans||v+minv[t]>n)return;
	if(t==0){
		if(v==n)ans=min(ans,s);
		return;
	}
	for(int r=min(R-1,(int)sqrt(n-v));r>=t;r--){
		for(int h=min(H-1,(int)((1.0*n-v)/(r*r)));h>=t;h--){
			if (2*(n-v)/r+s>ans)continue;
			if(t==m)dfs(t-1,s+r*r+2*r*h,v+r*r*h,r,h);
			else dfs(t-1,s+2*r*h,v+r*r*h,r,h);
		}
	}
	return;
}
int main(){
	freopen("cake.in","r",stdin);
	freopen("cake.out","w",stdout);
	scanf("%d",&n);
	scanf("%d",&m);
	for(int i=1;i<=m;i++){
		mins[i]=mins[i-1]+2*i*i;
		minv[i]=minv[i-1]+i*i*i;
	}
	dfs(m,0,0,n,n);
	if(ans!=1e9)printf("%d\n",ans);
	else printf("0\n");
	return 0;
}