#H. [ABC189C] Mandarin Orange

    Type: Default 1000ms 256MiB

[ABC189C] Mandarin Orange

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.

[ABC189C] Mandarin Orange

题面翻译

题目描述

NN 个盘子摆在高桥君面前,从左到右第 ii 个盘子内放着 AiA_i 个橘子。

高桥君可以选择一组满足以下 33 个条件的整数 (l,r,x)(l,r,x)

  • 1lrN1\le l\le r\le N
  • 1x1\le x
  • 对于所有 ll 以上 rr 以下的整数 iixAix\le A_i

选择后,高桥君会从第 llrr 个(包括两端)的盘子里面分别拿 xx 个橘子吃。

请你计算当高桥君选择了最优的一组整数 (l,r,x)(l,r,x) ,他最多可以吃到几个橘子。

输入格式

输入以以下格式从标准输入中读取:

  • 11 行:一个正整数 NN
  • 22 行:NN 个正整数,第 ii 个正整数是 AiA_i
N
A(1) ... A(N)

输出格式

高桥君最多能吃几个橘子?

数据范围

  • 输入的全都是整数;
  • 1N1041\le N\le 10^4
  • 1Ai1051\le A_i\le 10^5

样例 1 解释

(l,r,x)=(2,6,4)(l,r,x)=(2,6,4) 时,高桥君可以吃 2020 个橘子;

样例 2 解释

(l,r,x)=(1,1,200)(l,r,x)=(1,1,200) 时,高桥君可以吃 200200 个橘子。

题目描述

高橋君の前に N N 枚の皿が一列に並べられており、左から i i 番目の皿には Ai A_i 個のみかんが置かれています。

高橋君は次の 3 3 つの条件を全て満たすような整数の組 (l,r,x) (l,r,x) 1 1 つ選びます。

  • 1 l  r  N 1\leq\ l\ \leq\ r\ \leq\ N
  • 1  x 1\ \le\ x
  • l l 以上 r r 以下の全ての整数 i i について、x  Ai x\ \le\ A_i

その後、高橋君は l l 番目から r r 番目まで (両端を含む) の全ての皿からみかんを x x 個ずつ取って食べます。

整数の組 (l,r,x) (l,r,x) を適切に選んだとき、高橋君は最大で何個のみかんを食べることができますか。

输入格式

入力は以下の形式で標準入力から与えられる。

N N A1 A_1 \ldots AN A_N

输出格式

高橋君が食べることのできるみかんの個数の最大値を出力せよ。

样例 #1

样例输入 #1

6
2 4 4 9 4 9

样例输出 #1

20

样例 #2

样例输入 #2

6
200 4 4 9 4 9

样例输出 #2

200

提示

制約

  • 入力は全て整数
  • 1  N  104 1\ \leq\ N\ \leq\ 10^4
  • 1  Ai  105 1\ \leq\ A_i\ \leq\ 10^5

Sample Explanation 1

(l,r,x)=(2,6,4) (l,r,x)=(2,6,4) としたとき、20 20 個のみかんを食べることができます。

Sample Explanation 2

(l,r,x)=(1,1,200) (l,r,x)=(1,1,200) としたとき、200 200 個のみかんを食べることができます。

训练题单三

Not Claimed
Status
Done
Problem
10
Open Since
2024-10-11 0:00
Deadline
2024-10-26 23:59
Extension
24 hour(s)