Login with GitHub. Nope?
修正 C++ 的程式碼在使用一定量動態記憶體後會產生 RF 的問題 @ 2019/12/6 4:45pm NeoHOJ 強勢復活中 (Open beta)
Submit  Ranklist

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

Testdata:

TestTimeMemoryScore
0-11000ms262144kb
0-21000ms262144kb
0-31000ms262144kb
1-11000ms262144kb10
1-21000ms262144kb
1-31000ms262144kb
1-41000ms262144kb
2-11000ms262144kb10
2-21000ms262144kb
2-31000ms262144kb
2-41000ms262144kb
3-11000ms262144kb10
3-21000ms262144kb
4-11000ms262144kb10
4-21000ms262144kb
51000ms262144kb10
61000ms262144kb10
75000ms262144kb10
85000ms262144kb10
95000ms262144kb10
10-15000ms262144kb10
10-25000ms262144kb