TopCoder

User's AC Ratio

96.6% (28/29)

Submission's AC Ratio

35.0% (48/137)

Description

你用了俄羅斯娃娃許了願,而這些俄羅斯娃娃也為了救出最底層的娃娃而實現了願望。然而為了救出娃娃,有些娃娃的法力變為負的了。

厭煩了上一種許願方法的你,決定再試試另一個坊間流傳的許願方法。為此,你隨機地將這些俄羅斯娃娃排成了$n$乘$n$的方陣($n\leq 500$)並搬來一個超級無敵大的俄羅斯娃娃。這個俄羅斯娃娃雖然足夠大,但每次只能裝入某個矩形內的所有俄羅斯娃娃(也可以不放任何娃娃)。而為了讓願望比較容易成真,你當然希望大俄羅斯娃娃所裝的俄羅斯娃娃法力總和最大。

要注意,這種許願方法是不允許移動已隨機放好的俄羅斯娃娃們。如果你移動了,法力會和你產生排斥,讓你變成俄羅斯娃娃。而你只有一次將俄羅斯娃娃裝入大俄羅斯娃娃的機會,所以你希望藉由程式幫助你找出最好的許願方法。

Input Format

第一行有一個正整數$n$,代表娃娃方陣的邊長。
接下來有$n$行,每行有$n$個數,代表娃娃的法力大小。
保證法力大小都在int範圍。

子任務(測資) 額外限制 分數
1 (0~4) $n\leq 100$ 50
2 (5~9) 無限制 50

Output Format

請輸入一個數,代表大俄羅斯娃娃裝的娃娃們法力總和的最大值。

Sample Input

3
1 -1 2
-8 3 -9
3 -2 3

Sample Output

4

Hints

範例測資中,讓法力總和最大的其中一種方法是把第三排的俄羅斯娃娃裝進大俄羅斯娃娃中。

Problem Source

Problem set / Description by Paupière
建國中學105學年度校內第一次模擬賽pD

Subtasks

For Testdata: 0 ~ 4, Score: 50
For Testdata: 5 ~ 9, Score: 50
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 500 65536 65536
1 500 65536 65536
2 500 65536 65536
3 500 65536 65536
4 500 65536 65536
5 500 65536 65536
6 500 65536 65536
7 500 65536 65536
8 500 65536 65536
9 500 65536 65536