Codeforces Round 855 (Div. 3) |
---|
Закончено |
Это простая версия задачи. Она отличается от сложной только ограничениями на $$$n$$$ и $$$t$$$.
Есть колода из $$$n$$$ карт, каждая из которых характеризуется своей силой. Бывают карты двух видов:
Вы можете делать с колодой следующее:
Ваша задача с помощью таких действий собрать армию с наибольшей суммарной силой.
Первая строка входных данных содержит единственное число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных в тесте.
Первая строка каждого набора содержит одно целое число $$$n$$$ ($$$1 \le n \le 5000$$$) — количество карт в колоде.
Вторая строка каждого набора содержит $$$n$$$ целых чисел $$$s_1, s_2, \dots, s_n$$$ ($$$0 \le s_i \le 10^9$$$) — силы карт в порядке сверху вниз.
Гарантируется, что сумма всех значений $$$n$$$ не превосходит $$$5000$$$.
Выведите $$$t$$$ чисел, каждое из которых является ответом на соответствующий набор входных данных — максимальную возможную суммарную силу армии, которой можно добиться.
553 3 3 0 060 3 3 0 0 371 2 3 0 4 5 071 2 5 0 4 3 053 1 0 0 4
6 6 8 9 4
В первом примере можно взять бонусы $$$1$$$ и $$$2$$$. Обе карты героев получат по $$$3$$$ к силе. Если взять все бонусы, один из них останется неиспользованным.
Во втором примере карту героя сверху колоды невозможно усилить, а остальных можно усилить бонусами $$$2$$$ и $$$3$$$ и получить $$$6$$$ суммарной силы.
В четвёртом примере можно взять бонусы $$$1$$$, $$$2$$$, $$$3$$$, $$$5$$$ и пропустить бонус $$$6$$$, тогда герой $$$4$$$ будет усилен бонусом $$$3$$$ на $$$5$$$, а герой $$$7$$$ бонусом $$$5$$$ на $$$4$$$. $$$4+5=9$$$.
Название |
---|