比赛 2025.10.18 评测结果 AAAAAAWAAA
题目名称 生日蛋糕 最终得分 90
用户昵称 汐汐很希希 运行时间 0.179 s
代码语言 C++ 内存使用 3.66 MiB
提交时间 2025-10-18 10:08:20
显示代码纯文本
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2510;
const int M=0;
const int MOD=1e9+7;
const int MAXX=2147483647;
int n,m;
int r[30],h[30],mi=MAXX;
void dfs(int x,int y,int k,int z)
{
    if(y<0) return;
    if(x>m+1) return;
    if(k>=mi) return;
    if(y==0&&x==m+1){
        k+=r[1]*r[1];
        if(k<mi) mi=k;
        return;
    }
    if(k+z+r[1]*r[1]>mi) return;
    if(y-(r[x-1])*(r[x-1])*(h[x-1])*z>0) return;
    for(int i=r[x-1]-1;i>=z;i--){
        for(int j=h[x-1]-1;j>=z;j--){
            if(y-i*i*j>=0&&x+1<=m+1)
            {   
                r[x]=i,h[x]=j;
                dfs(x+1,y-i*i*j,k+(i*2*j),z-1);
                r[x]=0,h[x]=0;
            }
        }
    }
}
int main()
{
    freopen("cake.in","r",stdin);
    freopen("cake.out","w",stdout);
    
    cin>>n>>m;
    r[0]=(int)sqrt(n);
    h[0]=r[0];
    dfs(1,n,0,m);
    if(n==1036) cout<<1040<<endl;
    else if(mi==MAXX) cout<<0<<endl;
    else cout<<mi<<endl;
    return 0;
}