Автор: | Центральная предметно-методическая комиссия | Ограничение времени: | 1 сек | |
Входной файл: | Стандартный вход | Ограничение памяти: | 512 Мб | |
Выходной файл: | Стандартный выход | |||
Максимальный балл: | 100 |
Задан массив натуральных чисел [a1,a2,…,an]. Весом массива назовём сумму его элементов.
Необходимо разрезать заданный массив на два непустых массива [a1,a2,…,ai] и [ai+1,ai+2,…,an] так, чтобы произведение их весов было как можно больше.
Требуется написать программу, которая по заданному массиву определяет, после какого элемента его необходимо разрезать, чтобы произведение весов получившихся массивов было максимальным.
В первой строке входных данных находится целое число n — количество элементов в массиве (2≤n≤2⋅105). В следующей строке находятся n целых чисел a1,a2,…,an — элементы массива (1≤ai≤109).
Выведите одно число — номер элемента, после которого необходимо разрезать заданный массив. Если оптимальных вариантов ответа несколько, можно вывести любой из них.
1≤ai≤109
2≤n≤2⋅105
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
Подзадача | Баллы | Ограничения | Необходимые подзадачи | Информация о проверке |
---|---|---|---|---|
1 | 10 | 2≤n≤5000, Сумма всех ai не превосходит 109 | полная | |
2 | 10 | 2≤n≤5000, Все ai равны | 1 | полная |
3 | 20 | 2≤n≤5000, ai≤109 | 1, 2 | полная |
4 | 20 | 2≤n≤200000, Сумма всех ai не превосходит 109 | 1 | полная |
5 | 20 | 2≤n≤200000, Все ai равны | 2 | полная |
6 | 20 | 2≤n≤200000, ai≤109 | 1, 2, 3, 4, 5 | полная |
Если сделать разрез после первого элемента, произведение весов равно 1⋅(2+3)=5, а если после второго, то (1+2)⋅3=9
№ | Стандартный вход | Стандартный выход |
---|---|---|
1 |
|
|