Subset sum 4
Time: 1.0 s Memory: 1024 MB
-
You are given multiple integers. Your task is to answer whether there exists a subset of these integers, whose sum is exactly $T$.
Input
The first line of input contains the integers $M$ and $T$ ($1 \leq M \leq 500$, $1 \leq T \leq 10^{18}$), the largest number in the input and the target sum.
The next line contains $M+1$ integers $n_0, n_1, \dots , n_M$ ($1 \leq n_i \leq 10^{12}$). For each $i$, $n_i$ means that there are $n_i$ integers of value $i$.
Output
Print YES if there is such a subset, otherwise print NO.
Explanation of sample 1
-
$n_0=0$ means that there are no zeros.
-
$n_1=3$ means that we have the integers $1, 1, 1$.
-
$n_2=0$ means there are no twos.
-
$n_3=3$ means that we have the integers $3,3,3$.
-
$\cdots $
-
$n_7=2$ means that we have the integers $7,7$.
If we choose the subset $\{ 3,3,3,7\} $, we get a subset with sum $16$. Thus, the answer is YES.
Sample Input 1 Sample Output 1 7 16 0 3 0 3 0 0 0 2
YES
Sample Input 2 Sample Output 2 1 10 0 9
NO
-
-
To solve the problems, you can either start a virtual contest or register for regular practice. A virtual contest simulates a participation in the original contest with a duration of 1 day, while regular practice lets you submit solutions without any constraints.
You must log in to register. - 1 Subset sum
- 2 Subset sum 2
- 3 Subset sum 3
- 4 Subset sum 4
- 5 Subset sum 5