Codeforces Round 859 (Div. 4) |
---|
Закончено |
Единственное различие между двумя версиями в том, что в этой версии ограничения ниже.
Изначально массив $$$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}$$$.
Первая строка входных данных содержит целое число $$$t$$$ ($$$1 \leq t \leq 1000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \leq n \leq 5000$$$) — длину массива $$$c$$$.
Вторая строка каждого набора входных данных содержит $$$n$$$ разделенных пробелами целых чисел $$$c_i$$$ ($$$1 \leq c_i \leq 5000$$$) — массив $$$c$$$, который вам нужно получить из массива $$$a$$$.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$5000$$$.
Для каждого набора входных данных выведите «YES» (без кавычек), если такая последовательность операций существует, и «NO» (без кавычек) в противном случае.
Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.
6111255 1 3 2 157 1 5 2 131 1 151 1 4 2 1
YES NO YES NO YES YES
Для первого набора входных данных исходный массив $$$a$$$ уже равен $$$[1]$$$, поэтому ответ «YES».
Для второго набора входных данных после выполнения любого количества операций длина массива $$$a$$$ станет хотя бы два, а в начальном массиве элемента $$$2$$$ нет, поэтому получить массив $$$[2]$$$ невозможно, и ответ будет «NO».
Для третьего набора входных данных мы можем выполнить следующие операции, чтобы получить массив $$$c$$$:
Название |
---|