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

Type: RemoteJudge

1000ms

128MiB

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

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

给定一个自然数组成的数组 $[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$ 。
若有多解，随意输出一解即可。

3
1 2 3

如果你选择 $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$	$10$		$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$