比赛 |
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;
}