题目详情题解（0）讨论（0）提交记录（0）

AT_abc162_f.[ABC162F] Select Half

提高+/省选-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定一个长度为 NN 的整数序列 A1,…,ANA_1,\ldots,A_N。

请从中恰好选择 $ \left\lfloor \frac{N}{2} \right\rfloor $ 个整数，要求任意两个被选中的位置都不相邻。

请你求出所能得到的选中元素之和的最大可能值。

这里，$ \lfloor x \rfloor $ 表示不超过 xx 的最大整数。

输入格式

输入以如下格式从标准输入读入。

NN A1A_1 ...... ANA_N

输出格式

请输出所能得到的选中元素之和的最大可能值。

输入输出样例

  • 输入#1

    6
1 2 3 4 5 6

    输出#1

    12

  • 输入#2

    5
-1000 -100 -10 0 10

    输出#2

    0

  • 输入#3

    10
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

    输出#3

    5000000000

  • 输入#4

    27
18 -28 18 28 -45 90 -45 23 -53 60 28 -74 -71 35 -26 -62 49 -77 57 24 -70 -93 69 -99 59 57 -49

    输出#4

    295

说明/提示

限制条件

  • 2≤N≤2×1052 \leq N \leq 2\times 10^5
  • ∣Ai∣≤109|A_i| \leq 10^9
  • 输入均为整数

样例解释 1

选择 2,4,62,4,6，它们的和为 1212，这是最大值。

样例解释 2

选择 −10,10-10,10，它们的和为 00，这是最大值。

样例解释 3

请注意防止溢出。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页