← 返回题目列表

AtCoder · abc128_d

D. 队列

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

分数: 400 点

问题陈述

你的朋友让你出队 D 作为生日礼物。

D 是一个水平圆柱体,包含一行 N 珠宝。

的 值 的珠宝是 V_1, V_2, ..., V_N 从左到右。可能存在具有负价值的珠宝。

一开始,你手里没有宝石。

您最多可以执行 K 操作 D,最多从以下选项中选择 K 次(可能为零):

  • 操作A:取出最左边的宝石 D 并将其握在手中。当以下情况时不能执行此操作 D 为空。

  • 操作B:取出包含在最右边的宝石 D 并将其握在手中。当以下情况时不能执行此操作 D 为空。

  • 操作C:选择手中的一颗宝石,将其插入到左端 D。当您手中没有宝石时,无法进行此操作。

  • 操作D:选择手中的一颗宝石,插入到右端 D。当您手中没有宝石时,无法进行此操作。

求运算后你手中的珠宝价值的最大可能总和。

约束

  • 输入中的所有值都是整数。
  • 1 \leq N \leq 50
  • 1 \leq K \leq 100
  • -10^7 \leq V_i \leq 10^7

输入

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

N K
V_1 V_2 ... V_N

输出

打印操作后您手中的珠宝价值的最大可能总和。


示例输入 1

6 4
-10 8 2 1 2 6

示例输出 1

14

经过以下操作序列后,您将获得两颗宝石值 您手中的 8 和 6 总计 14,这是最大结果。

  • 进行操作A。你取出有价值的宝石 -10 从左端开始 D.
  • 进行操作B。你取出有价值的宝石 6 从右端开始 D.
  • 进行操作A。你取出有价值的宝石 8 从左端开始 D.
  • 执行操作 D。您插入有价值的宝石 -10 到右端 D.

示例输入 2

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

示例输出 2

44

示例输入 3

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

示例输出 3

0

最好不执行任何操作。