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.

Solution (Python):



N,K = map(int,input().split())
V = [int(x) for x in input().split()]

max_value = 0 

for L in range(N+1):
  for R in range(N+1):
    if L+R > K:
      break
    if L+R > N:
      break
    
    get = V[:L]
    if R > 0:
      get += V[-R:]
    get.sort()
    rest = K - (L+R)
    minus = sum((1 if x < 0 else 0 for x in get))
    if minus > rest:
      value = sum(get[rest:])
    else:
      value = sum((x for x in get if x > 0))
    if value > max_value:
      max_value = value
    
      
      
   
print(max_value)

Solution (Python):
N,K=map(int,input().split())
V=list(map(int,input().split()))
total = 0
if N<=K:
  for i in range(N):
    if V[i] > 0:
      total += V[i]
  print(total)
else:
  max = 0
  for L in range(K+1):
    for R in range(K-L+1):

      p = K-L-R
      V0 = []
      if L>0:
        V0 = V0 + V[0:L]

      if R>0:
        V0 = V0 + V[N-R:N]

      V0.sort()

      for ii in range(len(V0)):
        if p <= 0:
            break
        if V0[ii] < 0:
          V0[ii] = 0
          p -= 1
        else:
          break

      su = sum(V0)

      if max < su:
        max = su
  print(max)

Solution (Python):
N, K = map(int, input().split())
d = list(map(int, input().split()))
left = [0]
left_m = []
right = [0]
right_m = []
for i, l, r in zip(range(K), d, d[::-1]):
    left.append(left[i] + l)
    left_m.append(l if l < 0 else 0)
    right.append(right[i] + r)
    right_m.append(r if r < 0 else 0)
point = 0
m = min(N, K)
for i in range(m + 1):
    for j in range(m - i + 1):
        p = K - i - j
        minus = list(sorted(left_m[:i] + right_m[:j]))
        point = max(point, left[i] + right[j] - sum(minus[:p]))
print(point)

Solution (Python):
n, k = map(int, input().split())
v = list(map(int, input().split()))
ret = 0
for l in range(min(n, k) + 1):
    for r in range(min(n, k) - l + 1):
        d = k - l - r
        g = sorted(v[:l] + v[n - r:])
        for i in range(min(d, len(g))):
            g[i] = max(0, g[i])
        ret = max(ret, sum(g))
print(ret)

Solution (Python):
N, K = map(int, input().split())
Vs = list(map(int, input().split()))

ans = 0
for x in range(1, min(K, N)+1):
    for i in range(x+1):
        Ts = Vs[:i] + Vs[N-(x-i):]
        sumOut = sum(Ts)
        Ts.sort()

        for T in Ts[:K-x]:
            if T < 0:
                sumOut -= T
            else:
                break

        ans = max(ans, sumOut)

print(ans)

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

s = 0
for i in range(min(K, N)+1):
    res = K - i
    for j in range(i+1):
        k = i - j

        Q = sorted(V[:j] + V[N-k:])
        minus = sum([q < 0 for q in Q])
        score = sum(Q[min(minus, res):])
        s = max(s, score)

print(s)

Solution (Python):
a,k=map(int,input().split())
L=list(map(int,input().split()))
ans=0

for i in range(min(k,a)+1):
  for j in range(min(k,a)-i+1):
    S=[0]+L[:i]+L[a-j:]
    S.sort()
    x=0
    while x < k-(j+i):
      if S[x]>=0:
        break
      x+=1
    ans=max(ans,sum(S)-sum(S[:x]))
    
print(ans)

Solution (Python):
N, K = map(int, input().split())
V = list(map(int, input().split()))
Vi = [i+1 for i in range(len(V))]
V.extend(V)
Vi.extend(Vi)
ans = 0
for k in range(1, min(K+1, N+1)):
    for s in range(len(V)):
        part_Vi = Vi[s:s+k]
        if 1 not in part_Vi and N not in part_Vi:
            continue
        can_remove = K - k
        part_V = V[s:s+k]
        part_V = sorted(part_V)
        plus_i = 0
        for v in part_V:
            if can_remove <= 0:
                break
            if v < 0:
                plus_i += 1
                can_remove -= 1
            else:
                break
        ans = max(ans, sum(part_V[plus_i:]))
print(ans)

Solution (Python):
N,K = map(int, input().split())
v_list = list(map(int,input().split()))


def func(n):
    lri = []
    for l in range(n+1):
        for r in range(n-l+1):
            for i in range(n-l-r+1):
                if i>l+r:
                    continue
                if l+r >N:
                    continue
                lri.append([l,r,i])
    return lri

lri_list = func(K)

result = 0
for l,r,i in lri_list:

    if r>0:
        tmp_v = v_list[:l] + v_list[-r:]
    else:
        tmp_v = v_list[:l]

    tmp_v = sorted(tmp_v)

    
    tmp_sum = sum(tmp_v)
    
    for v in tmp_v:
        if i<=0:
            break
        if v<0:
            tmp_sum += -v
            i -= 1
    if result < tmp_sum:
        result = tmp_sum

print(result)

Solution (Python):
from sys import stdin

n, k = [int(x) for x in stdin.readline().rstrip().split()]
v = list(map(int, input().split()))

l = [ [(0, [])]*(k+1) for _ in range(k+1)]

left=0
right=0
for i in range(k+1):
  left=0
  for j in range(k+1):
    if i==0 and j==0:
        continue

    if len(v) < (i+j):
        break
    if k < (i+j):
        break
    if j==0:
      item = v[(n-1)-right]
      right +=1
      l[i][j] = (l[i-1][j][0]+item,l[i-1][j][1]+[item])
      continue
    item = v[left]
    left +=1
    l[i][j] = (l[i][j-1][0]+item,l[i][j-1][1]+[item])




ans = 0
for i in range(k+1):
  for j in range(k+1):
    if k < (i+j):
      break
    value = l[i][j][0]
    if ( k != (i+j)):
        itemlist = l[i][j][1]
        itemlist.sort()
        
        for ii in range (k-(i+j)):
           if len(itemlist) <= ii:
               break
           if 0 < itemlist[ii]:
               break
           value -= itemlist[ii]
        
    ans = max(ans, value)

print(ans)

Solution (Python):
import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def II(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def SI(): return input()
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')

def main():
    N, K = LI()
    V_li = LI()

    maximum = 0
    for take_count in range(min(K+1, N)):
        for take_left in range(take_count+1):
            
            took = V_li[:take_left] + ([] if take_count == take_left else V_li[-(take_count - take_left):])
            took = sorted(took)
            for trash_count in range(K - take_count):
                if took and took[0] < 0:
                    took.pop(0)
                else:
                    break
            if not took:  
                 took = [0]
            
            maximum = max(maximum, sum(took))
    if N==1:
        maximum = max(0, V_li[0])
    if K >= N:
        maximum = max(maximum, sum(V_li))

    print(maximum)


main()

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

s = 0
for i in range(min(K, N)+1):
    res = K - i
    for j in range(i+1):
        k = i - j

        Q = sorted(V[:j] + V[N-k:])
        minus = sum([q < 0 for q in Q])
        score = sum(Q[min(minus, res):])
        s = max(s, score)

print(s)

Solution (Python):
n,k = map(int,input().split())
V = [0]+list(map(int,input().split()))+[0]
S = [0]
for v in V[1:-1]:
    S.append(S[-1]+v)

ans = 0
leftminus = []
leftm = 0
for left in range(min(n+1,k+1)):
    if V[left] < 0:
        leftminus.append(V[left])
        leftm += 1
    for right in range(n+1,left,-1):
        rightminus = []
        tempans = S[left]
        times = left + n - right + 1
        rm = leftm
        if times > k:
            break
        for v in V[right:]:
            tempans += v
            if v < 0:
                rightminus.append(v)
                rm += 1
        minus = rightminus+leftminus
        minus.sort()
        for j in range(min(k-times,rm)):
            tempans -= minus[j]
        if ans < tempans:
            ans = tempans
print(ans)

Solution (Python):
def inpl():
    return list(map(int, input().split()))


N, K = inpl()
V = inpl()
left_sum = [sum(V[:i]) for i in range(N + 1)]
right_sum = [sum(V[::-1][:i]) for i in range(N + 1)]

ans = 0
for left_k in range(K + 1):
    for right_k in range(K + 1 - left_k):
        if left_k + right_k > N:
            break

        
        
        tmp_ans = left_sum[left_k] + right_sum[right_k]
        if left_k == 0 and right_k == 0:
            A = []
        elif left_k == 0:
            A = V[-1 * right_k:]
        elif right_k == 0:
            A = V[:left_k]
        else:
            A = V[:left_k] + V[-1 * right_k:]

        A.sort()
        rest = K - left_k - right_k
        i = 0
        while i < len(A) and A[i] < 0 and i < rest:
            tmp_ans -= A[i]
            i += 1
        
        ans = max(ans, tmp_ans)

print(ans)

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

ans = 0

for m1 in range(N+1):
    for m2 in range(N-m1+1):
        for l in range(m1+m2+1):
            if m1 + m2 + l > K: continue
            if m1 + m2 > N: continue
            tmp = V[0:m1] + V[N-m2:N]
            tmp.sort(reverse = True)
            ans = max(ans,sum(tmp[0:m1+m2-l]))
print(ans)

Solution (Python):
N,K = list(map(int,input().split(" ")))
Vs = list(map(int,input().split(" ")))
rev = Vs[::-1]
ans = -(10e15)
for b in range(K+1):
    lr = min(K - b,N)
    for l in range(lr + 1):
        rlim = min(lr - l,N)
        for r in range(rlim+1):
            temoti = []
            temoti.extend(Vs[:l])
            temoti.extend(rev[:r])
            temoti.sort()
            tempans = sum(temoti)
            toridasi = 0
            for num in temoti:
                if toridasi == b: 
                    break
                if num < 0:
                    tempans -= num
                    toridasi += 1
                else:
                    break

            if tempans > ans:
                ans = tempans
print(ans)

Solution (Python):
from heapq import heappush, heappop
from collections import deque

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

ans = 0

for i in range(K+1):
    sup = min(i,N)
    for l in range(sup+1):
        for r in range(sup+1-l):
            j = min(i-r-l,r+l)
            hq = []
            dq = deque(V)
            for _ in range(l):
                item = dq.popleft()
                heappush(hq, item)
            for _ in range(r):
                item = dq.pop()
                heappush(hq, item)
            for _ in range(j):
                heappop(hq)
            res = sum(hq)
            ans = max(ans,res)

print(ans)

Solution (Python):
N, K = map(int, input().split())
Vs = list(map(int, input().split()))

ans = 0
for x in range(1, min(K, N)+1):
    for i in range(x+1):
        Ts = Vs[:i] + Vs[N-(x-i):]
        sumOut = sum(Ts)
        Ts.sort()

        for T in Ts[:K-x]:
            if T < 0:
                sumOut -= T
            else:
                break

        ans = max(ans, sumOut)

print(ans)

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

ans = 0
for i in range(1, K+1):
    enq = K - i
    for j in range(i+1):
        combi = V[:i-j] + V[N-j:]
        tmp = sum(combi)
        ans = max(ans, tmp)
        for _ in range(enq):
            combi.remove(min(combi))
            if sum(combi) <= tmp:
                break
            else:
                tmp = sum(combi)
                ans = max(ans, tmp)
                if not combi:
                    break
        if i >= N:
            break

print(ans)

Solution (Python):
inpl = lambda: list(map(int,input().split()))
N, K = inpl()
V = inpl()
Nneg = len(list(filter(lambda x: x < 0, V)))
Vneg = sorted(list(enumerate(V)),key=lambda x: x[1])[:Nneg]

if K >= Nneg + N:
    print(sum(list(map(lambda x: x if x>0 else 0, V))))
    exit()

ans = 0
for i in range(Nneg+1):
    L = K - i
    if L > N:
        continue

    for j in range(L):
        S = sum(V[:L-j]) + sum(V[N-j:])
        k = 0
        for n, v in Vneg:
            if k >= i:
                break
            elif n < L-j or N-j <= n:
                S -= v
                k += 1
        if S > ans:
            ans = S

print(ans)

Solution (Python):
n, k = map(int, input().split())
a = [int(x) for x in input().split()]
mx = 0
for i in range(min(n, k + 1)):
	for j in range(min(k - i + 1, n - i + 1)):
		summa = 0
		b = []
		for t in range(i):
			b.append(a[t])
		for t in range(n - j, n):
			b.append(a[t])
		z = k - i - j
		b.sort()
		for x in b:
			if x < 0 and z > 0:
				z -= 1
			else:
				summa += x
		mx = max(mx, summa)
print(mx)

Solution (Python):
N,K = map(int,input().split())
V = list(map(int,input().split()))
answer = 0
for i in range(min(N,K)+1):
    for j in range(min(N,K)+1-i):
        tempV = V[0:i]+V[N-j:] + [0]
        tempV.sort()
        for k in range(K-i-j):
            if tempV[0] < 0:
                tempV.pop(0)
        if sum(tempV) > answer:
            answer = sum(tempV)
            
print(answer)

Solution (Python):
from heapq import heappop, heappush

def getlist():
	return list(map(int, input().split()))

N, K = getlist()
V = getlist()
VV = [V[-1 - i] for i in range(N)]

ans = 0
for i in range(K + 1):
	if i == 0:
		pass
	elif i >= N:
		Q = []
		for j in V:
			heappush(Q, j)
		for j in range(K - N):
			if Q:
				if Q[0] < 0:
					heappop(Q)
				else:
					break
		val = sum(Q)
		if val > ans:
			ans = val

	else:
		for a in range(i + 1):
			Q = []
			b = i - a
			
			for x in range(a):
				heappush(Q, V[x])
			for x in range(b):
				heappush(Q, VV[x])
			for j in range(K - i):
				if Q:
					if Q[0] < 0:
						heappop(Q)
					else:
						break
			val = sum(Q)
			if val > ans:
				ans = val

print(ans)

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, K, V):
    ans = 0
    for k in range(min(K, N)+1):
        for i in range(k+1):
            l = V[:i]
            r = V[N-(k-i):]
            
            lr = l + r
            lr.sort(reverse=True)

            for _ in range(K-k):
                if lr and lr[-1] < 0:
                    lr.pop()
                else:
                    break
            ans = max(ans, sum(lr))

    return ans


def main():
    N, K = read_int_n()
    V = read_int_n()
    print(slv(N, K, V))


if __name__ == '__main__':
    main()

Solution (Python):
N, K = list(map(int, input().split()))
Vs = list(map(int, input().split()))
Length = len(Vs)
maxv = 0
for i in range(K + 1):
    count = K - i
    left = count
    right = 0
    for m in range(count + 1):
        if 0 <= left <= Length and 0 <= right <= Length:
            for p in range(i + 1):
                temp = sorted(Vs[:left] + Vs[Length - right:])
                for o in range(p):
                    if temp:
                        temp.pop(0)
                    else:
                        break
                sumv = sum(temp)
                if sumv > maxv:
                    maxv = sumv
            left -= 1
            right += 1

print(maxv)

Solution (Python):


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

def max_choice(V, n, m):
    if len(V) <= n:
        n = len(V)
    a = -999999999
    for i in range(n+1):
        tlist = V[:i]
        tlist.extend(V[len(V)-n+i:])
        tlist.sort()
        for j in range(m):
            if tlist[j]<0:
                tlist[j] = 0
            else:
                break       
        a = max(a, sum(tlist))
    return a

ans = 0
for i in range(1, min(N, K)+1):
    ans = max(max_choice(V, i, min(K-i, i-1)), ans)
    
print(ans)

Solution (Python):
N, K = map(int, input().split())
V = [int(i) for i in input().split()]
L = [0] * (N+1)
R = [0] * (N+1)
L_m = [[] for _ in range(N+1)]
R_m = [[] for _ in range(N+1)]

for i in range(1, N+1):
    L[i] = L[i-1] + V[i-1]
    R[i] = R[i-1] + V[-i]
    L_m[i] = L_m[i-1].copy()
    R_m[i] = R_m[i-1].copy()
    if V[i-1] < 0:
        L_m[i].append(V[i-1])
    if V[-i] < 0:
        R_m[i].append(V[-i])

ans = 0

for i in range(K+1):
    for l in range(K+1-i):
        r = K - i - l
        if l + r >= N:
            ans = max(ans, R[-1] - sum(R_m[-1]))
            break
        if r < 0:
            break
        M = L_m[l] + R_m[r]
        M.sort()
        if len(M) >= i:
            m = sum(M[:i])
        else:
            m = sum(M)
        a = L[l] + R[r] - m
        ans = max(ans, a)

print(ans)

Solution (Python):
n,k = list(map(int, input().split()))
v = list(map(int, input().split()))

dp=[[[-1 for i in range(k+1)] for j in range(n+1)] for l in range(n+1)]

def f(a, b, d):
    if d == 0: return 0
    if a == b and d > 1 and v[a] > 0: return v[a]
    if a == b and d > 1 and v[a] <= 0: return 0
    if dp[a][b][d] != -1: return dp[a][b][d]
    maxi = max(v[a] + f(a+1, b, d - 1), v[b] + f(a, b - 1, d - 1))
    if v[a] < 0 and d > 1:
        maxi = max(maxi, f(a + 1, b, d - 2))
    if v[b] < 0 and d > 1:
        maxi = max(maxi, f(a, b - 1, d - 2))
    maxi = max(maxi, 0)
    dp[a][b][d]=maxi
    return maxi


print(f(0, n-1, k))

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

max_score = 0
for i in range(N+1):
    for j in range(N+1):
        if not (i+j>K or i+j>N):
    
            H=V[:i]+V[N-j:]
            H.sort()
            suteru=[]
            for k in range(min(len(H),K-i-j)):
                if H[k]>0:
                    break
                else:
                    suteru.append(H[k])
            max_score=max(sum(H)-sum(suteru),max_score)
       
print(max_score)

Solution (Python):
n,k = map(int,raw_input().split())
v = map(int,raw_input().split())
best = 0
for i in xrange(min(n,k+1)):
	for j in xrange(min(n+1-i,k+1-i)):
		take = v[0:i]+v[n-j:]
		rid = k-i-j
		take = sorted(take)
		temp = sum(take)
		for x in xrange(min(rid,len(take))):
			if take[x] < 0:
				temp -= take[x]
		if temp > best:
			best = temp
print best

Solution (Python):
n, k = map(int, input().split())
v = list(map(int, input().split()))
sum_jewel = []
for i in range(1, min(n, k)+1):
    for j in range(i+1):
        take = v[:j] + v[n-i+j:]
        take.sort()
        for l in range(k-i):
            try:
                if take[0] < 0:
                    del take[0]
            except:
                pass
        value = 0
        for m in range(len(take)):
            value += take[m]
        sum_jewel.append(value)
print(max(sum_jewel))

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




now_max = 0
for i in range(1, min(K+1, N+1)):
  for offset in range(i+1):
    jewel = sorted(V[-offset+N: -offset+i+N])
    remain_del = K-i
    while True:
      if len(jewel) == 0 or remain_del == 0 or jewel[0] > 0:
        break
      jewel.pop(0)
      remain_del -= 1
    now_max = max(now_max, sum(jewel))
print(now_max)

Solution (Python):

import copy
import random
import bisect 
import fractions 
import math
import sys

mod = 10**9+7
sys.setrecursionlimit(mod) 

N,K = map(int,input().split())
V = [int(i) for i in input().split()]

if N == 1:
    print(max(0,V[0]))
    exit()

ans = 0
for i in range(K): 
    for j in range(K-i+1):
        if j <= N-(K-i-j):
            ans_list = V[:j]+V[N-(K-i-j):]
            ans_list.sort()
            tmp = sum(ans_list)
            for k in range(min(len(ans_list),i)):
                if ans_list[k] < 0:
                    tmp -= ans_list[k]
            ans = max(ans,tmp)
        else:
            pass

print(max(ans,0))

Solution (Python):
from heapq import heappush, heappop, heapify, heapreplace

class Solution:
    def main(self):
        N, K = map(int, input().split())
        V = list(map(int, input().split()))
        res = 0
        for n_l in range(min(N, K)+1):
            for n_r in range(min(N-n_l, K-n_l)+1):
                array = sorted(V[:n_l] + V[N - n_r:])
                
                for n_d in range(0, min(K-n_l-n_r, len(array))):
                    if array[0] < 0:
                        array.pop(0)
                    else:
                        break
                res = max(res, sum(array))
                
        print(res)


if __name__ == '__main__':
    Solution().main()

Solution (Python):

import sys
import heapq
from collections.abc import Iterable
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


def solve(N: int, K: int, V: "List[int]"):

    lq = []
    acc_l = 0
    acc_ml = []
    ret = 0
    for li in range(min(N+1, K + 1)):
        if 0 < li:
            acc_l += V[li - 1]
            if V[li - 1] < 0:
                acc_ml.append(V[li - 1])

        if ret < acc_l:
            ret = acc_l
        acc_r = 0
        ms = [v for v in acc_ml]
        ms.sort()
        for _ri in range(min(N+1, K + 1) - li):
            if 0 < _ri:
                ri = N - _ri
                acc_r += V[ri]
                if V[ri] < 0:
                    ms.append(V[ri])
                    ms.sort()
            ci = min(len(ms), K - li - _ri)
            acc_c = sum(ms[:ci])
            acc = acc_l + acc_r - acc_c
            if ret < acc:
                ret = acc
    return ret


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    K = int(next(tokens))  
    V = [ int(next(tokens)) for _ in range(N) ]  
    result = solve(N, K, V)
    if isinstance(result, Iterable) and not isinstance(result, str):
        result = '\n'.join([str(v) for v in result])
    print(result)

if __name__ == '__main__':
    main()

Solution (Python):
from copy import deepcopy
N, K = map(int, input().split())
V = list(map(int, input().split()))
Lsum = [0]
Rsum = [0]
Lnegs = [[]]
Rnegs = [[]]
for i in range(N):
    Lsum.append(Lsum[i]+V[i])
    Rsum.append(Rsum[i]+V[N-i-1])
    Lnegs_cp = deepcopy(Lnegs[i])
    if V[i] < 0:
        Lnegs_cp.append(V[i])
        
    Lnegs.append(Lnegs_cp)
    Rnegs_cp = deepcopy(Rnegs[i])
    if V[N-i-1] < 0:
        Rnegs_cp.append(V[N-i-1])
        
    Rnegs.append(Rnegs_cp)

ans = 0

for dig in range(min(N+1, K+1)):
    n_del = K - dig
    for ldig in range(dig+1):
        rdig = dig - ldig
        LRsum = Lsum[ldig] + Rsum[rdig]
        negs = []
        for neg in Lnegs[ldig]:
            negs.append(neg)
        for neg in Rnegs[rdig]:
            negs.append(neg)
        negs = sorted(negs)
        for i in range(min(n_del, len(negs))):
            LRsum -= negs[i]
        ans = max(ans, LRsum)

print(ans)

Solution (Python):



N, K = map(int, input().rstrip().split(' '))
X = [0] + list(map(int, input().rstrip().split(' ')))

sorted_left_X = []
sorted_right_X = []
sorted_remove_X = []
for i in range(N+1):
    sorted_left_X.append(sorted([x for x in X[:i] if x < 0]))
    sorted_right_X.append(sorted([x for x in X[::-1][:i] if x < 0]))
    
    sorted_remove_X.append(sorted([x for x in X[:i] if x < 0] + [x for x in X[::-1][:i] if x < 0]))

cum_X = []
cum = 0
for x in X:
    cum += x
    cum_X.append(cum)

if K > N:
    temp = sorted([x for x in X if x < 0])
    print(cum_X[-1] - sum(temp[:min(len(temp), K)]))
else:
    max_count = 0
    for k in range(1,K+1):
        for i in range(k+1):
            temp = sorted(sorted_left_X[i] + sorted_right_X[k-i])
            temp2 = sum(temp[:min(len(temp), K-k)])
            max_count = max(cum_X[i] - cum_X[0] + cum_X[-1] - cum_X[i+N-k] - temp2, max_count)

    print(max_count)

Solution (Python):
n, k = map(int, input().split())
v = list(map(int, input().split()))
maxvalue = 0
for l in range(n+1):
    for r in range(l, n+1):
        ava = sorted(v[:l] + v[r:])
        takeop = len(ava)
        if takeop <= k:
            value = sum(ava)
            for i in range(min(takeop, k - takeop)):
                if ava[i] >= 0:
                    break
                else:
                    value -= ava[i]
            maxvalue = max(maxvalue, value)
print(maxvalue)

Solution (Python):
import sys

from fractions import gcd





from itertools import accumulate






from collections import deque






input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def li(): return list(input().rstrip())



def iterate_tokens():
    for line in sys.stdin:
        for word in line.split():
            yield word


if __name__ == '__main__':

    tokens = iterate_tokens()
    N = int(next(tokens))  
    K = int(next(tokens))  
    V = [int(next(tokens)) for _ in range(N)]  

    

    left = []
    right = []
    left.append(0)
    right.append(0)
    left.append(max(V[0], 0))
    right.append(max(V[-1], 0))
    for i in range(2, 2*N+1):
        tmp_max = 0
        for j in range(-(-i // 2), i+1):
            tmp_V = V[:j]
            tmp_V.sort()
            
            if tmp_max < sum(tmp_V[i - 2 * j:]):
                tmp_max = sum(tmp_V[i - 2 * j:])
        
        left.append(tmp_max)

    for i in range(2, 2*N+1):
        tmp_max = 0
        for j in range(-(-i // 2), i+1):
            tmp_V = V[-j:]
            tmp_V.sort()
            if tmp_max < sum(tmp_V[i - 2 * j:]):
                tmp_max = sum(tmp_V[i - 2 * j:])
        
        right.append(tmp_max)
    ans = []
    
    
    sV = sum([i for i in V if i >= 0])
    
    for j in range(0, min(2*N, K) + 1):
        tmp_ans = -10**9
        for i in range(j+1):
            if tmp_ans < left[i] + right[j - i]:
                tmp_ans = left[i] + right[j - i]
        ans.append(tmp_ans)
    print(min(max(ans), sV))

Solution (Python):

import sys


def solve(N: int, K: int, V: "List[int]"):
    l = [0] * (K + 1)
    r = [0] * (K + 1)
    for i in range(1, K + 1):
        v = V[:i]
        v.sort(reverse=True)
        for j in range(0, i):
            if i + j <= K:
                l[i + j] = max(l[i + j], sum(v[:i - j]))

    V.reverse()
    for i in range(1, K + 1):
        v = V[:i]
        v.sort(reverse=True)
        for j in range(0, i):
            if i + j <= K:
                r[i + j] = max(r[i + j], sum(v[:i - j]))

    for i in range(1, K + 1):
        l[i] = max(l[i], l[i - 1])
        r[i] = max(r[i], r[i - 1])

    
    
    ret = 0
    for i in range(0, len(l)):
        ret = max(ret, l[i] + r[K - i])
        

    tmp = 0
    for v in V:
        if v > 0:
            tmp += v
    ret = min(ret, tmp)
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    K = int(next(tokens))  
    V = [ int(next(tokens)) for _ in range(N) ]  
    solve(N, K, V)

if __name__ == '__main__':
    main()

Solution (Python):
import heapq

n, k = map(int, input().split())
vs = list(map(int, input().split()))

max_v = -float('inf')
for a in range(min(k, n)+1):
    total = 0
    minus = []
    for i in range(a):
        total += vs[i]
        if vs[i] < 0:
            heapq.heappush(minus, vs[i])
    max_v = max(max_v, total)
    for b in range(min(k-a, n-a)+1):
        c = k - a - b
        if c < 0:
            break
        h = minus[:]
        t = total
        for i in range(b):
            t += vs[n-1-i]
            if vs[n-1-i] < 0:
                heapq.heappush(h, vs[n-1-i])
        for i in range(c):
            if h:
                v = heapq.heappop(h)
                t -= v
            else:
                break
        max_v = max(max_v, t)

print(max_v)

Solution (Python):
from heapq import*
n,k=map(int,input().split())
*v,=map(int,input().split())
motimono=[]
ans=[]
if k>=n:
    k-=n
    heapify(v)
    ans.append(sum(v))
    for i in range(k):
        if len(v)>0:
            heappop(v)
        ans.append(sum(v))
    print(max(ans))
else:
    v*=2
    for j in range(1,k+1):
        for i in range(n-j,n+1):
            motimono=v[i:i+j]
            ans.append(sum(motimono))
            heapify(motimono)
            for i in range(k-j):
                if len(motimono)>0:
                    heappop(motimono)
                ans.append(sum(motimono))
    print(max(ans))