Единственное различие между двумя версиями в том, что в этой версии ограничения выше.
Изначально массив \(a\) содержит только число \(1\). Вы можете выполнить несколько операций, чтобы изменить массив. За одну операцию можно выбрать некоторую подпоследовательность \(^{\dagger}\) из \(a\) и вставить на любую позицию в \(a\) элемент, равный сумме всех элементов подпоследовательности.
Вам дан массив \(c\). Проверьте, можно ли получить из массива \(a\) массив \(c\), выполнив некоторое количество (возможно, 0) операций над исходным массивом.
\(^{\dagger}\) Последовательность \(b\) является подпоследовательностью последовательности \(a\), если \(b\) может быть получена из \(a\) удалением нескольких (возможно, нуля, но не всех) элементов. Другими словами, операция выглядит так: выберем \(k\) (\(1 \leq k \leq |a|\)) различных индексов \(i_1, i_2, \dots, i_k\) и вставим в любое место \(a\) новый элемент со значением, равным \(a_{i_1} + a_{i_2} + \dots + a_{i_k}\).
Выходные данные
Для каждого набора входных данных выведите «YES» (без кавычек), если такая последовательность операций существует, и «NO» (без кавычек) в противном случае.
Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.
Примечание
Для первого набора входных данных исходный массив \(a\) уже равен \([1]\), поэтому ответ «YES».
Для второго набора входных данных после выполнения любого количества операций длина массива \(a\) станет хотя бы два, а в начальном массиве элемента \(2\) нет, поэтому получить массив \([2]\) невозможно, и ответ будет «NO».
Для третьего набора входных данных мы можем выполнить следующие операции, чтобы получить массив \(c\):
- Первоначально, \(a = [1]\).
- Выбрав подпоследовательность \([1]\) и вставив \(1\) в массив, \(a\) станет равным \([1, 1]\).
- Выбрав подпоследовательность \([1, 1]\) и вставив \(1+1=2\) в середину массива, \(a\) станет равным \([1, 2, 1]\).
- Выбрав подпоследовательность \([1, 2]\) и вставив \(1+2=3\) после первой \(1\) массива, \(a\) станет равным \([1, 3, 2, 1]\).
- Выбрав подпоследовательность \([1, 3, 1]\) и вставив \(1+3+1=5\) в начало массива, \(a\) станет равным \([5, 1, 3, 2, 1]\) (именно такой массив нам нужно было получить).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
1
1
1
2
5
5 1 3 2 1
5
7 1 5 2 1
3
1 1 1
5
1 1 4 2 1
|
YES
NO
YES
NO
YES
YES
|