Algorithmen und Datenstrukturen

Erweiterte Subset-Sum-Abfragen

Angenommen, wir haben eine Menge aus n Zahlen . Es sollen q Abfragen durchgeführt werden, die jeweils einem von zwei Typen entsprechen:
  • Typ 1: Überprüfe, ob es eine Teilmenge dieser Zahlen gibt, deren Summe gleich s ist.
  • Typ 2: Entferne die Zahl s aus der Menge.

Eingabe

Die erste Zeile der Eingabe enthält eine einzelne ganze Zahl n (1 ≤ n ≤ 300), die die Größe der Zahlenmenge angibt.
Die zweite Zeile enthält n durch Leerzeichen getrennte ganze Zahlen (1 ≤ a_i ≤ 10^5), also die Elemente der Menge.
  • Bei einer Abfrage vom Typ 1 ist t = 1 und s steht für die Zielsumme, die überprüft werden soll.
  • Bei einer Abfrage vom Typ 2 ist t = 2 und s ist das Element, das aus der Menge entfernt werden muss.
Die Anzahl der Abfragen vom Typ 2 übersteigt 200 nicht.

Ausgabe

Für jede Abfrage vom Typ 1 soll ausgegeben werden, ob eine entsprechende Teilmenge existiert. Gebe dafür Yes aus, wenn eine solche Teilmenge gefunden werden kann, oder No, wenn nicht.

Beispiele

Eingabe
Ausgabe
4 1 2 5 7 7 1 4 1 3 1 10 2 1 1 10 1 3 1 9
No Yes Yes No No Yes
 

Constraints

Time limit: 8 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue