Problem:


				Max Score: $600$ Points 

Problem Statement

					Sigma and his brother Sugim are in the $H \times W$ grid. They wants to buy some souvenirs. 

					Their start position is upper-left cell, and the goal position is lower-right cell. 

					Some cells has a souvenir shop. At $i$-th row and $j$-th column, there is $a_{i, j}$ souvenirs. 

					In one move, they can go left, right, down, and up cell. 

					But they have little time, so they can move only $H+W-2$ times. 

					They wanted to buy souvenirs as many as possible, but they had no computer, so they couldn't get the maximal numbers of souvenirs. 

					Write a program and calculate the maximum souvenirs they can get, and help them. 

Input

						The input is given from standard input in the following format. 

$H \ W$
$a_{1, 1} \ a_{1, 2} \ \cdots \ a_{1, W}$
$a_{2, 1} \ a_{2, 2} \ \cdots \ a_{2, W}$
$\vdots \ \ \ \ \ \ \ \ \ \ \vdots \ \ \ \ \ \ \ \ \ \ \vdots$
$a_{H, 1} \ a_{H, 2} \ \cdots \ a_{H, W}$

Output

Print the maximum number of souvenirs they can get.

Constraints

$1 \le H, W \le 200$

$0 \le a_{i, j} \le 10^5$

Subtasks

						Subtask 1 [ 50 points ] 

The testcase in the subtask satisfies $1 \le H \le 2$.

						Subtask 2 [ 80 points ] 

The testcase in the subtask satisfies $1 \le H \le 3$.

						Subtask 3 [ 120 points ] 

The testcase in the subtask satisfies $1 \le H, W \le 7$.

						Subtask 4 [ 150 points ] 

The testcase in the subtask satisfies $1 \le H, W \le 30$.

						Subtask 5 [ 200 points ] 

There are no additional constraints.

Sample Input 1

3 3
1 0 5
2 2 3
4 2 4

Sample Output 1

21

					The cell at $i$-th row and $j$-th column is denoted $(i, j)$. 

					In this case, one of the optimal solution is this:

Sigma moves $(1, 1) -> (1, 2) -> (1, 3) -> (2, 3) -> (3, 3)$.

Sugim moves $(1, 1) -> (2, 1) -> (3, 1) -> (3, 2) -> (3, 3)$.

					Then, they can get $21$ souvernirs. 

Sample Input 2

6 6
1 2 3 4 5 6
8 6 9 1 2 0
3 1 4 1 5 9
2 6 5 3 5 8
1 4 1 4 2 1
2 7 1 8 2 8

Sample Output 2

97

			Writer : square1001



Sample input:
3 3
1 0 5
2 2 3
4 2 4


Sample output:
21

Submission status: Wrong Answer

Solution code:
#tle -solution
import copy
def main():
    H,W = map(int,input().split())
    data = [[0]+list(map(int,input().split())) for i in range(H)]
    a = copy.deepcopy(data)
    for i in range(H):
        for j in range(1,W+1):
            data[i][j] += data[i][j-1]
            
    #dp[height][left][right] assert 1<=height<=H, 1<=left<right<=W
    
    dp = [[[0]*(W+1) for j in range(W+1)] for i in range(H+1)]   



    #initializaton : height is 1.

    for i in range(1,W+1):            
            for j in range(i,W+1):
                dp[1][i][j] =data[0][j]

    for height in range(2,H+1):
        for i in range(1,W+1):
            for j in range(i+1,W+1):              
                dp[height][i][j] = max(max(dp[height-1][i][k] +data[height-1][j]-data[height-1][k-1] for k in range(i+1,j+1))+a[height-1][i],dp[height][i][j])
                dp[height][i][j] = max(max(dp[height-1][l][j]+data[height-1][i]-data[height-1][l-1] for l in range(1,i+1))+a[height-1][j],dp[height][i][j])
                if i > 1:
                    dp[height][i][j] = max(dp[height][i-1][j],dp[height][i][j-1],dp[height][i][j])
    

    ans = max(dp[H][i][i+1]+data[-1][W] -data[-1][i+1] for i in range(1,W))
    
    print(ans)
    return


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#tle -solution 10**8 order
def main():
    H,W = map(int,input().split())
    data = [[0]+list(map(int,input().split())) for i in range(H)]
    for i in range(H):
        for j in range(1,W+1):
            data[i][j] += data[i][j-1]
            
    #dp[height][left][right] assert 1<=height<=H, 1<=left<right<=W
    
    dp = [[[0]*(W+1) for j in range(W+1)]for i in range(H+1)]   
    H_dp = [[[0]*(W+1) for j in range(W+1)] for i in range(H+1)]
    W_dp = [[[0]*(W+1) for j in range(W+1)] for   i in range(H+1)]


    #initializaton : height is 1.

    for i in range(1,2):            
            for j in range(i+1,W+1):
                dp[1][i][j] =data[0][j]

    for height in range(2,H+1):
        for i in range(1,W+1):
            for j in range(i+1,W+1):
                dp[height][i][j] = max(max(dp[height-1][i][k] +data[height-1][j]-data[height-1][k-1] for k in range(i+1,j+1))+data[height-1][i]-data[height-1][i-1],dp[height][i][j])
                dp[height][i][j] = max(max(dp[height-1][l][j]+data[height-1][i]-data[height-1][l-1] for l in range(1,i+1))+data[height-1][j]-data[height-1][j-1],dp[height][i][j])
    

    ans = max(dp[H][i][i+1]+data[-1][W] -data[-1][i+1] for i in range(1,W))
    
    print(ans)
    return


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#tle -solution 10**8 order
def main():
    H,W = map(int,input().split())
    data = [[0]+list(map(int,input().split())) for i in range(H)]
    for i in range(H):
        for j in range(1,W+1):
            data[i][j] += data[i][j-1]
            
    #dp[height][left][right] assert 1<=height<=H, 1<=left<right<=W
    
    dp = [[[0]*(W+1) for j in range(W+1)]for i in range(H+1)]   
    H_dp = [[[0]*(W+1) for j in range(W+1)] for i in range(H+1)]
    W_dp = [[[0]*(W+1) for j in range(W+1)] for   i in range(H+1)]


    #initializaton : height is 1.

    for i in range(1,2):            
            for j in range(i+1,W+1):
                dp[1][i][j] =data[0][j]

    for height in range(2,H+1):
        for i in range(1,W+1):
            for j in range(i+1,W+1):
                dp[height][i][j] = max(max(dp[height-1][i][k] +data[height-1][j]-data[height-1][k-1] for k in range(i+1,j+1))+data[height-1][i]-data[height-1][i-1],dp[height][i][j])
                dp[height][i][j] = max(max(dp[height-1][l][j]+data[height-1][i]-data[height-1][l-1] for l in range(1,i+1))+data[height-1][j]-data[height-1][j-1],dp[height][i][j])
    

    ans = dp[H][W-1][W]
    
    print(ans)
    return


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#atcoder problem solving


#problem name --> お土産購入計画2

#tle -solution 10**8 order
def main():
    H,W = map(int,input().split())
    data = [[0]+list(map(int,input().split())) for i in range(H)]
    for i in range(H):
        for j in range(1,W+1):
            data[i][j] += data[i][j-1]
            
    #dp[height][left][right] assert 1<=height<=H, 1<=left<right<=W
    
    dp = [[[0]*(W+1) for j in range(W+1)]for i in range(H+1)]   
    H_dp = [[[0]*(W+1) for j in range(W+1)] for i in range(H+1)]
    W_dp = [[[0]*(W+1) for j in range(W+1)] for   i in range(H+1)]


    #initializaton : height is 1.

    for i in range(1,W+1):
            for j in range(i+1,W+1):
                dp[1][i][j] =data[0][j]

    for height in range(2,H+1):
        for i in range(1,W+1):
            for j in range(i+1,W+1):
                dp[height][i][j] = max(max(dp[height-1][i][k] +data[height-1][j]-data[height-1][k-1] for k in range(i+1,j+1))+data[height-1][i]-data[height-1][i-1],dp[height][i][j])
                dp[height][i][j] = max(max(dp[height-1][l][j]+data[height-1][i]-data[height-1][l-1] for l in range(1,i+1))+data[height-1][j]-data[height-1][j-1],dp[height][i][j])
    

    ans = dp[H][W-1][W]
    
    print(ans)
    return


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
A = [list(map(int, input().split())) for i in range(H)]

memo = {(W+H-2, H-2, H-1): 0}
def dfs(c, p, q):
    if (c, p, q) in memo:
        return memo[c, p, q]
    res = 0
    if c+1-H < p < q < H:
        res = max(res, dfs(c+1, p, q))
    if c+1-H < p+1 < q < H:
        res = max(res, dfs(c+1, p+1, q))
    if c+1-H < p < q+1 < H:
        res = max(res, dfs(c+1, p, q+1))
    if c+1-H < p+1 < q+1 < H:
        res = max(res, dfs(c+1, p+1, q+1))
    memo[c, p, q] = res = res + A[c-p][p] + A[c-q][q]
    return res
print(dfs(1, 0, 1) + A[0][0] + A[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
#tle -solution
def main():
    H,W = map(int,input().split())
    data = [[0]+list(map(int,input().split())) for i in range(H)]
    for i in range(H):
        for j in range(1,W+1):
            data[i][j] += data[i][j-1]
            
    #dp[height][left][right] assert 1<=height<=H, 1<=left<right<=W
    
    dp = [[[0]*(W+1) for j in range(W+1)] for i in range(H+1)]   



    #initializaton : height is 1.

    for i in range(1,W+1):            
            for j in range(i,W+1):
                dp[1][i][j] =data[0][j]

    for height in range(2,H+1):
        for i in range(1,W+1):
            for j in range(i+1,W+1):              
                dp[height][i][j] = max(max(dp[height-1][i][k] +data[height-1][j]-data[height-1][k-1] for k in range(i+1,j+1))+data[height-1][i]-data[height-1][i-1],dp[height][i][j])
                dp[height][i][j] = max(max(dp[height-1][l][j]+data[height-1][i]-data[height-1][l-1] for l in range(1,i+1))+data[height-1][j]-data[height-1][j-1],dp[height][i][j])
                if i > 1:
                    dp[height][i][j] = max(max(dp[height-1][u][v] + data[height-1][i]-data[height-1][u-1] + data[height-1][j]-data[height-1][v-1] for u in range(1,i+1) for v in range(i+1,j+1)),dp[height][i][j])
    

    ans = max(dp[H][i][i+1]+data[-1][W] -data[-1][i+1] for i in range(1,W))
    
    print(ans)
    return


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
A = [list(map(int, input().split())) for i in range(H)]
if H == 1 or W == 1:
    print(sum(map(sum, A)))
    exit(0)

memo = [{} for i in range(W+H)]
def calc(c, p, q):
    yield 0
    if c+1-H < p:
        yield dfs(c+1, p, q)
        if q+1 < W:
            yield dfs(c+1, p, q+1)
    if p+1 < q:
        yield dfs(c+1, p+1, q)
    if q+1 < W:
        yield dfs(c+1, p+1, q+1)
def dfs(c, p, q):
    mc = memo[c]
    if (p, q) in mc:
        return mc[p, q]
    mc[p, q] = r = max(calc(c, p, q)) + A[c-p][p] + A[c-q][q]
    return r
print(dfs(1, 0, 1) + A[0][0] + A[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
A = [list(map(int, input().split())) for i in range(H)]
if H == 1 or W == 1:
    print(sum(map(sum, A)))
    exit(0)

memo = [{} for i in range(W+H)]
def dfs(c, p, q):
    mc = memo[c]
    if (p, q) in mc:
        return mc[p, q]
    res = 0
    if c+1-H < p:
        res = max(res, dfs(c+1, p, q))
        if q+1 < W:
            res = max(res, dfs(c+1, p, q+1))
    if p+1 < q:
        res = max(res, dfs(c+1, p+1, q))
    if q+1 < W:
        res = max(res, dfs(c+1, p+1, q+1))
    mc[p, q] = res = res + A[c-p][p] + A[c-q][q]
    return res
print(dfs(1, 0, 1) + A[0][0] + A[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
A = [list(map(int, input().split())) for i in range(H)]
if H == 1 or W == 1:
    print(sum(map(sum, A)))
    exit(0)

memo = {(W+H-2, H-2, H-1): 0}
def dfs(c, p, q):
    if (c, p, q) in memo:
        return memo[c, p, q]
    res = 0
    if c+1-H < p:
        res = max(res, dfs(c+1, p, q))
        if q+1 < W:
            res = max(res, dfs(c+1, p, q+1))
    if p+1 < q:
        res = max(res, dfs(c+1, p+1, q))
    if q+1 < W:
        res = max(res, dfs(c+1, p+1, q+1))
    memo[c, p, q] = res = res + A[c-p][p] + A[c-q][q]
    return res
print(dfs(1, 0, 1) + A[0][0] + A[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
A = [list(map(int, input().split())) for i in range(H)]
if H == 1 or W == 1:
    print(sum(map(sum, A)))
    exit(0)

memo = {(W+H-2, H-2, H-1): 0}
def dfs(c, p, q):
    if (c, p, q) in memo:
        return memo[c, p, q]
    res = 0
    if c+1-H < p < q < W:
        res = max(res, dfs(c+1, p, q))
    if c+1-H < p+1 < q < W:
        res = max(res, dfs(c+1, p+1, q))
    if c+1-H < p < q+1 < W:
        res = max(res, dfs(c+1, p, q+1))
    if c+1-H < p+1 < q+1 < W:
        res = max(res, dfs(c+1, p+1, q+1))
    memo[c, p, q] = res = res + A[c-p][p] + A[c-q][q]
    return res
print(dfs(1, 0, 1) + A[0][0] + A[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
A = [list(map(int, input().split())) for i in range(H)]
if H == 1 or W == 1:
    print(sum(map(sum, A)))
    exit(0)

memo = {(W+H-2, H-2, H-1): 0}
def dfs(c, p, q):
    if (c, p, q) in memo:
        return memo[c, p, q]
    res = 0
    if c+1-H < p < q < W:
        res = max(res, dfs(c+1, p, q))
    if c+1-H < p+1 < q < W:
        res = max(res, dfs(c+1, p+1, q))
    if c+1-H < p < q+1 < W:
        res = max(res, dfs(c+1, p, q+1))
    if c+1-H < p+1 < q+1 < W:
        res = max(res, dfs(c+1, p+1, q+1))
    memo[c, p, q] = res = res + A[c-p][p] + A[c-q][q]
    return res
print(dfs(1, 0, 1) + A[0][0] + A[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int,input().split())
src = [list(map(int,input().split())) for i in range(H)]

dp = [[[0 for ex in range(W)] for sx in range(W)] for xy in range(H+W-1)]
dp[0][0][0] = src[0][0]
for xy in range(H+W-2):
    n = min(xy+1,H,W,H+W-xy-1)
    sx0 = max(0,xy-H+1)
    for sx in range(sx0, sx0+n):
        for ex in range(sx, sx0+n):
            sy,ey = xy-sx, xy-ex
            if sx < W-1 and ex < W-1:
                gain = src[sy][sx+1]
                if sx+1 != ex+1: gain += src[ey][ex+1]
                if dp[xy+1][sx+1][ex+1] < dp[xy][sx][ex] + gain:
                    dp[xy+1][sx+1][ex+1] = dp[xy][sx][ex] + gain
            if sx < W-1 and ey < H-1:
                gain = src[sy][sx+1]
                if sx+1 != ex: gain += src[ey+1][ex]
                if dp[xy+1][sx+1][ex] < dp[xy][sx][ex] + gain:
                    dp[xy+1][sx+1][ex] = dp[xy][sx][ex] + gain
            if sy < H-1 and ex < W-1:
                gain = src[sy+1][sx]
                if sx != ex+1: gain += src[ey][ex+1]
                if dp[xy+1][sx][ex+1] < dp[xy][sx][ex] + gain:
                    dp[xy+1][sx][ex+1] = dp[xy][sx][ex] + gain
            if sy < H-1 and ey < H-1:
                gain = src[sy+1][sx]
                if sx != ex: gain += src[ey+1][ex]
                if dp[xy+1][sx][ex] < dp[xy][sx][ex] + gain:
                    dp[xy+1][sx][ex] = dp[xy][sx][ex] + gain

print(dp[-1][-1][-1])

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int,input().split())
src = [list(map(int,input().split())) for i in range(H)]

dp = [[[0 for ex in range(W)] for sx in range(W)] for xy in range(H+W-1)]
dp[0][0][0] = src[0][0]
for xy in range(H+W-2):
    n = min(xy+1,H,W,H+W-xy-1)
    sx0 = max(0,xy-H+1)
    for sx in range(sx0, sx0+n):
        for ex in range(sx, sx0+n):
            sy,ey = xy-sx, xy-ex
            assert 0 <= sx < W
            assert 0 <= ex < W
            assert 0 <= sy < H
            assert 0 <= ey < H
            if sx < W-1 and ex < W-1:
                gain = src[sy][sx+1]
                if sx+1 != ex+1: gain += src[ey][ex+1]
                dp[xy+1][sx+1][ex+1] = max(dp[xy+1][sx+1][ex+1], dp[xy][sx][ex] + gain)
            if sx < W-1 and ey < H-1:
                gain = src[sy][sx+1]
                if sx+1 != ex: gain += src[ey+1][ex]
                dp[xy+1][sx+1][ex] = max(dp[xy+1][sx+1][ex], dp[xy][sx][ex] + gain)
            if sy < H-1 and ex < W-1:
                gain = src[sy+1][sx]
                if sx != ex+1: gain += src[ey][ex+1]
                dp[xy+1][sx][ex+1] = max(dp[xy+1][sx][ex+1], dp[xy][sx][ex] + gain)
            if sy < H-1 and ey < H-1:
                gain = src[sy+1][sx]
                if sx != ex: gain += src[ey+1][ex]
                dp[xy+1][sx][ex] = max(dp[xy+1][sx][ex], dp[xy][sx][ex] + gain)

print(dp[-1][-1][-1])

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from heapq import heappop, heappush
import itertools

"""
・最小費用流。流量2を流せばよい。
・頂点xをx_in,x_outに拡張。x_inからx_outにcapacity1で、価値 a と 0 の辺を貼る
・このままだと最大化問題になっているので、辺のコストをX - a_{ij}とする感じで
"""

class MinCostFlow:
    """
    最小費用流。負辺がないと仮定して、BellmanFordを省略している。
    """
    def __init__(self, N, source, sink):
        self.N = N
        self.G = [[] for _ in range(N)]
        self.source = source
        self.sink = sink
        
    def add_edge(self, fr, to, cap, cost):
        n1 = len(self.G[fr])
        n2 = len(self.G[to])
        self.G[fr].append([to, cap, cost, n2])
        self.G[to].append([fr, 0, -cost, n1])

    def MinCost(self, flow, negative_edge = False):
        if negative_edge:
            raise ValueError
        N = self.N; G = self.G; source = self.source; sink = self.sink
        INF = 10 ** 18
        prev_v = [0] * N; prev_e = [0] * N # 経路復元用
        H = [0] * N # potential
        mincost=0
        while flow:
            dist=[INF] * N
            dist[source]=0
            q = [source]
            mask = (1 << 20) - 1
            while q:
                x = heappop(q)
                dv = (x >> 20); v = x & mask
                if dist[v] < dv:
                    continue
                if v == sink:
                    break
                for i,(w,cap,cost,rev) in enumerate(G[v]):
                    dw = dist[v] + cost + H[v] - H[w]
                    if (not cap) or (dist[w] <= dw):
                        continue
                    dist[w] = dw
                    prev_v[w] = v; prev_e[w] = i
                    heappush(q, (dw << 20) + w)
            if dist[sink] == INF:
                raise Exception('No Flow Exists')
            # ポテンシャルの更新
            for v,d in enumerate(dist):
                H[v] += d
            # 流せる量を取得する
            d = flow; v = sink
            while v != source:
                pv = prev_v[v]; pe = prev_e[v]
                cap = G[pv][pe][1]
                if d > cap:
                    d = cap
                v = pv
            # 流す
            mincost += d * H[sink]
            flow -= d
            v = sink
            while v != source:
                pv = prev_v[v]; pe = prev_e[v]
                G[pv][pe][1] -= d
                rev = G[pv][pe][3]
                G[v][rev][1] += d
                v = pv
        return mincost

H,W = map(int,readline().split())
A = list(map(int,read().split()))

N = 2 * H * W + 2
source = N-2; sink = N-1

G = MinCostFlow(N,source,sink)
add = G.add_edge
X = 10 ** 6

# スタート地点
add(fr=source, to=0, cap=2, cost=0)
# ゴール
add(2*H*W-1, sink, 2, 0)

# x_in to x_out
for x,a in enumerate(A):
    add(x+x,x+x+1,1,X) # とらない
    add(x+x,x+x+1,1,X - a) # とる

# 左から右への辺
for i,j in itertools.product(range(H),range(W-1)):
    x = W * i + j; y = x + 1
    add(x+x+1,y+y,1,0)
# 上から下への辺
for i,j in itertools.product(range(H-1),range(W)):
    x = W * i + j; y = x + W
    add(x+x+1,y+y,1,0)

cost = G.MinCost(2)

# 1点通るごとに、X - costになっている。2人合わせて、(H+W-1) * 2個のXが足されている

answer = 2 * (H+W-1) * X -cost
print(answer)

Submission status: Accepted

Solution code:
h,w=map(int,raw_input().split())
a=[map(int,raw_input().split()) for _ in xrange(h)]
dp=[[[0]*(h+1) for _ in xrange(w+1)] for _ in xrange(h+1)]

for i in xrange(h):
    for j in xrange(w):
        for k in xrange(h):
            if i+j-k<=-1 or i+j-k>=w:
                continue
            if i==k:
                dp[i+1][j+1][k+1]=max(dp[i][j+1][k+1],dp[i+1][j][k+1],dp[i][j+1][k],dp[i+1][j][k])+a[i][j]
            else:
                dp[i+1][j+1][k+1]=max(dp[i][j+1][k+1],dp[i+1][j][k+1],dp[i][j+1][k],dp[i+1][j][k])+a[i][j]+a[k][i+j-k]

print(dp[h][w][h])

Submission status: Runtime Error

Solution code:
H, W = map(int, input().split())
A = [list(map(int, input().split())) for i in range(H)]
if H <= 2 or W <= 2:
    print(sum(map(sum, A)))
    exit(0)

def solve(A, W, H):
    S = {(0, 1): 0}
    for c in range(1, H-1):
        T = {}
        for p, q in S:
            v = S[p, q] + A[c-p][p] + A[c-q][q]
            T[p, q] = max(T.get((p, q), 0), v)
            if p+1 < q:
                T[p+1, q] = max(T.get((p+1, q), 0), v)
            if q+1 < W:
                T[p, q+1] = max(T.get((p, q+1), 0), v)
                T[p+1, q+1] = max(T.get((p+1, q+1), 0), v)
        S = T
    return S
B = [e[::-1] for e in A[::-1]]
S0 = solve(A, W, H)
S1 = solve(B, H, W)
print(A[0][0] + A[-1][-1] + max(S0[p, q] + S1[H-1-q, H-1-p] + A[H-1-p][p] + A[H-1-q][q] for p, q in S0))

Submission status: Runtime Error

Solution code:
H, W = map(int, input().split())
A = [list(map(int, input().split())) for i in range(H)]
if H <= 2 or W <= 2:
    print(sum(map(sum, A)))
    exit(0)

def solve(A, W, H):
    S = {(0, 1): 0}
    for c in range(1, H-1):
        T = {}
        for p, q in S:
            v = S[p, q] + A[c-p][p] + A[c-q][q]
            T[p, q] = max(T.get((p, q), 0), v)
            if p+1 < q:
                T[p+1, q] = max(T.get((p+1, q), 0), v)
            if q+1 < W:
                T[p, q+1] = max(T.get((p, q+1), 0), v)
                T[p+1, q+1] = max(T.get((p+1, q+1), 0), v)
        S = T
        print(c, S)
    return S
B = [e[::-1] for e in A[::-1]]
S0 = solve(A, W, H)
S1 = solve(B, H, W)
print(A[0][0] + A[-1][-1] + max(S0[p, q] + S1[H-1-q, H-1-p] + A[H-1-p][p] + A[H-1-q][q] for p, q in S0))

Submission status: Runtime Error

Solution code:
H, W = map(int, input().split())
A = [list(map(int, input().split())) for i in range(H)]

memo = {(W+H-2, H-2, H-1): 0}
def dfs(c, p, q):
    if (c, p, q) in memo:
        return memo[c, p, q]
    res = 0
    if c+1-W < p < q < H:
        res = max(res, dfs(c+1, p, q))
    if c+1-W < p+1 < q < H:
        res = max(res, dfs(c+1, p+1, q))
    if c+1-W < p < q+1 < H:
        res = max(res, dfs(c+1, p, q+1))
    if c+1-W < p+1 < q+1 < H:
        res = max(res, dfs(c+1, p+1, q+1))
    memo[c, p, q] = res = res + A[c-p][p] + A[c-q][q]
    return res
print(dfs(1, 0, 1) + A[0][0] + A[-1][-1])