← 返回题目列表

AtCoder · arc117_f

F. 蛋糕

中文机器翻译题面 查看原题

分数: 900 点

问题陈述

AtCoder先生为他做了一个圆形的巧克力蛋糕 2N 朋友们。它从中心径向切割成 2N 等份,编号 0 通过 2N-1 按顺时针顺序。

为了进行最后的润色,他将在每件作品上放上草莓。他已经听到了他的朋友们对此的看法。朋友已数完 0 通过 2N-1和朋友 i (0 \leq i \leq 2N-1) 想要以下内容:

  • 一块 i, i+1, \dots, i+N-1 总共至少有 A_i 上面有草莓(用于 x \geq 2N,考虑一块 x 作为一块 x-2N).

为了满足所有朋友的要求,整个蛋糕上至少应该放多少个草莓?

约束

  • 1 \leq N \leq 150000
  • 0 \leq A_i \leq 5 \times 10^8 \ (0 \leq i \leq 2N-1)
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N
A_0 A_1 \cdots A_{2N-1}

输出

打印出整个蛋糕上应该放置的最少草莓数量,以满足朋友们的要求。


样本输入 1

3
2 5 7 4 2 1

示例输出 1

8

考虑我们提出的情况 1, 0, 1, 4, 2, 0 草莓碎片 0, 1, 2, 3, 4, 5。

这种情况下,好友的所有请求均已满足,如下:

  • 朋友 0:碎片 0, 1, 2 共有 2 上面有草莓,不少于 A_0 = 2.
  • 朋友 1:碎片 1, 2, 3 共有 5 上面有草莓,不少于 A_1 = 5.
  • 朋友 2:碎片 2, 3, 4 共有 7 上面有草莓,不少于 A_2 = 7.
  • 朋友 3:碎片 3, 4, 5 共有 6 上面有草莓,不少于 A_3 = 4.
  • 朋友 4:碎片 4, 5, 0 共有 3 上面有草莓,不少于 A_4 = 2.
  • 朋友 5:碎片 5, 0, 1 共有 1 上面有草莓,不少于 A_5 = 1.

因此,我们可以通过总共放置 8 蛋糕上的草莓。 这是所需的最少草莓数量。


示例输入 2

3
8 0 6 0 9 0

示例输出 2

12

考虑我们提出的情况 6, 0, 2, 1, 3, 0 草莓碎片 0, 1, 2, 3, 4, 5。

这种情况下,好友的所有请求均已满足,如下:

  • 朋友 0:碎片 0, 1, 2 共有 8 上面有草莓,不少于 A_0 = 8.
  • 朋友 1:碎片 1, 2, 3 共有 3 上面有草莓,不少于 A_1 = 0.
  • 朋友 2:碎片 2, 3, 4 共有 6 上面有草莓,不少于 A_2 = 6.
  • 朋友 3:碎片 3, 4, 5 共有 4 上面有草莓,不少于 A_3 = 0.
  • 朋友 4:碎片 4, 5, 0 共有 9 上面有草莓,不少于 A_4 = 9.
  • 朋友 5:碎片 5, 0, 1 共有 6 上面有草莓,不少于 A_5 = 0.

因此,我们可以通过总共放置 12 蛋糕上的草莓。 这是所需的最少草莓数量。


示例输入 3

5
3 1 5 7 0 8 4 6 4 9

示例输出 3

12

我们可以把 0, 0, 0, 4, 0, 1, 1, 1, 0, 5 草莓碎片 0, 1, \dots, 9分别满足朋友们的所有要求。

在这种情况下,总共有 12 蛋糕上的草莓,这是最少需要的草莓数量。


示例输入 4

1
267503 601617

示例输出 4

869120

我们可以把 267503 草莓片 0 和 601617 草莓片 1 满足朋友们的所有要求。


示例输入 5

8
418940906 38034755 396064111 43044067 356084286 61548818 15301658 35906016 20933120 211233791 30314875 25149642 42550552 104690843 81256233 63578117

示例输出 5

513119404