提出 #67772349

---

ソースコード 拡げる

H, W = map(int, input().split())
A = []
for _ in range(H):
    A.append(list(map(int, input().split())))

P = list(map(int, input().split()))

# S[i][j] = (x, y) ; x -> 過去のお金のマイナス値の最大 (絶対値として最小),
#                    y -> 今の所持金
S = [[None] * W for _ in range(H)]
S[0][0] = (A[0][0] - P[0], A[0][0] - P[0])

for k in range(1, H+W-1): # 1 日目から H+W-2 日目まで
    for hi in range(1, k+1): # hi, wi の全範囲
        if hi > H:
            continue

        wi = k + 1 - hi
        if wi > W:
            continue

        # 右へ行く
        if wi != W: # 端っこでなければ
            x, y = S[hi-1][wi-1] # 今の (x, y)
            y += (A[hi-1][wi] - P[k]) # 右に行ったときの, 現在のお金
            if x > y: # お金が, 過去の金額より小さくなっていたら, 値を更新
                x = y

            if S[hi-1][wi] == None: # まだ訪問してなければ
                S[hi-1][wi] = (x, y) # そのまま書き込む
            else: # 訪問していれば
                x_cur, y_cur = S[hi-1][wi] # 今の値
                if x_cur < x: # 今の値よりも, x が大きい (マイナスなら, 絶対として小さい) なら
                    S[hi-1][wi] = (x, y) # 値を更新
                
        # 下へ行く (右へ行く時と同様)
        if hi != H:
            x, y = S[hi-1][wi-1]
            y += (A[hi][wi-1] - P[k])
            if x > y:
                x = y

            if S[hi][wi-1] == None:
                S[hi][wi-1] = (x, y)
            else:
                x_cur, y_cur = S[hi][wi-1]
                if x_cur < x:
                    S[hi][wi-1] = (x, y)

# print(S)
x, _ = S[H-1][W-1] # 最終地点で, お金の値をチェック
if x > 0: # 正の値なら, 過去に一度も負になったことがないので, ゼロにする
    x = 0

print(-x) # 符号をつけて出力

提出情報

ジャッジ結果