#B4222. [常州市程序设计小能手 2023] 积木

    ID: 11634 远端评测题 1000ms 512MiB 尝试: 0 已通过: 0 难度: 3 上传者: 标签>动态规划 DP二分2023江苏前缀和ST 表小学科创活动

[常州市程序设计小能手 2023] 积木

题目背景

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

题目描述

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

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

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

输入格式

第一行,22 个整数 nnmm 表示地面的大小。 接下来 nn 行,每行 mm 个非负整数。第 ii 行第 jj 个数表示 hi,jh_{i,j}

输出格式

一行一个整数表示答案。

3 3 
2 2 1 
3 2 2 
3 1 2
10
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
77

提示

本题共有 1212 个测试点。

测试点编号 n,mn,m hi,jh_{i,j}
131\sim3 1n,m501\le n,m\le50 0hi,j10000\le h_{i,j}\le1000
464\sim6 1n,m2001\le n,m\le200 0hi,j10000\le h_{i,j}\le 1000
797\sim9 1n,m10001\le n,m\le1000 0hi,j200\le h_{i,j}\le 20
101210\sim12 0hi,j10000\le h_{i,j}\le1000