Codeforces Round 548 (Div. 2) |
---|
Закончено |
Вы пришли в магазин, продающих $$$n$$$ типов шоколадок. Всего в наличии есть $$$a_i$$$ шоколадок типа $$$i$$$.
У вас есть неограниченное количество денег (так что никаие цены не являются ограничивающим фактором) и вы хотите купить как можно больше шоколадок. Однако, если вы купите $$$x_i$$$ шоколадок типа $$$i$$$ (очевидно, $$$0 \le x_i \le a_i$$$), то для каждого $$$1 \le j < i$$$ должно быть верно хотя бы одно из двух:
Например, массив $$$x = [0, 0, 1, 2, 10]$$$ удовлетворяет условию выше (в предположении, что все $$$a_i \ge x_i$$$), а массивы $$$x = [0, 1, 0]$$$, $$$x = [5, 5]$$$ и $$$x = [3, 2]$$$ нет.
Вычислите наибольшое количество шоколадок, которое вы можете купить.
Первая строка содержит одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — количество типов шоколадок.
Следующая строка содержит $$$n$$$ целых чисел $$$a_i$$$ ($$$1 \le a_i \le 10^9$$$) — количество шоколадок каждого вида.
Выведите максимальное количество шоколадок, которое можно купить.
5 1 2 1 3 6
10
5 3 2 5 4 10
20
4 1 1 1 1
1
В первом примере оптимально купить: $$$0 + 0 + 1 + 3 + 6$$$ шоколадок.
Во втором примере оптимально купить: $$$1 + 2 + 3 + 4 + 10$$$ шоколадок.
В третьем примере оптимально купить: $$$0 + 0 + 0 + 1$$$ шоколадок.
Название |
---|