#679. [CZOI2023 G] 积木

[CZOI2023 G] 积木

题目描述

小 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 个测试点,每个测试点 1010 分。

对于所有测试点 1n,m1000,0hi,j10001\le n,m\le 1000,0\le h_{i,j}\le 1000

对于测试点 131\sim 31n,m501\le n,m\le 50

对于测试点 464\sim 61n,m2001\le n,m\le 200

对于测试点 797\sim 91n,m10001\le n,m\le 1000,0hi,j200\le h_{i,j}\le 20