记录编号	176943	评测结果	AAAAAAAAAA
题目名称	[NOI 1999]生日蛋糕	最终得分	100
用户昵称	stdafx.h	是否通过	通过
代码语言	C++	运行时间	0.438 s
提交时间	2015-08-10 15:06:08	内存使用	0.29 MiB

#include <cstdio>
#include <cmath>

int n,m,Ans=0x7fffffff;

void dfs(int p,int v,int s,int last_r,int last_h){
	if(s>=Ans||v>=n||(((n-v)<<1)/last_r+s>=Ans)){
		return;
	}
	for(int i=p;i<last_r;i++){
		for(int j=p;j<last_h;j++){
			//i = r,j = h;
			int g=i*i*j,g2=i*i,g3=i*j<<1;
			if(v+g+p-1>n||s+g3>Ans){
				break;
			}
			if(v+g+(g2-1)*(j-1)*(p-1)<n){
				continue;
			}
			if(p==1){
				if(v+g==n){
					if(m==1){
						if(g2+g3<Ans){
							Ans=g2+g3;
						}
					}
					else{
						if(s+g3<Ans){
							Ans=s+g3;
						}
					}
				}
			}
			else{
				if(p==m){
					dfs(p-1,g,g2+g3,i,j);
				}
				else{
					dfs(p-1,v+g,s+g3,i,j);
				}
			}
		}
	}
	return;
}

int main(){
	freopen("cake.in","r",stdin);
	freopen("cake.out","w",stdout);
	scanf("%d%d",&n,&m);
	int a=(int)sqrt((float)n)+1;
	dfs(m,0,0,a,n);
	if(Ans==0x7fffffff){
		Ans=0;
	}
	printf("%d",Ans);
	return 0;
}