TopCoder

腦子裝咖哩
想像不出自己 AC 的題目是實作不出來的!雖然想像得出來也不一定可以就是了

User's AC Ratio

88.9% (48/54)

Submission's AC Ratio

51.5% (85/165)

Tags

Description

填方格遊戲除了多人模式之外,還有一種不為人所知的單人模式。

有一個$m$乘$n$的方格,每格內有一個非負整數。一開始你的分數是零。每次你都可以選一個還沒被圈過的數,把他圈起來,並且計算出你圈的數字以及與他相鄰(有公共邊)的格子中有圈的那些的總和。算出這個總和之後,將這個總和加到你的分數。繼續這個操作直到整個方格都圈完了。

作為一個單人模式遊戲,你的目標當然是使你自己的分數愈高愈好。然而這個方格有點大,所以你決定藉助程式之力幫你玩這個遊戲。

Input Format

第一行有兩個正整數$m,n\leq 10^ 3$,代表方格的大小。
接下來的$m$行,每行有$n$個小於$10^ 9$的非負整數,代表方格內填的數。

子任務(測資) 額外限制 分數
1 (0~4) $mn\leq 10$ 13
2 (5~9) $m=1, n\leq 500$ 38
3 (10~14) 無限制 49

Output Format

請輸出一個數,代表分數的最高可能值。

Sample Input 1

3 3
1 2 1
2 3 2
1 2 1

Sample Output 1

43

Hints

一種達到43分的方法:
先圈3:3分;
再圈左邊的2:5分,總計8分;
再圈上面的2:5分,總計13分;
再圈右邊的2:5分,總計18分;
再圈下面的2:5分,總計23分;
再圈左上角的1:5分,總計28分;
再圈右上角的1:5分,總計33分;
再圈右下角的1:5分,總計38分;
最後圈左下角的1:5分,總計43分。

Problem Source

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

Subtasks

No. Testdata Range Score
1 0~4 13
2 5~9 38
3 10~14 49

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 500 65536 262144 1
1 500 65536 262144 1
2 500 65536 262144 1
3 500 65536 262144 1
4 500 65536 262144 1
5 500 65536 262144 2
6 500 65536 262144 2
7 500 65536 262144 2
8 500 65536 262144 2
9 500 65536 262144 2
10 1000 65536 262144 3
11 1000 65536 262144 3
12 1000 65536 262144 3
13 1000 65536 262144 3
14 1000 65536 262144 3