#3261. 「ROIR 2020 Day2」最大乘积

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: alpha1022

题目描述

译自 ROIR 2020 Day2 T1. Максимальное произведение

给定一个自然数组成的数组 [a_1,a_2,\ldots,a_n]
定义一个数组的权值为这个数组中所有数的和。

请把这个数组划分为两个非空数组 [a_1,a_2,\ldots,a_i] [a_{i+1},a_{i+2},\ldots,a_n] ,使得它们的权值之积尽量大。
你需要确定能够使得两个数组权值之积最大的 i

输入格式

第一行,一个整数 n ,表示元素的个数。
第二行, n 个整数 a_1,a_2,\ldots,a_n ,表示数组中的元素。

输出格式

输出能使得 [a_1,a_2,\ldots,a_i] [a_{i+1},a_{i+2},\ldots,a_n] 权值之积最大的 i
若有多解,随意输出一解即可。

样例

样例输入 1

3
1 2 3

样例输出 1

2

样例解释 1

如果你选择 i=1 ,则权值之积为 1 \cdot (2+3) = 5
如果你选择 i=2 ,则权值之积为 (1+2) \cdot 3 = 9

数据范围与提示

对于 100\% 的数据, 2 \le n \le 2\cdot 10^5, 1 \le a_i \le 10^9
具体数据限制如下表:

子任务编号 分值 限制 附加限制
1 10 2 \le n \le 5000 \sum a_i \le 10^9
2 a_1 = a_2 = \ldots = a_n
3 20 a_i \le 10^9
4 2 \le n \le 200000 \sum a_i \le 10^9
5 a_1 = a_2 = \ldots = a_n
6 a_i \le 10^9