c983: 驚殘好夢無尋處
Tags :
Accepted rate : 3人/4人 ( 75% ) [非即時]
評分方式:
Tolerant

最近更新 : 2019-04-05 22:35

Content

  $\color{black}{\space alan \space}$很愛睡覺,為了防止自己睡過頭,他每天都設定了$\color{black}{\space N \space}$個鬧鐘,都在固定的時間啟動,響一單位時間然後停止,而第$\color{black}{\space i\space}$個鬧鐘會在$\color{black}{\space t_i \space}$單位時間時響起。可是明天是放假日,$\color{black}{\space alan \space}$為了睡好睡滿睡一整天,需要關掉一些鬧鐘。他知道,如果在任意連續的$\color{black}{\space M \space}$單位時間內,存在不小於$\color{black}{\space K \space}$個鬧鐘響起,他就會醒來。

  不過這些鬧鐘可不單純,除了大眾一般的鬧鐘,其中還參雜著進化版的睡你妹鬧鐘、怪物鬧鐘、火箭鬧鐘等等棘手的鬧鐘,由於$\color{black}{\space alan \space}$平常時間的防範心太強了,這些鬧鐘就連取消設定都很費力,其中第$\color{black}{\space i\space}$個鬧鐘必須要花$\color{black}{\space p_i\space}$的力氣才能關閉。

  為了早點睡覺,$\color{black}{\space alan \space}$想要知道最少要花多少力氣才能確保明天不會被鬧鐘吵醒。

Input

輸入首行有一個正整數$\color{black}{\space T(T\leq 20) \space}$,代表共有$\color{black}{\space T \space}$筆測資。

每筆測資共有三行,首行有三個正整數$\color{black}{\space N,M,K(M\leq 10^9,K\leq 100, N\leq 1000) \space}$,代表$\color{black}{\space alan \space}$設定了$\color{black}{\space N \space}$個鬧鐘,如果在$\color{black}{\space M \space}$單位時間內有$\color{black}{\space K \space}$單位時間有鬧鐘響起,他就會醒來。

次行有$\color{black}{\space N \space}$個正整數$\color{black}{\space t_1\sim t_N(1\leq t_i\leq 10^9) \space}$,代表第$\color{black}{\space i \space}$個鬧鐘會在$\color{black}{\space t_i \space}$單位時間時響起。

末行有$\color{black}{\space N \space}$個正整數$\color{black}{\space p_1\sim p_N(1\leq p_i\leq 10^5) \space}$,代表第$\color{black}{\space i \space}$個鬧鐘必須要花$\color{black}{\space p_i \space}$的力氣才能關閉。

 

你可以假設一天有無限多單位時間,且所有$\color{black}{\space t_i \space}$兩兩相異。

Output

對於每筆測資,輸出$\color{black}{\space alan \space}$最少要花多少力氣才能確保明天不會被鬧鐘吵醒。

Sample Input
2
10 5 4
1 2 3 4 5 6 7 8 9 10
4 4 4 6 6 6 6 6 4 4
10 5 3
1 2 3 4 5 6 7 8 9 10
4 4 4 6 6 6 6 6 4 4
Sample Output
20
30
測資資訊:
記憶體限制: 512 MB
不公開 測資點#0 (18%): 1.2s , <1M
不公開 測資點#1 (9%): 1.2s , <1M
不公開 測資點#2 (17%): 1.2s , <1M
不公開 測資點#3 (15%): 1.2s , <1M
不公開 測資點#4 (20%): 1.2s , <1M
不公開 測資點#5 (21%): 1.2s , <1M
Hint :

  本題共有五組測試題組,條件限制如下所示。每一組可對應到一或多筆測試資料。

測資點$\color{black}{\space 0(18\%)\space}$:$\color{black}{\space K=2\space}$。

測資點$\color{black}{\space 1(9\%)\space}$:$\color{black}{\space N=M,\forall i,t_i=i\space}$。

測資點$\color{black}{\space 2(17\%)\space}$:$\color{black}{\space N\leq 18\space}$。

測資點$\color{black}{\space 3(15\%)\space}$:$\color{black}{\space \forall i,p_i=1\space}$。

測資點$\color{black}{\space 4\sim 5(41\%)\space}$:無特別限制。

 

改自ION Camp 2018 Final pC。

Tags:
出處:
[管理者:
baluteshih (波路特石)
]


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