Problem:


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.



Sample input:
6 4
-10 8 2 1 2 6


Sample output:
14

Submission status: Wrong Answer

Solution code:
import heapq
N,K=map(int, input().split())
V=list(map(int, input().split()))
ans=0

for i in range (0,min(N,K)+1):
    for j in range(0,min(N,K)-i):
        CNT = []
        tmp =K-(i+j)
        for k in range(0,i):
            CNT.append(V[k])
        for l in range(0,j):
            CNT.append(V[N-1-l])
        heapq.heapify(CNT)
        for h in range(0,tmp):
            if len(CNT)>0 and CNT[0]<0:
                heapq.heappop(CNT)
        ans=max(ans,sum(CNT))

print(ans)

Submission status: Wrong Answer

Solution code:
import heapq
N,K=map(int, input().split())
V=list(map(int, input().split()))
ans=0

for i in range (0,min(N,K)):
    for j in range(0,min(N,K)-i):
        CNT = []
        tmp =K-(i+j)
        for k in range(0,i):
            CNT.append(V[k])
        for l in range(0,j):
            CNT.append(V[N-1-l])
        heapq.heapify(CNT)
        for h in range(0,tmp):
            if len(CNT)>0 and CNT[0]<0:
                heapq.heappop(CNT)
        ans=max(ans,sum(CNT))

print(ans)

Submission status: Wrong Answer

Solution code:
import heapq
N,K=map(int, input().split())
V=list(map(int, input().split()))
ans=0
CNT=[]
for i in range (0,min(N,K+1)):
    for j in range(0,min(N,K-i)):
        tmp =K-(i+j)
        for k in range(0,i):
            CNT.append(V[k])
        for l in range(0,j):
            CNT.append(V[N-1-l])
        heapq.heapify(CNT)
        for h in range(0,tmp+1):
            if len(CNT)>0 and CNT[0]<0:
                heapq.heappop(CNT)
        ans=max(ans,sum(CNT))

print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
V = list(map(int, input().split()))

def query(l, r):
    if (l+r > min(N, K)):
        return -1
    rest = K-l-r
    lst = V[:l] + V[N-r+1:]
    lst.sort()
    return sum([x for i, x in enumerate(lst) if x > 0 or i >= rest])

ans = 0
for l in range(N):
    for r in range(N):
        ans = max(ans, query(l, r))
print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
V = list(map(int, input().split()))

def query(l, r):
    if (l+r > min(N, K)):
        return 0
    rest = K-l-r
    lst = V[:l] + V[N-r+1:]
    lst.sort()
    print(l, r, lst, sum([x for i, x in enumerate(lst) if x > 0 or i >= rest]))
    return sum([x for i, x in enumerate(lst) if x > 0 or i >= rest])

ans = 0
for l in range(N):
    for r in range(N):
        ans = max(ans, query(l, r))
print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
V = list(map(int, input().split()))

def query(l, r):
    if (l+r > min(N, K)):
        return 0
    rest = K-l-r
    lst = V[:l] + (V[-r:] if r is not 0 else [])
    lst.sort()
    return sum([x for i, x in enumerate(lst) if x > 0 or i >= rest])

ans = 0
for l in range(N):
    for r in range(N):
        ans = max(ans, query(l, r))
print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
V = list(map(int, input().split()))

def query(l, r):
    if (l+r > min(N, K)):
        return 0
    rest = K-l-r
    lst = V[:l] + (V[-r:] if r is not 0 else [])
    print(l, r, len(lst))
    lst.sort()
    print([x for i, x in enumerate(lst) if x > 0 or i >= rest])
    return sum([x for i, x in enumerate(lst) if x > 0 or i >= rest])

ans = 0
for l in range(N):
    for r in range(N):
        ans = max(ans, query(l, r))
print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
xs=[0]+list(map(int,input().split()))
from itertools import accumulate
As=list(accumulate(xs))
r = 0
for i in range(k+1):
    for j in range(i, k+1):
        x = i, j-i, k-j
#        m1 = As[i] + As[n] - As[n-j+i]
        m = sum(sorted(z for z in (xs[:i]+xs[n-j+i+1:]) if z < 0)[:k-j])
#        if m > r:
#            print(x, m, m1)
        r = max(r, m)
print(r)

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
V = [int(v) for v in input().split()]

ans = 0
for i in range(min(N+1,K+1)):
  que = V[:i]
  for j in range(min(N+1-i,K+1-i)):
    que += V[N-j:]
    que.sort()
    for k in range(min(K+1-i-j,i+j+1)):
      ans = max(ans,sum(que[k:]))
print(ans)

Submission status: Wrong Answer

Solution code:
#128d
from collections import deque

N,K = map(int, input().split()) #K<=100
V_list = list(map(int, input().split()))

#D に対して以下の 4 種類の操作から 1 つを選んで実行することを K回まで行うことができます。
#操作 A: Dに詰められた宝石のうち、左端の宝石を取り出して手に入れる。Dが空の場合、この操作を行えない。
#操作 B: Dに詰められた宝石のうち、右端の宝石を取り出して手に入れる。Dが空の場合、この操作を行えない。
#操作 C: 持っている宝石を 1つ選んで Dの左端に詰める。宝石を持っていない場合、この操作を行えない。
#操作 D: 持っている宝石を 1つ選んで D の右端に詰める。宝石を持っていない場合、この操作を行えない。

#操作CDは等価。負の値が最大値を詰めればOK

ans = 0 

#ABで全て探索
for i in range(0,min(N,K)+1):
    for j in range(0,i+1):
        max_discard = min(min(N,K)-i,i)
        #print("A:",j," B:",i-j," max_discard:",max_discard)
        result = V_list[0:j]+V_list[N-(i-j):] #指定回数を左右から取ったリストを作る
        result.sort(reverse=True)
        #print(result)
        
        for _ in range(0,max_discard):
            last = result.pop(-1)            
            #print("poped:",last)
            
            if last > 0:
                total = sum(result) + last
                #print(result,last,":",total)
                
                if ans < total:
                    ans = total
        
                break
        else:
            total = sum(result)
            #print(result,":",total)
                
            if ans < total:
                ans = total

print(ans)

Submission status: Wrong Answer

Solution code:
import heapq

N,K = map(int,input().split())
V = list(map(int,input().split()))
ans = -float('inf')
for ai in range(K+1):
  for bi in range(K+1):
    if ai+bi > min(K,N): continue
    have = []
    if ai != 0: [heapq.heappush(have, v) for v in V[:ai]]
    if bi != 0: [heapq.heappush(have, v) for v in V[N-bi:]]
    for i in range(K-ai-bi):
      if len(have) != 0: heapq.heappop(have)
    ans = max(ans,sum(have))
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq

N,K = map(int,input().split())
V = list(map(int,input().split()))
ans = -float('inf')
for ai in range(K+1):
  for bi in range(K+1):
    if ai+bi > min(K,N): continue
    have = []
    if ai != 0: [heapq.heappush(have, v) for v in V[:ai]]
    if bi != 0: [heapq.heappush(have, v) for v in V[-bi:]]
    for i in range(K-ai-bi):
      if len(have) != 0: heapq.heappop(have)
    ans = max(ans,sum(have))
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq

N,K = map(int,input().split())
V = list(map(int,input().split()))
ans = -float('inf')
for ai in range(K+1):
  for bi in range(K+1):
    if ai+bi > min(K,N): continue
    have = []
    if ai != 0: [heapq.heappush(have, v) for v in V[:ai]]
    if bi != 0: [heapq.heappush(have, v) for v in V[-bi:]]
    for i in range(K-ai-bi+1):
      if len(have) != 0: heapq.heappop(have)
    ans = max(ans,sum(have))
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq

N,K = map(int,input().split())
V = list(map(int,input().split()))
ans = -float('inf')
for ai in range(K+1):
  for bi in range(K+1):
    if ai+bi > K or ai > N or bi > N: continue
    have = []
    if ai != 0: [heapq.heappush(have, v) for v in V[:ai]]
    if bi != 0: [heapq.heappush(have, v) for v in V[-bi:]]
    for i in range(K-ai-bi+1):
      if len(have) != 0: heapq.heappop(have)
    ans = max(ans,sum(have))
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq

N,K = map(int,input().split())
V = list(map(int,input().split()))
ans = -float('inf')
for ai in range(K+1):
  for bi in range(K+1):
    if ai+bi > K or ai > N or bi > N: continue
    have = []
    if ai != 0: [heapq.heappush(have, v) for v in V[:ai]]
    if bi != 0: [heapq.heappush(have, v) for v in V[-bi:]]
    for i in range(K-ai-bi):
      if len(have) != 0: heapq.heappop(have)
    ans = max(ans,sum(have))
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq

N,K = map(int,input().split())
V = list(map(int,input().split()))
ans = -float('inf')
for ai in range(K+1):
  for bi in range(K+1):
    if ai+bi > K: continue
    have = []
    if ai != 0: [heapq.heappush(have, v) for v in V[:ai]]
    if bi != 0: [heapq.heappush(have, v) for v in V[-bi:]]
    for i in range(K-ai-bi):
      if len(have) != 0: heapq.heappop(have)
    ans = max(ans,sum(have))
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq

N,K = map(int,input().split())
V = list(map(int,input().split()))
ans = -float('inf')
for ai in range(K):
  for bi in range(K):
    if ai+bi > K: continue
    have = []
    if ai != 0: [heapq.heappush(have, v) for v in V[:ai]]
    if bi != 0: [heapq.heappush(have, v) for v in V[-bi:]]
    for i in range(K-ai-bi):
      if len(have) != 0: heapq.heappop(have)
    ans = max(ans,sum(have))
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import combinations

N, K = map(int,input().split())
A = list(map(int,input().split()))

ans=0

if len(A)<=K:
  l = sorted(A)
  ans = max(ans,sum(l[K-len(A):]))

for i,j in combinations(range(N+2),2):
  l = sorted(A[0:i]+A[j-1:N])
  if len(l)<=K:
  	ans = max(ans,sum(l[K-len(l):]))
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import combinations

N, K = map(int,input().split())
A = list(map(int,input().split()))

ans=0

if len(A)<=K:
  l = sorted(A)
  ans = max(ans,sum(l[K-len(A):]))

for i,j in combinations(range(N+1),2):
  l = sorted(A[0:i]+A[j:N])
  if len(l)<=K:
  	ans = max(ans,sum(l[K-len(l):]))
print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
V = list(map(int, input().split()))


ret = -1 * 10**7 * 50 

for left in range(K):
    for right in range(K-left):
        if left + right > N:
            continue

        disposable = K - right - left
        
        chosen = V[:left] +  V[N - right:]
        chosen.sort()
        chosen_count = sum(chosen)

        dispoase_value = 0
        for i in range(disposable):
            if i >= len(chosen):
                break
            if chosen[i] >= 0:
                break
            dispoase_value += chosen[i]


        val = chosen_count - dispoase_value

        ret = max(ret, val)

print(ret)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
V = list(map(int, input().split()))


ret = 0

for left in range(K):
    for right in range(K-left):
        if left + right > N:
            continue

        disposable = K - right - left
        
        chosen = V[:left] +  V[N - right:]
        chosen.sort()
        chosen_count = sum(chosen)

        dispoase_value = 0
        for i in range(disposable):
            if i >= len(chosen):
                break
            if chosen[i] >= 0:
                break
            dispoase_value += chosen[i]


        val = chosen_count - dispoase_value

        ret = max(ret, val)

print(ret)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
V = list(map(int, input().split()))


ret = 0

for left in range(K):
    for right in range(K-left):
        if left + right > N:
            continue

        disposable = K - right - left
        
        chosen = V[:left] +  V[N - right:]
        chosen.sort()
        chosen_count = sum(chosen)

        dispoase_value = 0
        dispoase_count= 0
        for i in range(len(chosen)):
            if chosen[i] >= 0:
                break
            if dispoase_count >= disposable:
                break
            dispoase_value += chosen[i]
            dispoase_count += 1


        val = chosen_count - dispoase_value

        ret = max(ret, val)

print(ret)

Submission status: Wrong Answer

Solution code:
import heapq
from collections import deque

N,K = input().split()
q = [int(e) for e in input().split()]
deq = deque(q)
count_min = min([int(N),int(K)])

A_all = []
for i in range(count_min+1):
    for j in range(i+1):
        deq = deque(q)
        A = []
        A_count = j
        B_count = i - j
        count = 0

        for a in range(A_count):
            A.append(deq[0])
            deq.popleft()
        for b in range(B_count):
            A.append(deq[-1])
            deq.pop()
        A.sort()
        A_sum = sum(A)
        for z in range(count_min-(A_count+B_count)):
            if z >= A_count+B_count:
                break;
            if A[z] >= 0:
                break;
            else:
                A_sum += -(A[z])
        #print(A)
        A_all.append(A_sum)

print(max(A_all))

Submission status: Wrong Answer

Solution code:
import heapq
from collections import deque

N,K = input().split()
q = [int(e) for e in input().split()]
deq = deque(q)
count_min = min([int(N),int(K)])

A_all = []
for i in range(count_min+1):
    for j in range(i+1):
        deq = deque(q)
        A = []
        A_count = j
        B_count = i - j
        count = 0

        for a in range(A_count):
            A.append(deq[0])
            deq.popleft()
        for b in range(B_count):
            A.append(deq[-1])
            deq.pop()

        for z in range(count_min-(A_count+B_count)):
            if len(A) == 0:
                break;
            if min(A) < 0:
                A.remove(min(A))
        #print(A)
        A_all.append(sum(A))

print(max(A_all))

Submission status: Wrong Answer

Solution code:
import heapq
from collections import deque

N,K = input().split()
q = [int(e) for e in input().split()]
deq = deque(q)
count_min = min([int(N),int(K)])
#print(count_min)
A_all = []
for i in range(count_min+1):
    for j in range(i+1):
        deq = deque(q)
        A = []
        A_count = j
        B_count = i - j
        count = 0

        for a in range(A_count):
            A.append(deq[0])
            deq.popleft()
        for b in range(B_count):
            A.append(deq[-1])
            deq.pop()

        for z in range(count_min-(A_count+B_count)):
            if len(A) == 0:
                break;
            A.remove(min(A))
        #print(A)
        A_all.append(sum(A))

print(max(A_all))

Submission status: Wrong Answer

Solution code:
# -*- coding:utf-8 -*-
import sys
import heapq


def solve():
    N, K = list(map(int, sys.stdin.readline().split()))
    Vs = list(map(int, sys.stdin.readline().split()))

    ans = 0
    for i in range(0, N+1):
        for j in range(0, N+1):
            if i+j > K: break

            if i+j <= N:
                _Vs = Vs[::-1]
                have = Vs[0:i]+_Vs[0:j]
                have.sort(reverse=True)
            else:
                have = Vs

            M = i+j
            while M < K:
                if len(have) == 0: break
                if have[-1] < 0:
                    have.remove(have[-1])
                    M += 1
                    continue
                break

            ans = max(ans, sum(have))

    print(ans)



if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
# -*- coding:utf-8 -*-
import sys
import heapq


def solve():
    N, K = list(map(int, sys.stdin.readline().split()))
    Vs = list(map(int, sys.stdin.readline().split()))

    ans = 0
    for i in range(0, N+1):
        for j in range(0, N+1):
            if i+j > K: break

            if i+j <= N:
                _Vs = Vs[::-1]
                have = Vs[0:i]+_Vs[0:j]
                have.sort(reverse=True)
            else:
                have = Vs
            M = i+j
            while M < K:
                if len(have) == 0: break
                if have[-1] < 0:
                    have.remove(have[-1])
                    M += 1
                break

            ans = max(ans, sum(have))

    print(ans)



if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
# -*- coding:utf-8 -*-
import sys
import heapq


def solve():
    N, K = list(map(int, sys.stdin.readline().split()))
    Vs = list(map(int, sys.stdin.readline().split()))

    ans = 0
    for i in range(0, N+1):
        for j in range(0, N+1):
            if i+j > K: break

            _Vs = Vs[::-1]
            have = Vs[0:i]+_Vs[0:j]
            have.sort(reverse=True)
            M = i+j
            while M < K:
                if len(have) == 0: break
                if have[-1] < 0:
                    have.remove(have[-1])
                    M += 1
                break

            ans = max(ans, sum(have))

    print(ans)



if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
from collections import Counter,defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n,k = inpl()
v = inpl()
m = min(n,k)
ans = 0
for a in range(m):
    for b in range(m):
        if a+b > m:
            continue
        q = deque(v)
        tmp = []
        for i in range(a):
            tmp.append(q.popleft())
        for j in range(b):
            tmp.append(q.pop())
        if k - (a + b) > 0:
            for i in range(k-(a+b)):
                tmp.sort()
                if not tmp:
                    break
                if tmp[0] < 0:
                    tmp.pop(0)
                else:
                    break
        ans = max(ans, sum(tmp))
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter,defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n,k = inpl()
v = inpl()
m = min(n,k)
ans = 0
for a in range(m):
    for b in range(m):
        if a+b > m:
            continue
        q = deque(v)
        tmp = [0]
        for i in range(a):
            tmp.append(q.popleft())
        for j in range(b):
            tmp.append(q.pop())
        if k - (a + b) > 0:
            for i in range(k-(a+b)):
                tmp.sort()
                if not tmp:
                    break
                if tmp[0] < 0:
                    tmp.pop(0)
                else:
                    break
        ans = max(ans, sum(tmp))
print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int,input().split(' '))
V = list(map(int,input().split(' ')))

# 左からのリスト
Vl=[0]
Dl=[[]]
for l in range(N):
    tmpV = sum(V[0:l+1])
    Vl.append(tmpV)
    tmpD =[]
    for i in range(l+1):
        if V[i] <= 0:
            tmpD.append(V[i])
    Dl.append(tmpD)

#print(Vl)
#print(Dl)

# 右からのリスト
Vr=[0]
Dr=[[]]
for r in range(N-1,-1,-1):
    tmpV = sum(V[r:])
    Vr.append(tmpV)
    tmpD =[]
    for i in range(N-1,r-1,-1):
        if V[i] <= 0:
            tmpD.append(V[i])
    Dr.append(tmpD)

#print(Vr)
#print(Dr)

max=0
# ここで比べる
for l in range(N+1):
    for r in range(N+1):
        for d in range(len(Dl[l])+len(Dr[r])+1 ):
            #print(l,r,d)
            if l + r +d > K:
                continue
            else:
                tmpD=Dl[l]
                tmpD.extend(Dr[r])
                tmpD.sort()
                tmpDsum=-1*sum(tmpD[0:d])

                if Vl[l]+Vr[r]+tmpDsum > max:
                    max = Vl[l]+Vr[r]+tmpDsum

print(max)

Submission status: Wrong Answer

Solution code:
N, K = map(int,input().split())
V = list(map(int,input().split()))

m = min(N,K)
ans = 0
for i in range(m):
    for a in range(i+1):
        b = i-a
        if b != 0:
            X = V[:a] + V[-b:]
        else:
            X = V[:a]
        X.sort()
        value = sum(X)
        for e in X[:min((K-i),a+b)]:
            if e < 0:
                value -= e
            else:
                break
        if value > ans:
            ans = value
print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
V = list(map(int, input().split()))

ans = 0
for i in range(min(N, K) + 1):
    for j in range(i+1):
        Juel = V[:j] + V[N-i+j:]
        Juel.sort()
        sum_v = 0
        for k in range(min(K-i, i)):
            Juel[k] = max(Juel[k], 0)
        ans = max(ans, sum(Juel))
    print(ans)
print(ans)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
v = list(map(int,input().split()))
nk = min(n,k)
can = []
left = []
for i in range(nk+1):
  if i != 0:
    left.append(v[i-1])
  right = []
  for j in range(n-nk+1):
    if j != 0:
      right.append(v[-j])
    tmp = left + right
    tmp.sort()
    now = sum(tmp)
    rest = min(k-i-j,len(tmp))
    for h in range(rest):
      if tmp[h] < 0:
        now -= tmp[h]
    can.append(now)
    #print(i,j,now)
print(max(can))

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    a, p = LI()
    print((a*3+p)//2)
    return

#B
def B():
    n = II()
    sp = []
    for i in range(n):
        sp.append(input().split())
    another = [(s[0], -1 * int(s[1]),num) for num,s in enumerate(sp)]
    another.sort()
    for s,p,q in another:
        print(q+1)

    return

#C
def C():
    n, m = LI()
    ks = LIR_(m)
    p = LI()
    patern = itertools.product(range(2), repeat=n)
    ans = 0
    for on in patern:
        ki = [0 for i in range(m)]
        for num, oni in enumerate(on):
            if oni:
                for i,ksi in enumerate(ks):
                    ksi = ksi[1::]
                    if num in ksi:
                        ki[i] ^= 1
        for num, pi in enumerate(p):
            if pi != ki[num]:
                break
        else:
            ans += 1
    print(ans)

            
    return

#D
def D():
    N, K = LI()#random.randint(1,50),random.randint(1,100)
    v = LI()#[random.randint(-10 ** 2, 10 ** 2) for i in range(N)]
    ans = 0
    for a in range(min(N, K) + 1):
        for b in range(min(N, K) + 1):
            if a + b > min(K,N):
                break
            if a == b == 0:
                continue
            deletes = K - a - b
            left = v[:a]
            right = v[:-b-1:-1]
            x = left + right
            x.sort()
            tmp = sum(x)
            for delete in range(min(deletes, len(x))):
                if x[delete] >= 0:
                    break
                tmp -= x[delete]
                ans = max(ans,tmp)
    
    print(ans)
                

    return

#E
def E():
    return

#F
def F():
    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    a, p = LI()
    print((a*3+p)//2)
    return

#B
def B():
    n = II()
    sp = []
    for i in range(n):
        sp.append(input().split())
    another = [(s[0], -1 * int(s[1]),num) for num,s in enumerate(sp)]
    another.sort()
    for s,p,q in another:
        print(q+1)

    return

#C
def C():
    n, m = LI()
    ks = LIR_(m)
    p = LI()
    patern = itertools.product(range(2), repeat=n)
    ans = 0
    for on in patern:
        ki = [0 for i in range(m)]
        for num, oni in enumerate(on):
            if oni:
                for i,ksi in enumerate(ks):
                    ksi = ksi[1::]
                    if num in ksi:
                        ki[i] ^= 1
        for num, pi in enumerate(p):
            if pi != ki[num]:
                break
        else:
            ans += 1
    print(ans)

            
    return

#D
def D():
    N, K = LI()#random.randint(1,50),random.randint(1,100)
    v = LI()#[random.randint(-10 ** 2, 10 ** 2) for i in range(N)]
    ans = 0
    for a in range(min(N, K) + 1):
        for b in range(min(N, K) + 1):
            if a + b > min(K,N):
                break
            deletes = K - a - b
            left = v[:a]
            right = v[:-b-1:-1]
            x = left + right
            x.sort()
            tmp = sum(x)
            for delete in range(min(deletes, len(x))):
                if x[delete] >= 0:
                    break
                tmp -= x[delete]
                ans = max(ans,tmp)
    
    print(ans)
                

    return

#E
def E():
    return

#F
def F():
    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    a, p = LI()
    print((a*3+p)//2)
    return

#B
def B():
    n = II()
    sp = []
    for i in range(n):
        sp.append(input().split())
    another = [(s[0], -1 * int(s[1]),num) for num,s in enumerate(sp)]
    another.sort()
    for s,p,q in another:
        print(q+1)

    return

#C
def C():
    n, m = LI()
    ks = LIR_(m)
    p = LI()
    patern = itertools.product(range(2), repeat=n)
    ans = 0
    for on in patern:
        ki = [0 for i in range(m)]
        for num, oni in enumerate(on):
            if oni:
                for i,ksi in enumerate(ks):
                    ksi = ksi[1::]
                    if num in ksi:
                        ki[i] ^= 1
        for num, pi in enumerate(p):
            if pi != ki[num]:
                break
        else:
            ans += 1
    print(ans)

            
    return

#D
def D():
    N, K = LI()#random.randint(1,50),random.randint(1,100)
    v = LI()#[random.randint(-10 ** 2, 10 ** 2) for i in range(N)]
    ans = 0
    for a in range(min(N, K) + 1):
        for b in range(min(N, K) + 1):
            if a + b > K:
                break
            deletes = K - a - b
            left = v[:a]
            right = v[:-b-1:-1]
            x = left + right
            x.sort()
            tmp = sum(x)
            for delete in range(min(deletes, len(x))):
                if x[delete] >= 0:
                    break
                tmp -= x[delete]
                ans = max(ans,tmp)
    
    print(ans)
                

    return

#E
def E():
    return

#F
def F():
    return

#Solve
if __name__ == '__main__':
    D()