探險家鯊魚正在一條名為「肉丸之路」的直線上進行探險，這條路上由左至右放著 N（1≤N≤200000）顆肉丸，依序編號為 1 至 N（即第 i 顆肉丸的座標為 i ），每顆肉丸都有其對應的飽足度 Wi （0≤Wi≤M）以及獨一無二的美味度 Di（1≤Di≤108）。
鯊魚很餓，但鯊魚媽媽怕鯊魚吃太多撐死所以她規定鯊魚只能吃到飽足度 M（1≤M≤500）（也就是說，鯊魚吃的所有肉丸的飽足度總和不能超過 M）。而為了展現對頂級美食的尊重，鯊魚在規劃好要吃哪些肉丸後，必須遵守一個移動規則：「依據選定肉丸的美味度由大到小，依序前往各個肉丸的座標進行享用」。鯊魚初始位於座標 0，他會先移動到美味度最高的已選肉丸座標並將其吃掉；接著再移動到美味度次高的已選肉丸座標……以此類推，直到吃完所有選定的肉丸為止。
為了吃一顆已選的肉丸，鯊魚必須從原位置 A 游到肉丸所在位置 B，然而，路過美味的肉丸而不能吃簡直就是惡夢！（可能因為肉丸不在享用計畫內，或者它的美味度較低、還沒輪到被吃）因此，對於他游過而沒有吃的肉丸，鯊魚會產生等同於該肉丸美味度的傷心值，值得注意的是，若鯊魚在往返游動中多次路過同一顆當下未被吃掉的肉丸，傷心值會重複累積。
鯊魚希望在遵守鯊魚媽媽定下的規則的前提下，最大化滿足度，滿足度即為選定的肉丸總美味度，但鯊魚媽媽想要知道她的規則會不會讓鯊魚太傷心，因此她希望知道在此條件下，鯊魚的傷心值總和是多少。請你寫一個程式，計算出鯊魚在最大化滿足度的條件下，傷心值總和是多少。
第一行包含兩個正整數 N 與 M，分別代表肉丸的總數與鯊魚媽媽定下的飽足度上限值。
第二行包含 N 個非負整數 W1, W2, …, Wn，依序代表座標 1 到 N 處肉丸的飽足度。
第三行包含 N 個正整數 D1, D2, …, Dn，依序代表座標 1 到 N 處肉丸的美味度（保證所有 Di 皆不重複）。
請輸出一個整數，代表鯊魚的傷心值總和。題目保證在最大化滿足度的條件下傷心值總和唯一。
3 10 4 5 5 100 40 50
40
4 10 1 1 1 1 30 100 40 80
70
不公開 測資點#0 (5%): 0.5s , <10M
不公開 測資點#1 (5%): 0.5s , <10M
不公開 測資點#2 (5%): 0.5s , <10M
不公開 測資點#3 (5%): 0.5s , <10M
不公開 測資點#4 (5%): 0.5s , <10M
不公開 測資點#5 (5%): 0.5s , <10M
不公開 測資點#6 (5%): 0.5s , <10M
不公開 測資點#7 (5%): 0.5s , <1M
不公開 測資點#8 (5%): 0.5s , <1M
不公開 測資點#9 (5%): 0.5s , <1M
不公開 測資點#10 (5%): 0.5s , <10M
不公開 測資點#11 (5%): 0.5s , <10M
不公開 測資點#12 (5%): 0.5s , <10M
不公開 測資點#13 (5%): 0.5s , <10M
不公開 測資點#14 (5%): 0.5s , <10M
不公開 測資點#15 (5%): 0.5s , <1M
不公開 測資點#16 (5%): 0.5s , <1M
不公開 測資點#17 (5%): 0.5s , <1M
不公開 測資點#18 (5%): 0.5s , <1K
不公開 測資點#19 (5%): 0.5s , <1K
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||