[ROIR 2020] 最大乘积 (Day2)

Luogu

IDLGP9787

Time1000ms

Memory128MB

DifficultyP2

2020Special JudgeROIR（俄罗斯）

**译自 [ROIR 2020](http://neerc.ifmo.ru/school/archive/2019-2020.html) Day2 T1.** ***[Максимальное произведение](http://neerc.ifmo.ru/school/archive/2019-2020/ru-olymp-regional-2020-day2.pdf)***，译者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$。 ## Input 第一行，一个整数 $n$，表示元素的个数。第二行，$n$ 个整数 $a_1,a_2,\ldots,a_n$，表示数组中的元素。 ## Output 输出能使得 $[a_1,a_2,\ldots,a_i]$ 和 $[a_{i+1},a_{i+2},\ldots,a_n]$ 权值之积最大的 $i$。若有多解，随意输出一解即可。 [samples] ## Note #### 【样例 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$|$10$|$2 \le n \le 5000$|$a_1 = a_2 = \ldots = a_n$| |$3$|$20$|$2 \le n \le 5000$|$a_i \le 10^9$| |$4$|$20$|$2 \le n \le 200000$|$\sum a_i \le 10^9$| |$5$|$20$|$2 \le n \le 200000$|$a_1 = a_2 = \ldots = a_n$| |$6$|$20$|$2 \le n \le 200000$|$a_i \le 10^9$|

Samples

Input #1

3
1 2 3

Output #1

API Response (JSON)

{
  "problem": {
    "name": "[ROIR 2020] 最大乘积 (Day2)",
    "description": {
      "content": "**译自 [ROIR 2020](http://neerc.ifmo.ru/school/archive/2019-2020.html) Day2 T1.** ***[Максимальное произведение](http://neerc.ifmo.ru/school/archive/2019-2020/ru-olymp-regional-2020-day2.pdf)***，译者Shine",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P2"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9787"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "**译自 [ROIR 2020](http://neerc.ifmo.ru/school/archive/2019-2020.html) Day2 T1.** ***[Максимальное произведение](http://neerc.ifmo.ru/school/archive/2019-2020/ru-olymp-regional-2020-day2.pdf)***，译者Shine...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments