Отрезок подлиннее - Maximum Segments with Non-decreasing Sums · IZhO 2019 #E
Physics
Problem
Наш маленький мальчик Асхат сделал интересное наблюдение — покрыть массив "прыжками," где каждый "больше" предыдущего, не так уж и просто. Разумеется, теперь Вам предстоит придумать как это сделать.
Вам дается последовательность из положительных целых чисел длины N.
Нужно разделить данную последовательность на максимальное количество отрезков так, что:
1. Каждый элемент последовательности принадлежит ровно одному отрезку.
2. Сумма чисел в каждом отрезке, кроме первого, не меньше чем в предыдущем.
Формат входных данных:
Первая строка ввода содержит целое число N (1⩽N⩽5×105).
Следующая строка содержит N положительных целых чисел ai (1⩽ai⩽109) разделенных пробелами.
Формат выходных данных:
Выведите единственное целое число — максимальное число отрезков, на которое можно поделить данную последовательность.
Система оценки:
1. 1⩽N⩽20; ai⩽106. Оценивается в 13 баллов.
2. 1⩽N⩽500. Оценивается в 14 баллов.
3. 1⩽N⩽3000. Оценивается в 10 баллов.
4. 1⩽N⩽105. Оценивается в 36 баллов.
5. Ограничения из условия. Оценивается в 27 баллов.
Примеры:
```
Вход: 4
2 3 1 7
Выход: 3
Вход: 5
6 2 3 9 13
Выход: 3
Вход: 3
3 1 2
Выход: 2
```