c062: 寶藏獵人2$(Treasure2)$
Tags :
Accepted rate : 0人/0人 (0%) [非即時]
評分方式:
Tolerant

最近更新 : 2021-06-07 23:53

Content

串串:「這就是傳說中的...」

電電:「沒錯,是可以解決一切問題的神器,AC自動機。我們趕快把它拿走吧~」

串串:「等一下!你看那個戴物臺不太對勁...」

電電的手碰觸到神器的瞬間,戴物臺發出一陣吵雜聲,隨著整個空間都開始晃動,電電迅速把手伸了回去,一切又回復了平靜。

串串:「看來這不是普通的酨物臺,這是重量感測器。如果戴物臺上的重量發生大幅變動時,感測器會感應到並觸發陷阱。」

電電:「那怎麼辦?」

串串:「沒辦法了,我們把身上的東西挑一些出來,等我們拿走神器後趁感測器還沒回復時放上去,如果我們可以讓放上去的物重和神器的重量相差不超過K,應該就不會觸發陷阱。可是這些物品中還有不少很好的寶藏,這樣丟掉實在有點可惜...」

電電:「所以是要求放上去的物品的價值總和最低嗎?既然這樣,我們就用AC自動機來解決我們的煩惱吧~」

串串:「你在說甚麼?AC自動機字串演算法吧。」

 

 

 

 

Input

第一行有三個數字N,W,K,表示物品的數量、神器的重量、感測器能承受的最大差值。

第二、三行各有N個數字,分別代表物品i的重量$w_i$與價值$v_i$。

$(0 \leq N,W,K,w_i,v_i \leq 2000)$

 

Output

輸出最小的價值總和,如果無法讓放上去的物重和神器的重量相差不超過K則輸出-1。

Sample Input
// 1
5 20 1
6 20 15 8 13
100 350 50 200 120

// 2
3 10 15
6 9 15
90 100 120

// 3
5 101 0
100 50 40 20 30
100 50 40 20 30

// 4
10 20 2
9 8 1 10 12 16 6 8 18 13
15 8 17 11 10 20 30 10 19 16
Sample Output
// 1
150

// 2
0

// 3
-1

// 4
18
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (10%): 1.0s , <1K
公開 測資點#1 (10%): 1.0s , <1K
公開 測資點#2 (10%): 1.0s , <1K
公開 測資點#3 (10%): 1.0s , <1K
公開 測資點#4 (10%): 1.0s , <1M
公開 測資點#5 (10%): 1.0s , <1M
公開 測資點#6 (10%): 1.0s , <1M
公開 測資點#7 (10%): 1.0s , <1M
公開 測資點#8 (10%): 1.0s , <1M
公開 測資點#9 (10%): 1.0s , <1M
Hint :

子題一(40%):$N \leq 10$

子題二(20%):$K = 0$ 

子題三(40%):無其他限制。

Tags:
出處:
[管理者:
810848 (路過)
]


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