← 返回题目列表

AtCoder · abc303_g

G. 袋子游戏

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

分数: 550 点

问题陈述

N 袋子排列成一排。 的 i第袋包含 x_i 日元(日本货币)。

拥有足够金钱的高桥和青木轮流执行以下动作:

  • 选择以下三个操作之一并执行。
    • 选择最左边或最右边的袋子并拿走它。
    • 支付 A 日元到 Snuke。 然后,重复以下动作 \min(B,n) 次(其中 n 是剩余袋子的数量):选择最左边或最右边的袋子并拿走。
    • 支付 C 日元到 Snuke。 然后,重复以下动作 \min(D,n) 次(其中 n 是剩余袋子的数量):选择最左边或最右边的袋子并拿走。

当所有袋子被拿走时,高桥的收益定义为“(高桥拿走的袋子中的总金额)-(高桥支付给snuke的总金额)”;令这个金额为 X 日元。 我们类似地定义 Aoki 的收益,用下式表示金额: Y 日元。

查找 X-Y 如果高桥和青木分别做出最大化和最小化的最佳动作 X-Y.

约束

  • 1 \leq N \leq 3000
  • 1 \leq x_i \leq 10^9
  • 1 \leq A,C \leq 10^9
  • 1 \leq B,D \leq N
  • 输入中的所有值都是整数。

输入

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

N A B C D
x_1 x_2 \ldots x_N

输出

打印答案。


示例输入 1

5 10 2 1000000000 1
1 100 1 1 1

示例输出 1

90

如果高桥和青木做出最佳动作,最终会是 X=92 和 Y=2.


示例输入 2

10 45 3 55 4
5 10 15 20 25 30 35 40 45 50

示例输出 2

85

示例输入 3

15 796265 10 165794055 1
18804175 185937909 1934689 18341 68370722 1653 1 2514380 31381214 905 754483 11 5877098 232 31600

示例输出 3

302361955