比赛 2025.10.18 评测结果 AAAAAAAWAA
题目名称 生日蛋糕 最终得分 90
用户昵称 彭欣越 运行时间 1.059 s
代码语言 C++ 内存使用 3.70 MiB
提交时间 2025-10-18 10:15:27
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100010;
ll n,m,a[N],b[N],ans=1e18+10;
void dfs (int idx,ll r,ll h,ll s,ll v) {
	if (idx==0) {
		if (v==n) ans=min(ans,s);
		return;
	}
	if (s+a[idx-1]>ans) return;
	if ((n-v)/r/2+s>=ans)  return; 
	if (v+b[idx-1]>n) return;
	for (int i=r-1;i>=idx;i--) {
		if (idx==m) s=i*i;
		int t=min(h-1,(n-b[idx-1]-v)/i/i); 
		for (int j=t;j>=idx;j--) dfs(idx-1,i,j,s+2*i*j,v+i*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++) {
    	a[i]=a[i-1]+2*i*i;
        b[i]=b[i-1]+i*i*i;
	}
	dfs(m,n,n,0,0);
	cout << ans <<endl;
    return 0;
}