f832: 隕石 (Meteorite)
Tags : greedy
Accepted rate : 46人/59人 ( 78% ) [非即時]
評分方式:
Tolerant

最近更新 : 2021-05-07 20:45

Content

問題敘述
有 N 顆隕石即將要掉落在 OI 國,所幸科學家預測隕石的著陸位置是在杳無人煙的荒野上,即使著陸也不會造成傷亡。科學家發現這一批隕石上面含有一種稀有而且 OI 國迫切需要的物質,因而想要去提煉。然而,如果在隕石撞進地表後再去開挖,需要花費很長的時間;在唯一的解法是要使用一種特殊的隕石捕捉器在空中攔截,然後帶回實驗室。


已知 OI 國有 M 個隕石捕捉器,每一個捕捉器只能使用一次,而且只可捕捉一個隕石。第 i 個捕捉器可以捕捉一個重量不超過Ci單位重的隕石。N 顆隕石的重量已由科學家估算出來,重量分別為 W1 ~ WN
一個隕石上稀有物質的含量正比於該隕石的重量,所以 OI 國 的目標是要最大化捕捉隕石的重量總和。給定隕石重量以及捕捉器的容量,請寫一個程式計算 OI 國的科學家最多能捕捉到重量總和為多少的隕石。

Input

第一行有兩個正整數 N 和 M 分別表示有 N 顆隕石 和 M 個隕石捕捉器。

第二行有 N 個正整數 W1, …, WN,整數後以一個空白隔開,表示每一個隕石的重量。第三行有 M 個正整數 C1, …, CM,整數後以一個空白隔開,第 i 個數表示每一個隕石捕捉器最多可以捕捉到重量為 Ci的隕石 。

1 ≤ N, M ≤ 105

1 ≤ W1 , …, WN ≤ 109

1 ≤ C1, …, C≤ 109

Output

請輸出一行正整數,表示科學家最大能捕捉隕石的重量總和。答案有可能會超過 32 位元有號整數的範圍。

Sample Input #1
4 3
23 45 67 99 
46 67 100 
Sample Output #1
211
Sample Input #2
4 4
1 8 5 7 
1 9 6 6 
Sample Output #2
14
測資資訊:
記憶體限制: 256 MB
公開 測資點#0 (5%): 1.0s , <1K
公開 測資點#1 (5%): 1.0s , <1K
公開 測資點#2 (5%): 1.0s , <1K
公開 測資點#3 (5%): 1.0s , <1K
公開 測資點#4 (5%): 1.0s , <1M
公開 測資點#5 (5%): 1.0s , <1M
公開 測資點#6 (5%): 1.0s , <1M
公開 測資點#7 (5%): 1.0s , <1M
公開 測資點#8 (5%): 1.0s , <1M
公開 測資點#9 (5%): 1.0s , <1M
公開 測資點#10 (5%): 1.0s , <1M
公開 測資點#11 (5%): 1.0s , <1M
公開 測資點#12 (5%): 1.0s , <1M
公開 測資點#13 (5%): 1.0s , <10M
公開 測資點#14 (5%): 1.0s , <1M
公開 測資點#15 (5%): 1.0s , <1M
公開 測資點#16 (5%): 1.0s , <10M
公開 測資點#17 (5%): 1.0s , <1M
公開 測資點#18 (5%): 1.0s , <1M
公開 測資點#19 (5%): 1.0s , <1M
Hint :

評分說明
第一組 20 分 N , M ≤ 10, N = M, W 1 , …, W N ≤ 102
第二組 40 分 N , M ≤ 103
第三組 40 分 無特別限制

Tags:
greedy
出處:
TOI練習賽202012潛力組第一題 [管理者:
fire5386 (皮卡丘)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」