Boss, Thirsty
Contest: Codeforces Round 977 (Div. 2, based on COMPFEST 16 - Final Round)
Difficulty rating: 2500
Tags: dp, greedy, implementation

Pak Chanek has a friend who runs a drink stall in a canteen. His friend will sell drinks for $$$n$$$ days, numbered from day $$$1$$$ to day $$$n$$$. There are also $$$m$$$ types of drinks, numbered from $$$1$$$ to $$$m$$$.

The profit gained from selling a drink on a particular day can vary. On day $$$i$$$, the projected profit from selling drink of type $$$j$$$ is $$$A_{i, j}$$$. Note that $$$A_{i, j}$$$ can be negative, meaning that selling the drink would actually incur a loss.

Pak Chanek wants to help his friend plan the sales over the $$$n$$$ days. On day $$$i$$$, Pak Chanek must choose to sell at least one type of drink. Furthermore, the types of drinks sold on a single day must form a subarray. In other words, in each day, Pak Chanek will select $$$i$$$ and $$$j$$$ such that $$$1 \leq i \leq j \leq m$$$. Then all types of drinks between $$$i$$$ and $$$j$$$ (inclusive) will be sold.

However, to ensure that customers from the previous day keep returning, the selection of drink types sold on day $$$i$$$ ($$$i>1$$$) must meet the following conditions:

- At least one drink type sold on day $$$i$$$ must also have been sold on day $$$i-1$$$.
- At least one drink type sold on day $$$i$$$ must not have been sold on day $$$i-1$$$.

The daily profit is the sum of the profits from all drink types sold on that day. The total profit from the sales plan is the sum of the profits over $$$n$$$ days. What is the maximum total profit that can be achieved if Pak Chanek plans the sales optimally?

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 1000$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$; $$$3 \leq m \leq 2 \cdot 10^5$$$; $$$n \cdot m \leq 2 \cdot 10^5$$$) — the number of rows and columns in a grid.

The next $$$n$$$ lines of each test case contain $$$m$$$ integers each, where the $$$i$$$-th line contains the integers $$$A_{i,1} A_{i,2}, \ldots, A_{i,m}$$$ ($$$-10^9 \leq A_{i,j} \leq 10^9$$$) — project profits of each drink type on the $$$i$$$-th day.

It is guaranteed that the sum of $$$n \cdot m$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, output a single integer: the maximum profit that Pak Chanek can achieve.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
Here is Pak Chanek's optimal plan:

- On day $$$1$$$, Pak Chanek sells drink types $$$1$$$ to $$$3$$$. Generating a profit of $$$79+20+49 = 148$$$.
- On day $$$2$$$, Pak Chanek sells drink types $$$2$$$ to $$$4$$$. Generating a profit of $$$9+109+24 = 142$$$
- On day $$$3$$$, Pak Chanek sells drink types $$$1$$$ to $$$6$$$. Generating a profit of $$$185$$$.

So, the total profit of Pak Chanek's plan is $$$148 + 142 + 185 = 475$$$.

Example input:
1
3 6
79 20 49 5 -1000 500
-105 9 109 24 -98 -499
14 47 12 39 23 50

Example output:
475

Editorial:
We can see it as a grid of square tiles, consisting of $$$n$$$ rows and $$$m$$$ columns. Consider a single row. Instead of looking at the $$$m$$$ tiles, we can look at the $$$m+1$$$ edges between tiles, including the leftmost edge and the rightmost edge. We number the edges from $$$0$$$ to $$$m$$$ such that tile $$$j$$$ ($$$1\leq j\leq m$$$) is the tile between edge $$$j-1$$$ and edge $$$j$$$.
For a single row $$$i$$$, choosing a segment of tiles is equivalent to choosing two different edges $$$l$$$ and $$$r$$$ ($$$0\leq l<r\leq m$$$) as the endpoints of the segment, which denotes choosing the tiles from $$$l+1$$$ to $$$r$$$. For each edge $$$j$$$, we can precompute a prefix sum $$$\text{pref}[j]=A_{i,1}+A_{i,2}+\ldots+A_{i,j}$$$. That means, choosing edges $$$l$$$ and $$$r$$$ yields a profit of $$$\text{pref}[r]-\text{pref}[l]$$$.
Let's say we've chosen edges $$$l'$$$ and $$$r'$$$ for row $$$i-1$$$ and we want to choose two edges $$$l$$$ and $$$r$$$ for row $$$i$$$ that satisfies the problem requirement. We want to choose a continuous segment that includes at least one chosen tile and at least one unchosen tile from the previous row. A chosen tile that is adjacent to an unchosen tile only appears at the endpoints of the previous segment. That means, to satisfy the requirement, the new segment must strictly contain at least one endpoint of the previous segment. More formally, at least one of the following conditions must be satisfied:
• $$$l<l'<r$$$
• $$$l<r'<r$$$
Knowing that, we can see that when going from one row to the next, we only need the information for one of the two endpoints, not both.
We can solve this with dynamic programming from row $$$1$$$ to row $$$n$$$. For each row, we find the optimal profit for each $$$l$$$ and the optimal profit for each $$$r$$$. We do those two things separately. For each row $$$i$$$, define the following things:
• $$$\text{dpL}[i][l]$$$: the optimal profit for the first $$$i$$$ rows if the left endpoint of the last segment is $$$l$$$.
• $$$\text{dpR}[i][r]$$$: the optimal profit for the first $$$i$$$ rows if the right endpoint of the last segment is $$$r$$$.
Let's say we've calculated all values of $$$\text{dpL}$$$ and $$$\text{dpR}$$$ for row $$$i-1$$$ and we want to calculate for row $$$i$$$. Let $$$l$$$ and $$$r$$$ be the left and right endpoints of the new segment respectively. Let $$$p$$$ be one of the endpoints of the previous segment. Then it must hold that $$$l<p<r$$$, which yields a maximum profit of $$$-\text{pref}[l]+\max(\text{dpL}[i-1][p],\text{dpR}[i-1][p])+\text{pref}[r]$$$.
Let's calculate all values of $$$\text{dpR}$$$ first for row $$$i$$$. For each $$$r$$$, we want to consider all corresponding triples $$$(l,p,r)$$$ and find the maximum profit among them. In order to do that, we do three steps:
• Make a prefix maximum of $$$-\text{pref}[l]$$$.
• Then, for each $$$p$$$, we add $$$\max(\text{dpL[i-1][p]},\text{dpR}[i-1][p])$$$ with the maximum value of $$$-\text{pref}[l]$$$ for all $$$0\leq l<j$$$. And then we make a prefix maximum of those values.
• Then, for each $$$r$$$, the value of $$$\text{dpR}[i][r]$$$ is $$$\text{pref}[r]$$$ added by the maximum value for the previous calculation for each $$$p$$$ from $$$0$$$ to $$$r-1$$$.
We do the same thing for $$$\text{dpL}$$$ but we use suffix maxmiums instead.
After doing all that for every row from $$$1$$$ to $$$n$$$, we find the maximum value of $$$\text{dpL}$$$ and $$$\text{dpR}$$$ in the last row to get the answer.
Time complexity of each test case: $$$O(nm)$$$