[常州市赛 2023] 积木

Luogu

IDLGB4222

Time1000ms

Memory512MB

DifficultyP3

动态规划 DP二分2023江苏前缀和ST 表科创活动小学活动

小 X 在地上玩积木，每块积木都是一个 $1\times 1\times 1$ 的正方体。地面可以看成一个 $n\times m$ 的网格，其中每一小格内都整齐地从下到上堆着若干块积木。其中第 $i$ 行第 $j$ 列中有 $h_{i,j}$ 块积木。现在小 X 想要拿走一些积木，使得剩下来到积木组成一个正方体，正方体指的是长、宽、高都相同的长方体。小 X 想问你他最少拿掉多少块积木才能使得最后剩下来的积木组成一个正方体。 ## Input 第一行，$2$ 个整数 $n$ 和 $m$ 表示地面的大小。接下来 $n$ 行，每行 $m$ 个非负整数。第 $i$ 行第 $j$ 个数表示 $h_{i,j}$。 ## Output 一行一个整数表示答案。 [samples] ## Background 搬运自 <http://czoj.com.cn/p/679>。数据为民间数据。 ## Note 本题共有 $12$ 个测试点。 |测试点编号|$n,m$|$h_{i,j}$| |:-:|:-:|:-:| |$1\sim3$|$1\le n,m\le50$|$0\le h_{i,j}\le1000$| |$4\sim6$|$1\le n,m\le200$|$0\le h_{i,j}\le 1000$| |$7\sim9$|$1\le n,m\le1000$|$0\le h_{i,j}\le 20$| |$10\sim12$|$1\le n,m\le1000$|$0\le h_{i,j}\le1000$|

Samples

Input #1

Output #1

Input #2

Output #2

API Response (JSON)

{
  "problem": {
    "name": "[常州市赛 2023] 积木",
    "description": {
      "content": "小 X 在地上玩积木，每块积木都是一个 $1\\times 1\\times 1$ 的正方体。地面可以看成一个 $n\\times m$ 的网格，其中每一小格内都整齐地从下到上堆着若干块积木。其中第 $i$ 行第 $j$ 列中有 $h_{i,j}$ 块积木。 现在小 X 想要拿走一些积木，使得剩下来到积木组成一个正方体，正方体指的是长、宽、高都相同的长方体。 小 X 想问你他最少拿掉多少块积木才能使",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGB4222"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "小 X 在地上玩积木，每块积木都是一个 $1\\times 1\\times 1$ 的正方体。地面可以看成一个 $n\\times m$ 的网格，其中每一小格内都整齐地从下到上堆着若干块积木。其中第 $i$ 行第 $j$ 列中有 $h_{i,j}$ 块积木。\n\n现在小 X 想要拿走一些积木，使得剩下来到积木组成一个正方体，正方体指的是长、宽、高都相同的长方体。\n\n小 X 想问你他最少拿掉多少块积木才能使...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments