← 返回题目列表

AtCoder · joi2026_semifinal_a

A. 座位 3

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

配点: 100 点

問題文

2N+2 座位排成一排。从左边开始 i 第一个座位(1 \leqq i \leqq 2N+2) 的坐感舒适为 A_i 。

2 一群参观者 N 团体及单独来访的贵宾 2 有人,这些 2N+2 致客户 分配 1 人 1 座位。 然而,2 请勿将同一座位分配给多名乘客。

目前属于同一组 2 需要为人们分配相邻的座位。 这时,VIP嘉宾 2 分配给人员 我们希望最大限度地提高 2 座椅的总体舒适度。

给定座位信息,VIP乘客 编写一个程序来查找 2 分配给人员 我们希望最大限度地提高 2 座位的总座位舒适度的最大值。


入力

输入是按以下格式从标准输入给出的。

N
A_1 A_2 \cdots A_{2N+2}

出力

标准输出,VIP 客户 2 分配给人员 我们希望最大限度地提高 2 座椅的总舒适度最大值为 1 行。


制約

  • 1 \leqq N \leqq 200\,000.
  • 1 \leqq A_i \leqq 10^9 (1 \leqq i \leqq 2N+2).
  • 所有输入值都是整数。

小課題

  1. (10 点) N = 1.
  2. (10 点) N \leqq 2.
  3. (10 点) N \leqq 3.
  4. (30 点) N \leqq 2\,000.
  5. (40 点)没有额外的限制。

入力例 1

2
20 60 40 30 10 50

出力例 1

90

通过如下分配, 2 一个人座椅的总舒适度是 它变成 90 。

  • 1 从左边开始, 分配第 1, 2 个座位。
  • 2 从左边开始, 分配第 4, 5 个座位。
  • VIP客户 2 人们从左边开始。 3, 6 个座位。

VIP客户 2 计算人们座椅的总乘坐舒适度。 它不能大于 90 ,所以90 。 您将获得

此输入示例是一个小作业。 2,3,4,5 满足约束。


入力例 2

1
1000000000 1000000000 1 1

出力例 2

2000000000

此输入示例满足所有子任务约束。


入力例 3

4
4 10 8 6 7 6 7 8 12 3

出力例 3

16

此输入示例是一个小作业。 4,5 满足约束。