P1736 Creative Way to Eat Fish

Thanks to @throusea for contributing two sets of testdata.

After returning home, the cat moved all the fish from three buckets into her large rectangular pool and began to think: what method should she use to eat the fish (the cat is so cute—she even wants to figure out a tasty way to eat fish ^_*)? She finds that viewing the big pool as a $01$ matrix ($0$ means the corresponding cell has no fish, $1$ means there is a fish) helps decide her eating strategy. In the $01$ matrix representing the pool, there are many square submatrices. If, in some square submatrix, one of its diagonals has fish in every cell and all other cells in that submatrix have no fish, then the cat can start from one end of that diagonal and, with a single suck, pull all the fish on that diagonal into her mouth. The cat is greedy, so she wants to eat as many fish as possible in one bite. Please help her compute the maximum number of fish she can eat in a single bite.

The first line contains two integers $n$ and $m$ ($n,m≥1$), describing the size of the pool. The next $n$ lines each contain $m$ numbers (each is either $0$ or $1$). Adjacent numbers are separated by spaces.

Output a single integer—the number of fish the cat can eat in one bite—on one line, followed by a newline.

For example, a $3\times 3$ square submatrix with fish only along a diagonal: ``` 1 0 0 0 1 0 0 0 1 ``` ### Constraints - For $30\%$ of the testdata, $1\le n,m\le 100$. - For $60\%$ of the testdata, $1\le n,m\le 1000$. - For $100\%$ of the testdata, $1\le n,m\le 2500$. Translated by ChatGPT 5