P4039 [AHOI2014/JSOI2014] Puzzle

JYY has recently become obsessed with jigsaw puzzles. As a computer scientist, JYY has a set of black-and-white puzzle pieces. He hopes that by concatenating them properly, the final assembled pattern will contain an all-white subrectangle with the largest possible area. JYY has $S$ puzzle pieces, numbered from $1$ to $S$. The piece numbered $i$ is a grid rectangle with $N$ rows and $W_i$ columns, where each cell is either black or white. At the beginning, JYY places these $S$ pieces on the table side by side from left to right in numerical order, forming a large $N$ by $M$ rectangle (where $M=\sum_{i=1}^S W_i$). Later, JYY discovers that by changing the concatenation order of these $S$ pieces, the area of the maximum all-white subrectangle in the resulting $N$ by $M$ rectangle can be increased. Now JYY wants to know how to arrange the pieces to obtain the largest possible all-white subrectangle. Please help him compute the optimal concatenation order.

The first line contains an integer $T$, the number of test cases. The descriptions of the test cases follow. For each test case, the first line contains two integers $S$ and $N$. Then follow $S$ groups of input, where the $i$-th group corresponds to puzzle piece $i$. In the $i$-th group, the first line contains an integer $W_i$; then $N$ lines describe a $N$-row by $W_i$-column $0/1$ matrix; if the cell at row $x$, column $y$ is $0$, then the color at that position of the piece is white, otherwise it is black.

For each test case, output one line containing a single integer ans, which denotes the area of the largest possible all-white subrectangle.

For $100\%$ of the testdata, $1\le S,N,W_i \le 10^5$, $N \times \sum W_i \le 10^5$, $1\le T\le 3$. Translated by ChatGPT 5