747 . 禮物分裝

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

1xlc

User's AC Ratio

66.7% (2/3)

Submission's AC Ratio

33.3% (2/6)

Tags

apcsc apcsc-dc

Description

小風生日將至，他收到 N 件禮物，他幫每一件禮物都打上一個「美麗度」ti，小風想選取一些禮物使得禮物的美麗度總和正好是他想要的值，他選取禮物的方式很特別，他會操作若干次（包含零次）以下的操作並選取禮物們：

  • 計算出 mid=⌊max+min2⌋，其中 max 與 min 分別代表目前剩餘禮物裡的美麗值的最大與最小值。
  • 將禮物分成兩堆，其中一堆的美麗值均不超過 mid，另一堆均超過 mid。
  • 留下其中一堆，把另一推排除掉。

請你幫小風回答以下 Q 則詢問，每一個詢問會有一個整數 si，小風想問你他能不能經過若干次以上操作讓剩餘的禮物美麗度總和恰為 si？

Input Format

輸入第一行包含兩個正整數 N,Q(1≤N,Q≤105)，分別代表禮物的數量與詢問的個數。
輸入第二行有 N 個正整數 t1,t2,…,tN(1≤ti≤106)，代表每個禮物的美麗度。
接下來 Q 行，第 i 行有一個正整數 si(1≤ti≤109)，代表第 i 個詢問。

Output Format

一共輸出 Q 行，每個詢問佔一行。對於第 i 個詢問，若小風能夠讓禮物美麗度總和恰為 si，請輸出 Yes，否則請輸出 No。

Sample Input 1

5 5
1 2 3 4 5
1
8
9
12
6

Sample Output 1

Yes
No
Yes
No
Yes

Sample Input 2

5 5
3 1 3 1 3
1
2
3
9
11

Sample Output 2

No
Yes
No
Yes
Yes

Hints

Problem Source

Codeforces

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~41 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2000 524288 65536 1 2
1 2000 524288 65536 1 2
2 2000 524288 65536 2
3 2000 524288 65536 2
4 2000 524288 65536 2
5 2000 524288 65536 2
6 2000 524288 65536 2
7 2000 524288 65536 2
8 2000 524288 65536 2
9 2000 524288 65536 2
10 2000 524288 65536 2
11 2000 524288 65536 2
12 2000 524288 65536 2
13 2000 524288 65536 2
14 2000 524288 65536 2
15 2000 524288 65536 2
16 2000 524288 65536 2
17 2000 524288 65536 2
18 2000 524288 65536 2
19 2000 524288 65536 2
20 2000 524288 65536 2
21 2000 524288 65536 2
22 2000 524288 65536 2
23 2000 524288 65536 2
24 2000 524288 65536 2
25 2000 524288 65536 2
26 2000 524288 65536 2
27 2000 524288 65536 2
28 2000 524288 65536 2
29 2000 524288 65536 2
30 2000 524288 65536 2
31 2000 524288 65536 2
32 2000 524288 65536 2
33 2000 524288 65536 2
34 2000 524288 65536 2
35 2000 524288 65536 2
36 2000 524288 65536 2
37 2000 524288 65536 2
38 2000 524288 65536 2
39 2000 524288 65536 2
40 2000 524288 65536 2
41 2000 524288 65536 2
Submit
Back to Top