比赛 2025.10.18 评测结果 AAAAAAAAAA
题目名称 生日蛋糕 最终得分 100
用户昵称 李奇文 运行时间 0.040 s
代码语言 C++ 内存使用 3.72 MiB
提交时间 2025-10-18 10:17:31
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int N=2e4+5;
int n,m,ans=inf,ms[N],mv[N];
void dfs(int v,int s,int c,int r,int h){
	if(c==0){
		if(v==n){
			ans=min(ans,s);
		}
		return;
	}
	int hs=h;
	if(s+ms[c-1]>=ans||v+mv[c-1]>n){
		return;
	}
	if(2*(n-v)/r+s>=ans){
		return;
	}
	for(int i=r-1;i>=c;i--){
		if(c==m) s=i*i;
		hs=min((n-mv[c-1]-v)/i/i,h-1);
		for(int j=hs;j>=c;j--){
			dfs(v+i*i*j,s+2*i*j,c-1,i,j);
		}
	}
}
int main(){
	freopen("cake.in","r",stdin);
	freopen("cake.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		mv[i]=mv[i-1]+i*i*i;
		ms[i]=ms[i-1]+2*i*i;
	}
	dfs(0,0,m,n,n);
	if(ans==inf) cout<<0<<"\n";
	else cout<<ans<<"\n";
	return 0;
}