Problem : 192 - 撿肥皂

Problem Statistics

Solved Member: 30　　Submission: 127　　User Tried: 34

Statement:

hanhan 與他的好朋友 nahnah 在撿肥皂。

某天，他們到了一張充滿肥皂的地圖上。地圖可以用 n*n 的方格來表示。最初 hanhan 與 nahnah 都位於最左上角的格子上，他們各自都可以向上下左右四個方向移動，兩人都需要不繞路的走到地圖的右下角。

每個格子上都有一個值，代表第一個到這格的人會得到的肥皂數(或者負的，代表會減少)，當一個格子被其中一個人走過之後下次變不會再撿到肥皂了。由於 hanhan 以及 nahnah 不能沒有肥皂，所以一當他的肥皂數被降到 0 以下時，他會先融資來償還被減少的肥皂，假設他一共欠了 x 個肥皂，我們仍然以 -x 來表示他所擁有的肥皂數。

請你幫 hanhan 與 nahnah 各規劃一條路徑，使得他們沿路走到右下角能擁有最多的肥皂數。

Input:Output:

第一行有一個整數 n(1 ≤ n ≤ 300)，代表地圖的大小。
接下來有 n 行，每行有 n 個整數Vij ( -1000 ≤ n ≤ 1000 ) ，分別代表每個格子有多少數量的肥皂。

輸出一個數字，代表兩人走到終點之後最多總共能擁有多少肥皂。

Sample Input:Sample Output:

SAMPLE A:
1
5

SAMPLE B:
2
11 14
16 12

SAMPLE C:
3
25 16 25
12 18 19
11 13 8

SAMPLE A:
5

SAMPLE B:
53

SAMPLE C:
136

HINT:

20% 測資滿足: n ≤ 30且所有格子肥皂數皆為正數或0。
40% 測資滿足: n ≤ 30
40% 測資滿足: 所有格子的肥皂數皆為正數或0

SAMPLE C:

兩種顏色的路徑分別代表 hanhan 與 nahnah 所走的路線。

Source:

Codeforces #131

Problem Setter

Nekosyndrome

Testdata:

Test	Time	Memory	Score
0-1	1000ms	262144kb
0-2	1000ms	262144kb
0-3	1000ms	262144kb
1-1	1000ms	262144kb	10
1-2	1000ms	262144kb
1-3	1000ms	262144kb
1-4	1000ms	262144kb
2-1	1000ms	262144kb	10
2-2	1000ms	262144kb
2-3	1000ms	262144kb
2-4	1000ms	262144kb
3-1	1000ms	262144kb	10
3-2	1000ms	262144kb
4-1	1000ms	262144kb	10
4-2	1000ms	262144kb
5	1000ms	262144kb	10
6	1000ms	262144kb	10
7	5000ms	262144kb	10
8	5000ms	262144kb	10
9	5000ms	262144kb	10
10-1	5000ms	262144kb	10
10-2	5000ms	262144kb