0 Judge
Code: 0
怠惰是一件邪惡的事情,比如就像是坐在電腦螢幕前面什麼也不做的人,真是非常怠惰,因此為了讓這一些人勤勉起來,怠惰的大罪司教貝特魯吉烏斯·羅曼尼康帝決定要給這一些人一個試煉,來活動筋骨。
因為上面那個名字太長了,所以簡稱他是怠惰
。在他的老巢裡面有一個矩形的魔法陣,由一些直線與橫線分割了這一個矩形成$N\times N$個子區域,每一個區域都有不同的魔力能量,經由怠惰的權能測定完每一個區域的魔力能量後,他希望請你在一些區域上放置魔力的結晶石來吸收魔法陣的能量,使得能量的總和最大。如果一個區域的魔力能量是$K$,那在該區域放置結晶石就能吸收$K$單位的能量,不過放置結晶石會破壞原有的魔法陣陣型,使得相鄰的八個格子(上、下、左、右、左上、右上、左下、右下)區域的魔力能量流失殆盡,直接歸零,因此慎選放置的區域十分重要,比如說下方的範例中選擇粗體紅字的區域放置會是最好的。你能完成怠惰的任務嗎?$$ \begin{array}{|c|c|c|c|} \hline 50 & 8 & 50 & 20 \\ \hline 30 & \color{red}{\boldsymbol{90}} & 75 & \color{red}{\boldsymbol{40}} \\ \hline 13 & 15 & 30 & 80 \\ \hline \color{red}{\boldsymbol{60}} & 25 & \color{red}{\boldsymbol{65}} & 60 \\ \hline \end{array} $$
輸入的第一行有一個正整數$N$,代表魔法陣的大小。接下來$N$行,每行有$N$個整數,兩 個整數間都以一個空格隔開,代表魔法陣中每行區域中的魔力能量。
請輸出該魔法陣能吸收能的魔力能量總和最大值為何。
4
50 8 50 20
30 90 75 40
13 15 30 80
60 25 65 60
255
第$i$筆測資$N=max(3,i)$,各佔5分
時限 | 3000ms |
---|---|
記憶體 | 128 MB |
Tip:
。