Codeforces Round 833 (Div. 2) |
---|
Закончено |
Красота массива $$$v_1,v_2,\ldots,v_n$$$ равняется количеству индексов $$$i$$$ ($$$1 \le i \le n$$$), таких что $$$v_1+v_2+\ldots+v_i = 0$$$.
У вас есть массив $$$a_1,a_2,\ldots,a_n$$$ длины $$$n$$$. Вы можете применить к нему следующую операцию сколько угодно раз:
Какой максимальной красоты массив $$$a$$$ вы можете получить?
В первой строке задано одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следуют описания этих наборов.
В первой строке дано одно число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — длина массива $$$a$$$.
Во второй строке даны $$$n$$$ целых чисел $$$a_1,a_2,\ldots,a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$) — массив $$$a$$$.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.
Для каждого набора входных данных выведите одно число: максимальную красоту массива $$$a$$$ после применения к нему операций.
552 0 1 -1 031000000000 1000000000 040 0 0 083 0 2 -10 10 -30 30 091 0 0 1 -1 0 1 0 -1
3 1 4 4 5
В первом наборе входных данных вы можете заменить $$$a_2$$$ на $$$-2$$$ за одну операцию. После этого массив $$$a$$$ станет равен $$$[2,-2,1,-1,0]$$$ и будет иметь красоту $$$3$$$:
Во втором наборе входных данных вы можете заменить $$$a_3$$$ на $$$-2\,000\,000\,000$$$, чтобы получить массив красоты $$$1$$$.
В третьем наборе входных данных вы можете не делать операции.
Название |
---|