發布時間: June 27, 2024, 7:51 p.m. 最後更新時間: June 28, 2024, 7:53 a.m. 時間限制: 1000ms 記憶體限制: 128M
由於太久沒有參與社團,我(37th副社長)決定在這次社內賽向各位現任軟研社員發起挑戰,只要你成功AC本題我就會送你一份禮物喔。決定好要接受挑戰了嗎?那就請看題目!
當接下挑戰的瞬間,你被傳送到了一個競技場之中,但並沒有出現想像中的武器或防具,只有一整排的骰子、一個計分版和一個暫時紀錄器,而仔細觀察骰子後發現這是一個不可能存在的1000面骰,上面的數字是1到1000,正當你疑惑之時,角落的喇吧傳來刺耳的聲響:「歡迎來到虛擬競技場,在你面前的道具就是本挑戰會用到的所有物品,接下來請自行閱讀遊戲規則。」
說完的同時一張紙在你面前憑空出現,最上方寫著四個大字:「遊戲規則」,內容如下:
在挑戰開始時,系統會告訴你本次挑戰的難度$n$並投擲$n$顆骰子,然後告訴你依序骰出的值為何,接著你會被輸送帶運送到每顆骰子前,並對該骰子進行以下其中一個操作。
操作一:將當前骰子的數值加到暫時紀錄器並前往下一顆骰子。
操作二:將剩餘所有的骰子數值加總(含當前的骰子)得一數值$k$,且設暫時紀錄器當前數值為$m$,則將$k \times m$的值加到計分板上並將暫時紀錄器歸零。然後前往下一顆骰子。
當對最後一顆骰子做完操作後,會將暫時紀錄器中的數值加到計分板上,此時計分板的分數即為你的得分,當然,分數是越高越好。
了解遊戲規則後,你知道想通過挑戰必須算出最大值,所以請依照遊戲規則算出可能的最大值並通過挑戰吧!
第一行有一正整數$n, n \leq 10^6$,表示遊戲難度為$n$,
第二行會有$n$個正整數,保證每個數都介於$1$至$1000$,表示依序每顆骰子骰到的數值
輸出根據遊戲規則可得的最大值為何
保證答案不超過long long 範圍
4 1 2 3 4
25
4 4 3 2 1
27
5 3 2 1 2 3
36