2025 . 反手無力

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

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

CKsim 2017-CKsim-2nd

Description

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


涼風搬貓

Input Format

第一行是一個正整數T≤50，代表測資筆數
每筆測資第一行包含兩個正整數N≤2×103,K≤2×103，分別代表貓的個數以及風的個數。
而第二行包含N個正整數w1,w2,…,wN，代表N隻貓分別的重量。
第三行包含K個正整數s1,s2,…,sK，代表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≤30
第二組30分，N≤300
第三組51分，N≤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
Submit
Back to Top