← 返回题目列表

AtCoder · awc0064_b

B. 拿牌游戏

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

分数: 300 分

问题陈述

高桥和青木正在互相玩抽牌游戏。

有 N 卡片放在桌子上。每张卡片的编号为 1 to N和卡 i 有一个正整数 A_i 。

游戏按照以下规则进行:

  1. 两名玩家的开局得分均为 从桌上剩余的牌中选择 0.
  2. 高桥先行,高桥和青木轮流轮流。
  3. 在轮到他们时,玩家必须准确选择 从当前行的左端或右端选择 1 牌并拿走它(不允许传递)。所拿的牌将从表中移除,并且该牌上写的整数将添加到该玩家的分数中。
  4. 当所有牌都被拿走后,游戏结束。

根据上述规则,高桥将采取 \lceil N/2 \rceil 卡和青木将采取 \lfloor N/2 \rfloor 卡。

高桥以最佳方式发挥最大化(高桥的分数) - (青木的得分),并且青木发挥最优以最小化(高桥的得分) - (青木的分数)。查找(高桥的分数) - (青木的得分)当两名球员都发挥最佳状态时。

约束

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^9
  • 所有输入均为整数

输入

N
A_1 A_2 \ldots A_N
  • 第一行包含一个整数 N 代表卡片数量。 卡上写着
  • 第二行包含 N 整数 A_i (i = 1, 2, \ldots, N) 写在卡片上 i,用空格分隔。

输出

在单行中以整数形式输出(高桥分数)的值 - (青木的得分)当两名球员都发挥最佳状态时。


示例输入 1

3
10 20 30

示例输出 1

20

示例输入 2

5
1 2 3 4 5

示例输出 2

3

示例输入 3

8
100 50 80 120 90 30 70 60

示例输出 3

60