시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 0 | 0 | 0 | 0.000% |
Cheryl is an ambitious chemist who likes to conduct an experiment. In her lab, she has N different types of atom numbered from 1 to N. We can assume that for all i, Cheryl has infinitely many atoms of type i. All atoms of the ith type have a weight of a positive integer Wi.
Cheryl would like to combine atoms of two different types to create a compound. A compound of type (x, y) (1 ≤ x < y ≤ N) can be created by combining at least one atom of type x and at least one atom of type y. The weight of a compound is the sum of the weight of all the atoms used to create it. To avoid destroying her lab, Cheryl would not create a compound with a weight of more than 1012. Note that there are N(N−1)/2 distinct compound types.
The variety of a compound type is the number of distinct weight of that compound that can be created by Cheryl. In other words, the variety of a compound type (x, y) is the number of distinct weight w not more than 1012 such that there exists positive integers α and β satisfying w = Wx · α + Wy · β.
For example, let N = 5 and W1...5 = {2, 3, 4, 3, 3}.
For each compound type, Cheryl can choose to create exactly one compound of that type or to not create any compound of that type. We say that a compound type (x, y) is created if Cheryl chooses to create a compound of type (x, y).
If a compound type (x, y) is created, then any other compound type of the same variety as (x, y) must also be created. There are Q questions that Cheryl would like to answer. For the jth question, Cheryl is wondering whether she can create exactly Kj compounds.
Input begins with a line containing two integers: N Q (2 ≤ N ≤ 500; 1 ≤ Q ≤ 100 000) representing the number of atom types and the number of questions, respectively. The next line contains N integers: Wi (1 ≤ Wi ≤ 100 000) representing the weight of the atoms. The next Q lines each contains an integer: Kj (1 ≤ Kj ≤ N(N−1)/2) representing the number of compounds to be created.
For each query in the same order as input, output in a line a string “YES
” (without quotes) or “NO
” (without quotes) whether it is possible to create exactly Kj compounds.
5 4 2 3 4 3 3 1 2 3 10
YES NO YES YES
This is the example from the problem description.
There are three compound types with a variety of 999 999 999 995 ((1, 2), (1, 4), and (1, 5)), three compound types with a variety of 999 999 999 991 ((2, 3), (3, 4), and (3, 5)), three compound types with a variety of 333 333 333 332 ((2, 4), (2, 5), and (4, 5)), and one compound type with a variety of 499 999 999 998 ((1, 3)). Therefore,
ICPC > Regionals > Asia Pacific > Indonesia > Indonesia National Contest > INC 2020 I번