c500: Problem A: AEWE-645的傷害
標籤 :
通過比率 : 94% (16 人 / 17 人 ) (非即時)
評分方式:
Strictly

最近更新 : 2018-02-01 12:37

內容

(時間限制: 3.0000秒)

兔吉是香噴噴學園的程式高手,他這個賽季在神的程式領域八戰中連拿八次第一,堪稱程式界的鬼神。不過最重要的一個比賽,就是全國高中程式競賽(Informational High, IH),他要想辦法維持住香噴噴學園在IH的不敗紀錄。可是他萬萬沒想到,他遇到一個敵人,來自京城的拜見隊隊長阿翔,阿翔有打敗他祕密武器。在IH開賽前一天,阿翔跟兔吉說:「我知道你非常討厭使用AEWE-645這型號滑鼠的參賽者,坐在你的右邊。因為你暗戀的泉田就是被坐在右邊使用AEWE-645這種滑鼠的新開學長追走的,造成你每次比賽都非常在意滑鼠,只要有使用這款滑鼠的參賽者,坐在你右邊,你的程式能力就會大幅下降。我已經偷偷混入k隻滑鼠進入IH競賽了,今年勝利的是我們拜見隊。」

今年IH比賽時,所有競賽座位是排成一直線(從場地左側排至右側,編號從1號開始),共有n個座位(1號~n號,n<=10000000),現在兔吉知道自己坐在從左側算來的第m號位置。並且知道安排在會場的k隻全部不同顏色的AEWE-645滑鼠( 顏色1號~到顏色k號),由於AEWE-645滑鼠的顏色不同,對兔吉的傷害也不同。因此,不同顏色的AEWE-645滑鼠,安排在兔吉右邊,每距離他右邊1個座位,就會對兔吉造成不同的傷害值dk。由於需要安排別家廠牌的滑鼠,為了公平起見,大會規定此品牌的滑鼠必需安排在距離f個座位。因為香噴噴學園是IH競賽去年的冠軍,根據大會規定香噴噴學園可以安排AEWE-645滑鼠要分配給哪幾台電腦,因為兔吉忙著去準備競賽無法思考,所以請聰明的你,幫他排AEWE-645型號的滑鼠,要分配給哪幾部電腦,可使兔吉在比賽時,所受到的傷害最小,請你根據他所給的資料來安排。(請注意,兔吉自己用AEWE-645滑鼠,不會受傷害,而全部AEWE-645滑鼠都必須安排完。)

輸入說明

測試資料中,會有多筆兔吉給的賽場可能座位安排與滑鼠個數資料,每筆測資都有兩行,第一行有四個數字,分別代表 k, n, m, f。而第二行的k個數字,就是代表k隻不同顏色的滑鼠安排在兔吉右邊的位置,每距離兔吉1個位置,所帶給兔吉的傷害值dk所有滑鼠都 AEWE-645滑鼠都能並且都要擺進比賽中

輸出說明

對於每一組測資,請輸出安排滑鼠位置後,讓兔吉受傷的最小傷害值。

範例輸入
4 10 5 3
1 2 3 4
4 10 5 1
1 2 3 4
範例輸出
9
0
測資資訊:
記憶體限制: 64 MB
不公開 測資點#0 (25%): 3.0s , <1M
不公開 測資點#1 (25%): 3.0s , <1M
不公開 測資點#2 (25%): 3.0s , <1M
不公開 測資點#3 (25%): 3.0s , <1M
提示 :
標籤:
出處:
新北市 TOI 程式競賽初選試題 [編輯:
snail (蝸牛)
]


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