#P9787. [ROIR 2020 Day2] 最大乘积

[ROIR 2020 Day2] 最大乘积

题目描述

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

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

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

输入格式

第一行,一个整数 nn,表示元素的个数。
第二行,nn 个整数 a1,a2,,ana_1,a_2,\ldots,a_n,表示数组中的元素。

输出格式

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

3
1 2 3
2

提示

【样例 1 解释】

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

【数据范围】

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

子任务编号 分值 限制 附加限制
11 1010 2n50002 \le n \le 5000 ai109\sum a_i \le 10^9
22 a1=a2==ana_1 = a_2 = \ldots = a_n
33 2020 ai109a_i \le 10^9
44 2n2000002 \le n \le 200000 ai109\sum a_i \le 10^9
55 a1=a2==ana_1 = a_2 = \ldots = a_n
66 ai109a_i \le 10^9