o344. 超市掃貨 - 高中生程式解題系統

內容

廚師大黑拿到了新配方--酪梨披薩！因此廚師大黑決定去超市掃貨。

超市裡有n個酪梨攤販排成一排，第 $i$ 間酪梨攤販賣的酪梨大小為 $w_{i}$ 。

廚師大黑對酪梨獨具慧眼，他會選擇購買任意長度的一排連續攤販的酪梨，並將他們混在一起變成巨大酪梨來製作頂尖披薩，當然只選擇一間的酪梨也是可以的。

經過大黑長久以來的研究，他知道一個巨大酪梨的美味度會是被選擇的酪梨的大小總和乘上最小的酪梨，大黑想從很多個選擇中合成出能讓美味度最高的巨大酪梨，請你幫他計算出他能獲得的最高美味度是多少？

輸入說明

第一行數字 $t$ ，代表總共有 $t$ 筆測資

每筆測資中:
第一行為 $N$
第二行有 $N$ 個數字，表示每個酪梨的大小 $w_{i}$

$1 \leq N \leq 10^{6}$
$1 \leq a_{i} \leq 3 \times 10^{6}$
保證 $t$ 筆測資中 $N$ 總和 $\leq 10^{6}$

輸出說明

輸出最大的 $美味度$

範例輸入 #1

範例輸出 #1

5
10

測資資訊：

記憶體限制： 256 MB
公開測資點#0 (10%): 1.0s , <10M
公開測資點#1 (20%): 1.0s , <1M
公開測資點#2 (70%): 1.0s , <10M

提示：

子題1:
$p_{1} \leq p_{2} \leq . . . \leq p_{n}$
10分

子題2:
$t$ 筆測資中 $N$ 總和 $\leq 3000$
20分

子題3:
原題
70分

標籤:

出處:

[管理者： CGSH (快加油吧~~) ]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」