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

Solution (Python):
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 
        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)


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)



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

Solution (Python):
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 
        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)


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)



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

Solution (Python):
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])

Solution (Python):
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])