Задача №114529. Максимальное произведение
Задан массив натуральных чисел \([a_1, a_2, \ldots, a_n]\). Весом массива назовём сумму его элементов.
Необходимо разрезать заданный массив на два непустых массива \([a_1, a_2, \ldots, a_i]\) и \([a_{i+1}, a_{i+2}, \ldots, a_n]\) так, чтобы произведение их весов было как можно больше.
Требуется написать программу, которая по заданному массиву определяет, после какого элемента его необходимо разрезать, чтобы произведение весов получившихся массивов было максимальным.
В первой строке входных данных находится целое число \(n\) — количество элементов в массиве (\(2 \le n \le 2 \cdot {10}^5\)). В следующей строке находятся \(n\) целых чисел \(a_1, a_2, \ldots, a_n\) — элементы массива (\(1 \le a_i \le {10}^9\)).
Выведите одно число — номер элемента, после которого необходимо разрезать заданный массив. Если оптимальных вариантов ответа несколько, можно вывести любой из них.
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
|
|c|c|}
Подзадача |
Баллы | Ограничения | Дополнительные ограничения | Необх. подзадачи | Информация о проверке |
| 1 | 10 | \(2 \le n \le 5000\) | полная | ||
| 2 | 10 | \(2 \le n \le 5000\) | полная | ||
| 3 | 20 | \(2 \le n \le 5000\) | 1, 2 | полная | |
| 4 | 20 | \(2 \le n \le 200000\) | 1 | полная | |
| 5 | 20 | \(2 \le n \le 200000\) | 2 | полная | |
| 6 | 20 | \(2 \le n \le 200000\) | 1, 2, 3, 4, 5 | полная |
Если сделать разрез после первого элемента, произведение весов равно \(1 \cdot (2 + 3) = 5\), а если после второго, то \((1 + 2) \cdot 3 = 9\).
3 1 2 3
2