记录编号	607739	评测结果	AAAAAAAAAA
题目名称	67.[NOI 1999]生日蛋糕	最终得分	100
用户昵称	我常常追忆未来	是否通过	通过
代码语言	C++	运行时间	0.035 s
提交时间	2025-10-20 07:40:58	内存使用	3.86 MiB

#include<bits/stdc++.h>
using namespace std;
const int N=1008;
int n,m,ans=1e9+7,h[N],r[N];
int mins[N],minv[N];
void dfs(int u,int v,int s){
	if(s>ans){
		return;
	}
	if(v+minv[u]>n){
		return;
	}
	if(s+mins[u]>ans){
		return;
	}
	if(u==0){
		if(v==n){
			ans=min(ans,s);
		}
		return;
	}
	for(int i=min(r[u+1]-1,(int)sqrt(n-v));i>=u;i--){
		for(int j=min(h[u+1]-1,(int)((double)(n-v)/i/i));j>=u;j--){
			if(v+i*i*j>n){
				continue;
			}
			if(2*(n-v)/i+s>ans){
				continue;
			}
			h[u]=j,r[u]=i;
			if(u==m){
				dfs(u-1,v+i*i*j,s+2*i*j+i*i);
			}
			else{
				dfs(u-1,v+i*i*j,s+2*i*j);
			}
			h[u]=0,r[u]=0;
		}
	}
}
int main(){
	scanf("%d%d",&n,&m);
	h[m+1]=n,r[m+1]=n;
	for(int i=1;i<=m;i++){
		minv[i]=minv[i-1]+i*i*i;
		mins[i]=mins[i-1]+2*i*i;
	}
	mins[m]+=m*m;
	dfs(m,0,0);
	if(ans==1e9+7){
		printf("0");
	}
	else{
		printf("%d\n",ans);
	}

	return 0;
}