P3231 [HNOI2013] Disinfection

Xiao T has run into big trouble while working in a biology lab. Due to a recent upgrade, his compartmentalized dish is a rectangular box with dimensions $a\times b\times c$. For convenience, it is partitioned into $a\times b\times c$ unit cubes, each of size $1\times 1\times 1$, and a unit cube is denoted by $(i, j, k)$. The dish has not been used for a long time. Now, Xiao T is required by his advisor to disinfect some of the unit cubes (each unit cube may be disinfected multiple times). Due to strict experimental requirements, he must use a specific reagent F. This reagent F is peculiar: each time he disinfects a rectangular box of size $x\times y\times z$ (consisting of $x\times y\times z$ unit cubes), it costs only $\min(x, y, z)$ units of reagent F. Since reagent F is expensive, Xiao T wants to minimize the total amount used. Please tell him the minimum total units of reagent F required.

This problem contains multiple testcases. - The first line contains a positive integer $D$, the number of testcases. - For each testcase, the first line contains three positive integers $a, b, c$, the dimensions of the dish. - Then follow $a$ blocks. For each $i=1,2,\dots,a$, read a $b$-row, $c$-column `01` matrix with entries separated by spaces. `0` means the corresponding unit cube does not need disinfection, and `1` means it needs disinfection. For example, if the $(2, 3)$ entry of the first `01` matrix is `1`, then unit cube $(1, 2, 3)$ must be disinfected.

Output $D$ lines. For each testcase, output one integer: the minimum total units of reagent F required.

Sample 1 explanation: Disinfecting regions $(1,1,3)-(2,2,4)$ and $(1,1,1)-(4,4,1)$ costs $2$ units and $1$ unit of reagent F, respectively. Constraints: For $100\%$ of the testdata, it is guaranteed that $1\le a,b,c\le 5\times 10^3$, $abc\le 5\times 10^3$, and $1\le D\le 3$. Translated by ChatGPT 5