比赛 2025.10.18 评测结果 AAAAAAAAAA
题目名称 生日蛋糕 最终得分 100
用户昵称 梦那边的美好ME 运行时间 0.040 s
代码语言 C++ 内存使用 3.87 MiB
提交时间 2025-10-18 10:03:29
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
#define ll long long

ll n,m; 
ll v[21000],s[21000];
ll maxn,ans=1e9;

void dfs(ll x,ll ss,ll vv,ll lh,ll lr){
	if (x==0){
		if (vv==n) ans=min(ans,ss); 
		return;
	}
	if(ss+2*lr*(n-vv)/(lr*lr)>=ans) return;
    if(vv+v[x]>n) return;
    if(ss+s[x]>ans) return;
    for (int i=lr-1;i>=x;i--){
        if(x==m) ss=i*i;
        ll maxx;
		maxx=min(lh-1,(n-vv-v[x-1])/(i*i));
        for (int j=maxx;j>=x;j--){
			dfs(x-1,ss+2*i*j,vv+i*i*j,j,i);
		}
    }
}

int main(){
//	freopen("in.in","r",stdin);
//	freopen("out.out","w",stdout);
	freopen("cake.in","r",stdin);
	freopen("cake.out","w",stdout);
	scanf("%lld %lld",&n,&m);
	for (int i=1;i<=m;i++){
		v[i]=v[i-1]+i*i*i;
		s[i]=s[i-1]+2*i*i;
	}
	maxn=sqrt(n);
	dfs(m,0,0,n,maxn);
	printf("%lld",ans==1e9?0:ans);
	return 0;
}