Abfragen zur Teilmengen-Summe
Angenommen, wir haben eine Menge aus
n ganzen Zahlen und q Abfragen, bei denen jede Abfrage eine Ganzzahl enthält. Für jede Abfrage soll ermittelt werden, ob eine Teilmenge der Zahlen existiert, deren Summe ergibt.Eingabe
Die erste Zeile der Eingabe enthält eine einzelne ganze Zahl
n (1 ≤ n ≤ 500).Die zweite Zeile enthält
n durch Leerzeichen getrennte ganze Zahlen (1 ≤ ≤ 100 000), also die Elemente der Menge.Die dritte Zeile der Eingabe enthält eine einzelne ganze Zahl
q (1 ≤ q ≤ 100 000), die Anzahl der Abfragen. In den nächsten q Zeilen folgt jeweils eine ganze Zahl (1 ≤ ≤ 100 000), die den Zielwert für die i-te Abfrage angibt.Ausgabe
Geben Sie
q Zeilen aus, in denen jeweils entweder Yes oder No steht, abhängig davon, ob es eine Teilmenge der Zahlen gibt, deren Summe dem jeweiligen Abfragewert entspricht.Beispiele
Eingabe | Ausgabe |
4
1 2 5 7
5
4
3
10
14
11 | No
Yes
Yes
Yes
No |
Constraints
Time limit: 10 seconds
Memory limit: 512 MB
Output limit: 1 MB