比赛 2025.10.18 评测结果 TATAAAAAAA
题目名称 生日蛋糕 最终得分 80
用户昵称 LikableP 运行时间 6.278 s
代码语言 C++ 内存使用 1.88 MiB
提交时间 2025-10-18 09:35:18
显示代码纯文本
#include <cstdio>
#include <cctype>

template <typename T> T read() {
  T res = 0, f = 1;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) res = (res << 3) + (res << 1) + (ch ^ 48);
  return res * f;
}

template <typename T> void read(T& x) {
  x = read<T>();
}

template <typename T, typename ...Others> void read(T& x, Others& ...y) {
  read(x);
  read(y...);
}

void read(char* x) {
  char ch = getchar();
  for (; isspace(ch); ch = getchar());
  for (; !isspace(ch); ch = getchar()) *x++ = ch;
  *x = 0;
}

void write(__int128 x) {
  if (x < 0) x = -x, putchar('-');
  int sta[64], top = 0;
  do {
    sta[++top] = x % 10;
    x /= 10;
  } while (x);
  while (top) {
    putchar(sta[top--] ^ 48);
  }
}

template <typename T> void write(T x) {
  write((__int128)x);
}

void write(char x) {
  putchar(x);
}

void write(char* x) {
  while (*x) putchar(*x++);
}

void write(const char* x) {
  while (*x) putchar(*x++);
}

template <typename T, typename ...Others> void write(T x, Others ...y) {
  write(x);
  write(y...);
}

#include <cmath>
using namespace std;

int n, m;

int ans = 0x7fffffff;
int radius[30], height[30];
void dfs(int now, int s, int v) {
  if (s >= ans || v > n) return ;
  if (now > m) {
    if (v == n && s < ans) ans = s;
    return ;
  }

  if (now == 1) {
    for (int h = m - now + 1; h < height[now - 1]; ++h) {
      for (int r = m - now + 1; r < radius[now - 1]; ++r) {
        height[now] = h;
        radius[now] = r;
        dfs(now + 1, s + 2 * r * h + r * r, v + r * r * h);
      }
    }
  } else {
    for (int h = m - now + 1; h < height[now - 1]; ++h) {
      for (int r = m - now + 1; r < radius[now - 1]; ++r) {
        height[now] = h;
        radius[now] = r;
        dfs(now + 1, s + 2 * r * h, v + r * r * h);
      }
    }
  }
}

int main() {
  freopen("cake.in", "r", stdin);
  freopen("cake.out", "w", stdout);
  read(n, m);
  height[0] = n, radius[0] = sqrt(n);
  dfs(1, 0, 0);
  write(ans == 0x7fffffff ? 0 : ans, '\n');
  return 0;
}