J - Two Paths Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

縦 N+1 マス、横 N+1 マスのグリッドがあります。左上のマスを (0,0) 、 (0,0) から下に i マス、右に j マス進んだマスを (i,j) とします。

マス (i,j)\ (0 \leq i,j \leq N) には A_{i,j} 個のクッキーが置かれています。

以下の操作を 2 回行います。

  • (0,0) から (N,N) までの最短経路を選び、経路上のマスにあるクッキーをすべて食べる。

ここで、 (0,0) から (N,N) までの最短経路とは、 (0,0) から縦または横に隣り合うマスに移動することを繰り返して (N,N) に到達する経路のうち、通るマスの個数が最小となるものをいいます。

各操作後、選ばれた経路上のマスにあるクッキーの個数は 0 個になります。

食べることのできるクッキーの個数の最大値を求めてください。

制約

  • 1 \leq N \leq 200
  • 0 \leq A_{i,j} \leq 10^5\ (0 \leq i,j \leq N)
  • A_{0,0} = A_{N,N} = 0
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N
A_{0,0} A_{0,1} \cdots A_{0,N}
A_{1,0} A_{1,1} \cdots A_{1,N}
\vdots
A_{N,0} A_{N,1} \cdots A_{N,N}

出力

答えを 1 行に出力せよ。

入力例 1

2
0 1 1
1 2 1
1 1 0

出力例 1

7

次のような操作で、 7 個のクッキーを食べることができます。

入力例 2

9
0 25273 26794 66830 40997 84165 45980 5843 80656 61575
87941 16379 8963 54856 64123 92048 30508 13499 63597 47707
23578 11427 93616 82855 28147 98207 67964 93434 32977 63765
51357 17333 43635 41603 984 97559 50230 50827 8012 67522
18345 2692 3452 69676 20584 88882 29554 11120 45476 1931
86655 70278 16349 93974 65638 22263 52541 55849 87916 18224
77866 70308 34053 17087 11677 84733 22083 66162 98308 2293
23288 68456 52353 44462 22185 20880 73802 87851 50133 56588
69248 59757 31414 72695 79497 30822 15037 76133 21699 45443
32105 6492 8375 65971 7857 72820 86156 24248 92835 0

出力例 2

2151343

原案 : anmichi