考虑对每一列进行 DP。
记 $f(i,j)$ 代表从 $(1,1)$ 走到第 $i$ 列第 $j$ 行的最大值，$sum(i,j,k)$ 代表在第 $i$ 列中第 $j$ 行到第 $k$ 行的数字之和。
那么很明显地，当 $i>1$ 时 $f(i,j)$ 一定收到 $f(i-1,k)$ 中的其中一个 $k$ 推导出。
而从 $f(i-1,k)$ 走到 $f(i,j)$，就需要这样走：$(i-1,k) ightarrow (i,k) ightarrow (i,j)$。
如果不这么走，变为 $(i-1,k) ightarrow (i-1,j) ightarrow (i,j)$ 路径的话，那你也没必要从 $(i-1,k)$ 出发求得答案，直接往右移动一格即可。
所以，转移方程为：
$$f(i,j)=max{f(i-1,k)+sum(i,min(j,k),max(j,k))}+a_{i,j}$$
处理一下各列前缀和，时间复杂度 $O(n^2m)$，可以拿到 70 分。
现在考虑如何优化：
可以观察到，$(i-1,k) ightarrow (i,k)$ 后，想到达任意一个 $(i,j)$ 只能往上或往下走。
这说明一些 $f(i,j)$ 可能与 $f(i,j-1)$ 或 $f(i,j+1)$ 的答案路径有重合部分，即 $f(i,j-1)$ 或 $f(i,j+1)$ 可能推出 $f(i,j)$。
但 DP 不能有后效性，不能在同一列又上又下，所以我们开两个数组 $g,h$，并设计策略：
$$g(i,j)=max(f(i-1,j),g(i,j-1))+a_{i,j}$$
$$h(i,j)=max(f(i-1,j),h(i,j+1))+a_{i,j}$$
$$f(i,j)=max(g(i,j),h(i,j))$$
特殊地，对于 $i>1$，$g(i,1)=f(i-1,1)+a_{i,1}$，$h(i,n)=f(i-1,n)+a_{i,n}$。
正确性显然，对于任意 $(i,j)$， $g$ 和 $h$ 至少包含一条答案最大路径。
时间复杂度 $O(nm)$，$g,h$ 数组可以降至一维重复使用。
注意开 long long。