b377. 大魔王的怒火 - Zero1 Online Judge System

Content

大魔王經過上次「大魔王要炸了」的事件之後，發現原來身為異世界勇者的您，竟然已經在轟炸之前就逃出了新手村，決定要立即對異世界發動進一步的大範圍無差別轟炸，逃出了新手村的您，也在這期間學習了一些新的技能，所以決定要開始幫助拯救世界。

就在此時，藍藍的天空變成了暗紅色，滿天的火球像流星雨一樣，正以高速衝向地面的房屋，你立即啟動了你的「探知」技能，偵測到有 n 間房屋，有 m 個火球，每間房屋都有耐久值 a_i 點，如果耐久值小於等於零就會破壞，每個火球的攻擊力都固定為 2點，滿天的火球還有 t 秒的時間就會到達地面。

你可以在這段時間內使用「瞬間移動加強防禦」的技能，只需消耗 1秒就可以到達任意房屋，並且加強該房屋耐久值 1點，也可以原地瞬間移動，但也要消耗 1秒。

在有限的時間內，你需要決定增加那些房屋的耐久值，才能保護最多的房屋。

Input

第一行，一個正整數 T 表示有 T 組獨立測試數據 ( 1 <= T <= 100 )

第二行，三個正整數 n, t, m ，分別表示 n 間房屋, t 秒的拯救時間, m 個火球 ( 1 <= n <= 10000, 0 <= t <= 10000, 1 <= m <= 10000 )

第三行，n 個正整數 a_i，表示第 i 間房屋的耐久值 ( 1 <= a_i <= 10000 )

第四行，m 個正整數 x_i，表示第 i 個火球攻擊的房屋編號 ( 1 <= x_i <= n )

Output

輸出共 T 行，每行表示在該組獨立數據下，還有多少房屋未被破壞。

Sample Input #1

Sample Output #1

Sample Input #2

4
3 4 2
5 2 4
2 1
3 2 20
6 6 6
1 3 3 1 2 1 1 1 2 2 2 1 1 3 1 2 2 3 3 1
2 0 2
1 2
1 1
5 3 12
4 5797 2 1 1
5 4 3 2 4 4 5 5 5 5 1 1

Sample Output #2

測資資訊：

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

Hint ：

範例1：
有 4 間房屋分別耐久值為 2, 1, 3, 5
1號：2 + 1 - 2 = 1
2號：1 + 2 - 2 = 1
3號：3 + 0 - 4 = -1
4號：5 + 0 - 2 = 3
最後還有 3間房屋未被破壞。

Tags:

出處:

[管理者：

kulam@g.puic... (林建源)

]

ID	User	Problem	Subject	Hit	Post Date
1783	1550294-5@g.... (username)	b377	很難	21	2025-02-28 21:37