B4222 [常州市赛 2023] 积木

• 题号：B4222
• 难度：普及（3）
• 标签：动态规划 DP、二分、2023、江苏、前缀和、ST 表、科创活动、小学活动
• 时间限制：1000 ms
• 内存限制：512 MB
• 样例数：2
• 提交 / 通过：1282 / 561
• 抓取时间：2026-11-11T08:53:11.787Z
• 正文来源：problem.content（zh-CN）

题目背景

搬运自 http://czoj.com.cn/p/679。数据为民间数据。

题目描述

小 X 在地上玩积木，每块积木都是一个 $1\times 1\times 1$ 的正方体。地面可以看成一个 $n\times m$ 的网格，其中每一小格内都整齐地从下到上堆着若干块积木。其中第 $i$ 行第 $j$ 列中有 $h_{i,j}$ 块积木。

现在小 X 想要拿走一些积木，使得剩下来的积木正好组成一个正方体，正方体指的是长、宽、高都相同的长方体。

小 X 想问你他最少拿掉多少块积木才能使得最后剩下来的积木组成一个正方体。

输入格式

第一行，$2$ 个整数 $n$ 和 $m$ 表示地面的大小。 接下来 $n$ 行，每行 $m$ 个非负整数。第 $i$ 行第 $j$ 个数表示 $h_{i,j}$。

输出格式

一行一个整数表示答案。

样例

样例 1 输入

3 3 
2 2 1 
3 2 2 
3 1 2

样例 1 输出

10

样例 2 输入

5 5 
4 4 3 4 3
3 4 3 3 3 
3 3 1 4 4 
3 4 4 3 3 
4 3 4 4 4

样例 2 输出

77

提示

本题共有 $12$ 个测试点。

由 fetch_luogu_statements.mjs v1.0.0 自动抓取生成；原始数据见 json/B4222.json。