TopCoder

玩泥巴:3
NP≠P -周柏宇 2016.11.19&21

User's AC Ratio

86.7% (13/15)

Submission's AC Ratio

43.3% (29/67)

Tags

Description

有$N$個貓在數線上,從左到右第$i$隻貓重量是$w_i$。
現在會有$K$陣風依序吹來,第$i$陣風的強度是$S_i$。你可以控制每陣風的起始點、方向($+X$或$-X$)和持續時間。
每一秒鐘,如果迎風且最接近起始點的那隻貓重量小於等於風的強度,那麼它就會被往風的方向吹,並與它後面的那隻貓合併成一隻貓,其重量為原本兩隻貓的重量相加。
(如果那隻貓重量大於風的強度,則那陣風就無法再使任何貓移動。)
問你能否安排每陣風的起始點、方向和持續時間,使所有貓合而為一。


涼風搬貓

Input Format

第一行是一個正整數$T\leq 50$,代表測資筆數
每筆測資第一行包含兩個正整數$N\leq 2\times 10^ 3, K\leq 2\times 10^ 3$,分別代表貓的個數以及風的個數。
而第二行包含$N$個正整數$w_1,w_2,\dots,w_{N}$,代表$N$隻貓分別的重量。
第三行包含$K$個正整數$s_1,s_2,\dots,s_{K}$,代表$K$陣風分別的強度。
輸入之整數保證是正的且在int範圍內

Output Format

如果可以輸出"Yes"(不含引號)
否則輸出"No"(不含引號)

Sample Input 1

4
5 2
1 1 1 1 1
2 2
6 7
3 2 1 1 2 3
2 2 2 2 2 2 2
7 4
1 2 3 4 3 2 1
3 3 3 3
5 1
5 4 3 2 1
10

Sample Output 1

Yes
No
Yes
Yes

Hints

本題共有三組測試資料。每組可有多個輸入檔案,全部答對該組才得分。

第一組19分,$N\leq 30$
第二組30分,$N\leq 300$
第三組51分,$N\leq 2000$

Problem Source

rsabcmoi

Subtasks

No. Testdata Range Score
1 0 19
2 0~1 30
3 0~2 51

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1 2 3
1 5000 65536 262144 2 3
2 5000 262144 262144 3