equeue

题目描述

你的朋友把一个双端队列 $D$ 作为生日礼物送给你。 $D$ 是一个水平放置的圆筒，里面排着一排 $N$ 个宝石。 从左到右这些宝石的价值分别为 $V_1, V_2, ..., V_N$。宝石的价值可能为负。 一开始，你手上没有任何宝石。 你最多可以对 $D$ 执行 $K$ 次下列操作（最多 $K$ 次，次数可以为零）：

操作 A：从 $D$ 中取出最左边的宝石放到你手上。当 $D$ 为空时不能执行此操作。

操作 B：从 $D$ 中取出最右边的宝石放到你手上。当 $D$ 为空时不能执行此操作。

操作 C：从你手中的宝石中选一个并插入到 $D$ 的左端。当你手上没有宝石时不能执行此操作。

操作 D：从你手中的宝石中选一个并插入到 $D$ 的右端。当你手上没有宝石时不能执行此操作。

在这些操作之后，求你手中宝石价值之和的最大可能值。

输入格式

从标准输入读取输入，格式如下： $N$ $K$ $V_1$ $V_2$ $...$ $V_N$

输出格式

输出在操作之后你手中宝石价值之和的最大可能值。

6 4
-10 8 2 1 2 6

14

6 4
-6 -100 50 -2 -5 -3

44

6 3
-6 -100 50 -2 -5 -3

0

提示

所有输入数值均为整数。 $1 \leq N \leq 50$ $1 \leq K \leq 100$ $-10^7 \leq V_i \leq 10^7$经过如下操作序列，你手中有价值为 $8$ 和 $6$ 的两个宝石，总和为 $14$，这是最大结果。

执行操作 A。你从左端取出价值为 $-10$ 的宝石。 执行操作 B。你从右端取出价值为 $6$ 的宝石。 执行操作 A。你从左端取出价值为 $8$ 的宝石。 执行操作 D。你把价值为 $-10$ 的宝石插入到右端的 $D$。
最优的做法是可以不执行任何操作。

标签: AtCoder|abc128D

来源

AtCoder|abc128D