101283: [AtCoder]ABC128 D - equeue

Memory Limit：256 MB Time Limit：2 S
Judge Style：Text Compare Creator：
Submit：0 Solved：0

Description

Score : $400$ points

Problem Statement

Your friend gave you a dequeue $D$ as a birthday present.

$D$ is a horizontal cylinder that contains a row of $N$ jewels.

The values of the jewels are $V_1, V_2, ..., V_N$ from left to right. There may be jewels with negative values.

In the beginning, you have no jewel in your hands.

You can perform at most $K$ operations on $D$, chosen from the following, at most $K$ times (possibly zero):

  • Operation A: Take out the leftmost jewel contained in $D$ and have it in your hand. You cannot do this operation when $D$ is empty.

  • Operation B: Take out the rightmost jewel contained in $D$ and have it in your hand. You cannot do this operation when $D$ is empty.

  • Operation C: Choose a jewel in your hands and insert it to the left end of $D$. You cannot do this operation when you have no jewel in your hand.

  • Operation D: Choose a jewel in your hands and insert it to the right end of $D$. You cannot do this operation when you have no jewel in your hand.

Find the maximum possible sum of the values of jewels in your hands after the operations.

Constraints

  • All values in input are integers.
  • $1 \leq N \leq 50$
  • $1 \leq K \leq 100$
  • $-10^7 \leq V_i \leq 10^7$

Input

Input is given from Standard Input in the following format:

$N$ $K$
$V_1$ $V_2$ $...$ $V_N$

Output

Print the maximum possible sum of the values of jewels in your hands after the operations.

Sample Input 1

6 4
-10 8 2 1 2 6

Sample Output 1

14

After the following sequence of operations, you have two jewels of values $8$ and $6$ in your hands for a total of $14$, which is the maximum result.

  • Do operation A. You take out the jewel of value $-10$ from the left end of $D$.
  • Do operation B. You take out the jewel of value $6$ from the right end of $D$.
  • Do operation A. You take out the jewel of value $8$ from the left end of $D$.
  • Do operation D. You insert the jewel of value $-10$ to the right end of $D$.

Sample Input 2

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

Sample Output 2

44

Sample Input 3

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

Sample Output 3

0

It is optimal to do no operation.

Input

题意翻译

### 题目描述 有一个双端队列，初始时队列中共有 $n$ 个元素，元素从头到尾的权值为 $v_{1},v_{2},\cdots,v_{n}$ 你可以进行不超过 $k$ 次操作（也可以一次都不操作），每次操作可以选择队头或队尾的一个元素，将它归为己有，或将自己手上的一个元素塞到队头或队尾 问最终你手上所有元素的权值之和的最大值是多少 ### 输入格式 第一行两个整数 $n,k$ 接下来一行 $n$ 个整数表示 $v_{i}$ ### 输出格式 一行一个整数，表示答案 ### 数据范围与提示 $ 1 \le n \le 50,1 \le k \le 100, -10^7 \le v_{i} \le 10^7 $

Source/Category

加入题单

算法标签：