0 Judge
Code: 0
兩年半後,柏林 1945年3月20日,元首的56歲生日,地堡中的洪普斯被巨大的聲響吵醒「是大砲」「別傻了,怎麼會有大炮呢」「你說的對,這不是空投炸彈,這就是大砲,俄國人已經來了,多好的生日禮物啊」,另一邊元首正在憤怒的和柯勒通著電話「俄國人應該已經佔領了奧多河上的一座鐵路橋,離市中心只有12公里,俄國人已經到這麼近啦,應該把德國空軍高層通通都絞死!」碰的一聲他掛斷了電話。
由於情勢急迫,元首決定實施``克勞塞維茲戰略'',也就是將大部分人員撤離柏林,但是元首他堅持留在柏林,他的幕僚們都認為柏林守不住了,紛紛勸元首離開,其中希姆萊甚至打算與艾森豪威爾進行談話「見了艾森豪威爾我是該和行納粹禮還是握手呢」雖然這是叛國罪但這種情況還真是沒其他辦法啊。
經過一番對話,官員們都認為元首已經失去理智了,他要調動的軍隊根本不存在,他在紙上談兵。的確,斯坦納的軍隊已經軍心渙散,自身難保,怎麼可能來支援元首呢?現在要斯坦那發動進攻,太荒唐了。元首這時穿著他的大衣來到地面,者裡聚集了柏林希特勒青年軍最成功的坦克射手
希特勒青年軍們按順序排成一排,準備迎接元首的到來,他們每個人身上都有一個數字,長官為了製造更好的視覺效果,想要由左到右從這些孩子中找出$k$個區段,第$i$個區段必須包含$i$個小孩,想要使的每一區段的小孩身上數字和的平方的總和最大,才能給元首最震撼的效果。換言之假設有$N$個孩子,第$i$個孩子身上的數字為$a_i$,則我們要選出$1 \leq L_1 \leq R_1 < L_2 \leq R_2<...< L_k \leq R_k \leq N$使得 $$\sum^{K}_{i=1}(\sum^{R_i}_{j=L_i}a_j)^2 \; 最大$$ 「我的元首,這小子用反坦克炮彈摧毀了兩輛俄國坦克,他叫"彼得.克蘭茲"」「那麼你就是彼得了,希望我的將軍能有你這般勇氣」,元首捏了一下彼得的臉頰,這也是元首最後一次來到地面。
第一行有兩個數字$N(1 \leq N \leq 10^5),k(1 \leq k \leq 100)$接著第二行有$N$個數字$a_1 \sim a_N(-10^6 \leq a_i \leq 10^6)$依序為青年軍身上的數字
保證$k(k+1)/2 \leq N$。
請輸出長官能得到的最大答案,元首看了會很開心的
5 2
3 4 3 7 1
116
在第一筆測資中,我們選擇(4)、(3 7)這兩段區間,滿足題目條件且可以得到最大的答案$4^2+(3+7)^2=116$
時限 | 1000ms |
---|---|
記憶體 | 65536000 bytes |