P2228 [HNOI2001] Yangyang Eats Cake

Yangyang is a well-known “little foodie.” He loves to eat many things, but there are also some things he doesn’t like. One day, Yangyang found a freshly baked rectangular cake at home, and the cake had all sorts of ingredients: strawberries and cheese that he likes, and walnuts that he doesn’t like. This put Yangyang in a dilemma: should he eat it or not? At this moment, his grandpa noticed Yangyang’s trouble and said: If you can follow the rules below, you may eat the cake as you wish: 1. The cake has size $n \times m$. Before eating, it should be partitioned into $n \times m$ unit cake cells. Then, for each unit cell, assign a score according to your preference: a higher score means he likes it more, and a lower score means he dislikes it more. This score is the taste value of that unit cell. 2. Each unit cell is either eaten completely or not eaten at all. 3. Any eaten cake piece must be a rectangle or a square, composed of some unit cells, and its sides must be parallel to the sides of the original cake. The taste value of a cake piece is the sum of the scores of all unit cells that form this piece. 4. The sizes of the eaten pieces are arbitrary, and the number of pieces is also arbitrary. 5. To keep the cake looking nice, all eaten pieces, in their positions within the original cake, must not be adjacent and must not overlap. The eating methods shown in Figures 1 and 2 are not allowed, while those in Figures 3 and 4 are allowed.  6. The sum of the taste values of all eaten pieces must be maximized. Grandpa’s words did not remove Yangyang’s worry, because he can only accomplish the first step and does not know how to choose the pieces. So, Yangyang asks you to help select the pieces so that the total taste value of all eaten pieces is maximized.

The first line contains two integers $n$ and $m$. The next $n$ lines contain an $n$-by-$m$ matrix. The integer in row $i$, column $j$ denotes the taste value $c$ of unit cake cell $(i, j)$.

Output a single integer: the maximum total taste value.

Constraints For $100\%$ of the testdata, it is guaranteed that $1 \le n \le 200$, $1 \le m \le 10$, $-100 \le c \le 100$. Translated by ChatGPT 5