Query sulla Somma di Sottoinsiemi
Dato un insieme di
n interi e q query, in cui ogni query è rappresentata da un intero . Per ciascuna query, si richiede di stabilire se esiste un sottoinsieme dei numeri che, sommati, corrisponda a .Input
La prima riga dell’input contiene un unico intero
n (1 ≤ n ≤ 500).La seconda riga contiene
n interi separati da uno spazio (1 ≤ ≤ 100 000), che rappresentano gli elementi dell’insieme.La terza riga dell’input contiene un singolo intero
q (1 ≤ q ≤ 100 000), il numero di query. Ciascuna delle successive q righe contiene un intero (1 ≤ ≤ 100 000), che indica la somma obiettivo per la i-esima query.Output
Si devono produrre
q righe, ognuna contenente “Yes” o “No”, a seconda che esista un sottoinsieme dei numeri la cui somma sia uguale al corrispondente valore di query.Esempi
Ingresso | Uscita |
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