TopCoder

User's AC Ratio

74.1% (20/27)

Submission's AC Ratio

34.1% (56/164)

Description

你吃過「大根蘿蔔」嗎?

據說,有一種非常大根的蘿蔔,叫作「大根蘿蔔」。由於大根蘿蔔不需特別施肥就會長得肥美,因此是許多農夫愛種的作物之一。
身為農夫的你當然也不例外,挪出了$n$乘$n$($n\leq 22$)的農田方陣種大根蘿蔔。經過了兩三個月後,每個格子都長出了一個看起來超好ㄘ的大根蘿蔔(舔)。接下來的事就只剩拔起來跟賣出去了。然而,大根蘿蔔實在太大根了!

儘管外觀沒有任何異狀,但其實大根蘿蔔們在地底下已經打成一片,造成「牽一髮而動全身」的局面了:如果拔了其中一個大根蘿蔔,那麼在他左上,上,右上,右,右下,下,左下,下的八根大根蘿蔔都會因此而受損。身為一個顧品牌的好農夫,這些受損的蘿蔔當然是不能賣出去了。

你用幾十年的種菜經驗一眼看出了每根大根蘿蔔將帶給你的利潤是多少,不過你沒辦法馬上看出到底要拔哪些大根蘿蔔才能使你的總利潤最大。請寫一個程式幫助你計算你可能獲得的最大總利潤。

Input Format

第一行有一個正整數$n\leq 22$,代表農田的大小。
接下來的$n$行,每行有$n$個不超過$10^ 6$的正整數,分別代表該位置的蘿蔔可以帶來的利潤是多少。

子任務(測資) 額外限制 分數
1 (0~4) $n\leq 4$ 16
2 (5~9) $n\leq 9$ 20
3 (10~14) $n\leq 16$ 28
4 (15~19) 無限制 36

Output Format

請輸出一個正整數,代表可獲得的最大總利潤。

Sample Input

3
10 20 30
40 50 60
70 80 90

Sample Output

200

Hints

日文中的「大根(ダイコン)」指的是白蘿蔔。

Problem Source

Problem set / Description by Paupière
題目取自2015 TOI第一階段選訓第一次模擬考pA

Subtasks

For Testdata: 0 ~ 4, Score: 16
For Testdata: 5 ~ 9, Score: 20
For Testdata: 10 ~ 14, Score: 28
For Testdata: 15 ~ 19, Score: 36
No. Time Limit (ms) Memory Limit (KiB)
0 1000 131072
1 1000 131072
2 1000 131072
3 1000 131072
4 1000 131072
5 1000 131072
6 1000 131072
7 1000 131072
8 1000 131072
9 1000 131072
10 1000 131072
11 1000 131072
12 1000 131072
13 1000 131072
14 1000 131072
15 4000 131072
16 4000 131072
17 4000 131072
18 4000 131072
19 4000 131072