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: Accepted

Solution code:
import sys
import bisect
N, K = map(int, sys.stdin.readline().split())
V = list(map(int, sys.stdin.readline().split()))

# 累積和を計算しとく
sum_list = [V[0]]
for i in range(1, N):
    add = V[i] + sum_list[-1]
    sum_list.append(add)

ans = 0

max_take = min(N, K)

for A in range(max_take + 1):
    for B in range(max_take - A + 1):
        if A > 0 and B > 0:
            list = V[:A] + V[N - B:]
            total_sum = sum(list) #sum_list[A - 1] + (sum_list[N - 1] - sum_list[N - 1 - B])
            list.sort()
            n = bisect.bisect_left(list, 0)
            if n <= K - (A + B):
                total_sum -= sum(list[:n])
            else:
                total_sum -= sum(list[:K - (A + B)])
        elif A == 0 and B > 0:
            list = V[N - B:]
            total_sum = sum(list) #sum_list[N - 1] - sum_list[N - 1 - B]
            list.sort()
            n = bisect.bisect_left(list, 0)
            if n <= K - (A + B):
                total_sum -= sum(list[:n])
            else:
                total_sum -= sum(list[:K - (A + B)])
        elif A > 0 and B == 0:
            list = V[:A]
            total_sum = sum(list) #sum_list[A - 1]
            list.sort()
            n = bisect.bisect_left(list, 0)
            if n <= K - (A + B):
                total_sum -= sum(list[:n])
            else:
                total_sum -= sum(list[:K - (A + B)])
        else:
            continue
        
        #print("A = " + str(A) + " B = " + str(B))
        #print(total_sum)
        if total_sum > ans:
            ans = total_sum
            
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N,K = map(int,input().split())
V = list(map(int,input().split()))
D = []
ans = 0
for i in range(K+1):
    for j in range(K-i+1):
        if i + j > N:
            break
        D.append(V[:i]+V[N-j:])
for d in D:
    for x in range(K-len(d)):
        if d==[]:
            break
        elif min(d)<0:
            d.pop(d.index(min(d)))

        elif min(d)>0:
            break        
    if d!=[]:
        s = sum(d)
        if s>0 and s>ans:
            ans = s
print(ans)

Submission status: Accepted

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

D = []
ans = []

for i in range(K+1):
    for j in range(K-i+1):
        if i + j > N:
            break
        D.append(V[:i]+V[N-j:])

for d in D:
    for x in range(K-len(d)):
        if d==[]:
            break
        elif min(d)<0:
            d.pop(d.index(min(d)))

        elif min(d)>0:
            break
        
    if d==[]:
        ans.append(0)
    elif sum(d)>0:
        ans.append(sum(d))

if max(ans)>0:
    print(max(ans))

else:
    print(0)

Submission status: Accepted

Solution code:
import copy

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

result = 0
# i個取る
for i in range(min(N,K)+1):
    #print('i:',i)
    for sp in range(i+1): # 左右の分け方
        #print('right',sp)
        #print('left',i-sp)
        tmp = []
        V_tmp = copy.copy(V)
        #print('元々：',V_tmp)
        tmp.extend(V_tmp[:sp]) # 左端追加
        #print('left',V_tmp[:sp])
        tmp.extend(V_tmp[N-(i-sp):]) #右端追加
        #print('right',V_tmp[N-(i-sp):])
        #print(tmp)
        tmp = sorted(tmp)
        value = sum(tmp)
        # ret個戻す
        for ret in range(0, min(K-i,i)): #残り操作回数か取った石の個数iの小さい方
            if ret < i:
                # マイナスの価値は戻す
                if tmp[ret] < 0:
                    value -= tmp[ret]
                    #print('捨てた宝石：',tmp[ret])
            else:
                break
        result = max(result,value)
            #print()

print(result)

Submission status: Accepted

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

max_ = 0
for a in range(K + 1):
    for b in range(K - a + 1):
        if a + b > N:
            continue

        jwl = V[:a]
        jwl += V[N - b:]
        rmv = K - (a + b)
        jwl.sort()

        sum_ = sum(jwl)
        for i in range(min(rmv, len(jwl))):
            if jwl[i] >= 0:
                break

            sum_ -= jwl[i]

        max_ = max(max_, sum_)


print(max_)

Submission status: Accepted

Solution code:
def main():
    n,k = map(int,input().split())
    v = list(map(int,input().split()))
    m = 0
    for k_ in range(k+1):
        v_c = v
        if k_>n:
            v_ = v_c
            v_c = []
            s = k-n
        else:
            v_ = v_c[0:k_]
            v_c = v_c[k_:]
            s = k-k_
        for i in range(s+1):
            if i>len(v_c):
                v__ =v_+ v_c
                s_ = s-len(v_c)
            else:
                v__ = v_+ v_c[len(v_c)-i:]
                s_ = s-i
            while s_>0 and len(v__)>0 and min(v__)<0:
                v__.pop(v__.index(min(v__)))
                s_ = s_-1
            if sum(v__)>m:
                m = sum(v__)
    print(m)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import heapq
n, k = map(int, input().split())
r = min(n, k)
v = list(map(int, input().split()))
ans = 0
for i in range(1, r+1):
  for j in range(i+1):
    a = j
    b = i-j
    v_temp = v[:a]
    v_temp.extend(v[n-b:])
    heapq.heapify(v_temp)
    for l in range(k-i):
      get = heapq.heappop(v_temp)
      if get>=0:
        heapq.heappush(v_temp, get)
        break
      if not v_temp:
        break
    v_temp.append(0)
    ans = max(ans, sum(v_temp))
print(ans)

Submission status: Accepted

Solution code:
import heapq

res=0
n,k=map(int,input().split())
v=list(map(int,input().split()))
r=min(n,k)
for a in range(r+1):#操作Aの回数
    for b in range(r-a+1):#Bの回数
        d=v[:a]
        d.extend(v[n-b:])
        s=sum(d)
        heapq.heapify(d)

        l=k-(a+b) #捨てる回数print(d)
        for _ in range(l):
            if not d:
              break
            t=heapq.heappop(d)
            if t<0:
               s-=t
            else:
                break
        if s>res:
            res=s
print(res)

Submission status: Accepted

Solution code:
import heapq

n,k=map(int,input().split())
v=list(map(int,input().split()))
s=-10**7-1

if n>k:
    for l in range(k//2+1):
        for i in range(k+1-l):
            d=v[:i]
            d.extend(v[(n-k+l+i):])
            heap=heapq.heapify(d)
            res=sum(d)
            for j in range(l):
                t=heapq.heappop(d)
                if t<0:
                    res-=t
                else:
                    break
            if s<res:
                s=res
else:
    for l in range(n+1):
        for i in range(n-l+1):
            d=v[:i]
            d.extend(v[(l+i):])
            heap=heapq.heapify(d)
            res=sum(d)
            for j in range(k-(n-l)):
                if not d:
                    break
                t=heapq.heappop(d)
                if t<0:
                    res-=t
                else:
                    break
            if s<res:
                s=res

        
if s<0:
    print(0)
else:
    print(s)

Submission status: Accepted

Solution code:
from collections import deque
from heapq import heappush, heappop
from copy import deepcopy

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

dq = deque(v)

ans = 0
for ab in range(k + 1):
    cd = k - ab
    for a in range(ab + 1):
        hp = []
        cp = deepcopy(dq)

        b = ab - a
        for _ in range(a):
            if cp:
                val = cp.popleft()
                heappush(hp, val)
        for _ in range(b):
            if cp:
                val = cp.pop()
                heappush(hp, val)

        for _ in range(cd):
            if not hp or hp[0] >= 0:
                break
            heappop(hp)

        ans = max(ans, sum(hp))

print(ans)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
V=list(map(int,input().split()))
if N<=K:
  W=sorted(V)
  h=sum(V)
  for i in range(K-N):
    if W[i]<0:
      h-=W[i]
    else:
      break
else:
  ans=[]
  for i in range(1,K+1):
    for j in range(i+1):
      l=V[0:i-j]+V[N-j:N]
      l.sort()
      H=sum(l)
      for k in range(min(i,K-i)):
        if l[k]<0:
          H-=l[k]
        else:
          break
      ans.append(H)
  h=max(ans)
print(h)

Submission status: Accepted

Solution code:
n, k = [int(x) for x in input().split()]
v_list = [int(x) for x in input().split()]

stop = min(n, k)

ans = 0
for a in range(stop + 1):
    a_list = v_list[:a]
    for b in range(stop + 1 - a):
        b_list = v_list[n-b:]
    
        temp_list = a_list + b_list
        temp_list.sort(reverse=True)

        for _ in range(k - a - b):
            if len(temp_list) == 0 or temp_list[-1] >= 0:
                break
            temp_list.pop()

        temp = sum(temp_list)
        if ans < temp:
            ans = temp
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import permutations,combinations
from collections import defaultdict,Counter
from bisect import bisect_left,bisect_right
# from math import gcd,ceil,floor,factorial
# from fractions import gcd
from functools import reduce
from pprint import pprint

def myinput():
    return map(int,input().split())

def mylistinput(n):
    return [ list(myinput()) for _ in range(n) ]

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col,reverse_flag):
    data.sort(key=lambda x:x[col],reverse=reverse_flag)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

def myoutput(ls,space=True):
    if space:
        if len(ls)==0:
            print(" ")
        elif type(ls[0])==str:
            print(" ".join(ls))
        elif type(ls[0])==int:
            print(" ".join(map(str,ls)))
        else:
            print("Output Error")
    else:
        if len(ls)==0:
            print("")
        elif type(ls[0])==str:
            print("".join(ls))
        elif type(ls[0])==int:
            print("".join(map(str,ls)))
        else:
            print("Output Error")

# ----- heapq ここから-----
import heapq
class Reverse:
    def __init__(self, val):
        self.val = val
        
    def __lt__(self, other):
        return self.val > other.val
        
    def __repr__(self):
        return repr(self.val)
    
class Heapq:
    def __init__(self, arr, desc = False):
        if desc:
            for i in range(len(arr)):
                arr[i] = Reverse(arr[i])
        self.desc = desc
        self.hq = arr
        heapq.heapify(self.hq)
 
    def pop(self):
        if self.desc: return heapq.heappop(self.hq).val
        else: return heapq.heappop(self.hq)
 
    def push(self, a):
        if self.desc: heapq.heappush(self.hq, Reverse(a))
        else: heapq.heappush(self.hq, a)
 
    def top(self):
        if self.desc: self.hq[0].val
        else: return self.hq[0]
# ----- heapq ここまで-----

n,k = myinput()
v = list(myinput())
vr = v[::-1]

ls = [-1,-1]
ans = -float("inf")
for a in range(k+1):
    for b in range(min(k-a+1,n-a+1)):
        have = []
        have.extend( v[:a] )
        have.extend( vr[:b] )
        p = [ i for i in have if i>=0 ]
        m = [ i for i in have if i<0 ]
        m.sort()
        r = k - a - b
        m = m[r:]
        ans_tmp = sum(p)+sum(m)
        if ans<ans_tmp:
            ls[0] = a
            ls[1] = b
        ans = max(ans,ans_tmp)
# print(ls)
print(ans)

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections
INF = 10**9
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
_LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())
N,K = LI()
dq = LI()

ans = -INF
for r in range(N+1):
    if K < N - r: continue

    ret = 0
    for i in range(N-r+1):
        q = dq[:i] + dq[i+r:]
        ret = sum(q)
        q.sort()
        for j in range(K - (N-r)):
            if j >= len(q)-1 : break
            if q[j] < 0:
                ret -= q[j]
            else:
                break
        ans = max(ans,ret)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
import heapq
def f(d,n):
    a = list(d)
    heapq.heapify(a)
    while n > 0 and len(a) > 0:
        tmp = heapq.heappop(a)
        if tmp >= 0:
            heapq.heappush(a,tmp)
            break
        n -= 1
    return sum(a)
#マイナスを取り除いて和を求める関数をあらかじめ作っておく
#優先度付きキューを使うと楽
N, K = map(int, input().split())
V = list(map(int, input().split()))
ans = 0
for i in range(1,min(N,K)+1):
    d = deque()
    for k in range(i):
        d.append(V[k])
    ans = max(ans,f(d,K-i))
    for k in range(i):
        d.pop()
        d.appendleft(V[N-1-k])
        ans = max(ans,f(d,K-i))
print(ans)
#解説中のa+b,bについてループで全探索している

Submission status: Accepted

Solution code:
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

IN=lambda : map(int, input().split())
LIN=lambda : list(IN())
mod=1000000007

#+++++

def main():
	#a = int(input())
	n, k = IN()
	dq = LIN()
	rdq = dq[::-1]
	#s = input()
	max_v=0
	for left_get in range(k+1):
		for right_get in range(max(k-left_get+1,1)):
			if left_get+right_get>n:
				continue
			elif left_get==0 and right_get==0:
				continue
			nokori=k-left_get-right_get
			l=dq[:left_get]
			r=rdq[:right_get]
			#print(l, r)
			dd=(l+r)
			dd.sort(reverse=True)
			for _ in range(nokori):
				if dd[-1]>= 0:
					break
				dd.pop()
				if len(dd)==0:
					break
			r=sum(dd)
			max_v=max(max_v, r)
	print(max_v)
		
		
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

Solution code:
from collections import deque
import heapq
def f(d,n):
    a = list(d)
    heapq.heapify(a)
    while n > 0 and len(a) > 0:
        tmp = heapq.heappop(a)
        if tmp >= 0:
            heapq.heappush(a,tmp)
            break
        n -= 1
    return sum(a)
N, K = map(int, input().split())
V = list(map(int, input().split()))
ans = 0
for i in range(1,min(N,K)+1):
    d = deque()
    for k in range(i):
        d.append(V[k])
    ans = max(ans,f(d,K-i))
    for k in range(i):
        d.pop()
        d.appendleft(V[N-1-k])
        ans = max(ans,f(d,K-i))
print(ans)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
V=list(map(int,input().split()))
ans=0
for a in range(min(N,K)+1):
    for b in range(min(N,K)+1-a):
        v=[]
        value=sum(V[:a])
        v.extend(V[:a])
        if b!=0:
            value=value+sum(V[-b:])
            v.extend(V[-b:])
        v.sort()
        for i in range(min(a+b,K-a-b)):
            if v[i]<0:
                value=value-v[i]
            else:
                break
        ans=max(ans,value)
print(ans)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
V=list(map(int,input().split()))
ans=0
if 2*N<=K:
    for i in V:
        if i>=0:
            ans+=i
else:
    for a in range(min(N,K)+1):
        for b in range(min(N,K)+1-a):
            v=[]
            value=sum(V[:a])
            v.extend(V[:a])
            if b!=0:
                value=value+sum(V[-b:])
                v.extend(V[-b:])
            v.sort()
            for i in range(min(a+b,min(N,K)-a-b)):
                if v[i]<0:
                    value=value-v[i]
                else:
                    break
            ans=max(ans,value)
print(ans)

Submission status: Accepted

Solution code:
# D - equeue

import heapq

n, k = map(int, input().split())
v = list(int(x) for x in input().split())

ans = 0
for l in range(k+1):
    for r in range(k+1-l):
        if l+r>n:
            continue
        tmp = 0
        s = []
        for i in range(l):
            tmp += v[i]
            heapq.heappush(s, v[i])

        for i in range(n-r, n):
            tmp += v[i]
            heapq.heappush(s, v[i])
            
        for i in range(k-l-r):
            if len(s)==0:
                break
            if s[0]>0:
                break
            tmp -= heapq.heappop(s)
        
        ans = max(ans, tmp)

print(ans)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    N, K = map(int, readline().split())
    V = list(map(int, readline().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)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
V = list(map(int, input().split()))
ans = 0
for i in range(K+1):
  for j in range(N, max(N-1-(K-i), i-1), -1):
    bag = []
    bag += V[:i] + V[j:]
    bag.sort()
    idx = 0
    if len(bag) == 0:
      continue
    if len(bag) == 1:
      ans = max(ans, sum(bag))
      continue
    if len(bag) == K:
      ans = max(ans, sum(bag))
      continue
    tmp = 0
    for k in range(min(K-len(bag), len(bag))):
      if bag[k] < 0:
        tmp -= bag[k]
    ans = max(ans, sum(bag)+tmp)
print(ans)

Submission status: Accepted

Solution code:
#Satoooh
'''
左からL個、右からR個、取り出す。
取り出す回数は操作回数上限のK回なので、最大K個取り出せる。
操作はK回まで行えるので、操作回数がKより小さくてもOK。
求めるのは、価値の最大値なので、マイナスの宝石は、筒に戻す。
筒に戻せる上限は、下記１と２の小さい値min
１．操作回数制限：K-L-R、操作回数の上限から、LとRを取り出した回数を引く
２．宝石個数制限：手持ちは、L+R個なので、これ以上は戻せない
'''
N, K = map(int, input().split())
*V, = map(int, input().split())#タプルとして入力、仮に1個でもOK
ans = 0#格納されている宝石が負ばかりなら、何もしない

for l in range(K + 1):#左から最大K個取り出す
	for r in range(K - l + 1):
    #右から取り出すのはK-L個、左からL個取り出しているので
		inHand = []#手持ちを格納する配列
		if l + r > N:  # Nを超えてしまうありえない場合を処理
			break#ありえないケースはブレイク
		# inHandに左からl個、右からr個の要素を追加
		inHand = V[: l]
		inHand.extend(V[N - r:])
		tmp = sum(inHand)  
        # 現時点でのinHandの和をtmpとして負の要素をtmpから引いていく
		# inHand中の負の要素を消せるだけ消す
		inHand.sort()
		for i in range(min(K - l - r, l + r)):
			if inHand[i] >= 0:#負の要素だけ消す
				break
			tmp -= inHand[i]#負の要素は手持ちしないことにする
		ans = max(ans, tmp)#求めるのは手持ちの価値の最大値

print(ans)

Submission status: Accepted

Solution code:
#Satoooh
N, K = map(int, input().split())
*V, = map(int, input().split())#タプルとして入力
ans = 0#格納されている宝石が負ばかりなら、何もしない

for l in range(K + 1):#左から最大K個取り出す
	for r in range(K - l + 1):
    #右から取り出すのはK-L個、左からL個取り出しているので
		inHand = []#手持ちを格納する配列
		if l + r > N:  # Nを超えてしまうありえない場合を処理
			break#ありえないケースはブレイク
		# inHandに左からl個、右からr個の要素を追加
		inHand = V[: l]
		inHand.extend(V[N - r:])
		tmp = sum(inHand)  # 現時点でのinHandの和をtmpとして負の要素をtmpから引いていく
		# inHand中の負の要素を消せるだけ消す
		inHand.sort()
		for i in range(min(K - l - r, l + r)):
			if inHand[i] >= 0:#負の要素だけ消す
				break
			tmp -= inHand[i]#負の要素は手持ちしないことにする
		ans = max(ans, tmp)#求めるのは手持ちの価値の最大値

print(ans)

Submission status: Accepted

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

for i in range(N+1):
    for j in range(N+1):
        if i+j>N:
            continue
        
        l = []
        
        for k in range(i):
            l.append(V[k])
        
        for k in range(j):
            l.append(V[N-1-k])
        
        if len(l)>K:
            continue
        
        l.sort()
        cnt = K-len(l)
        now = 0
        
        while cnt>0 and now<len(l) and l[now]<0:
            cnt -= 1
            now += 1
        
        ans = max(ans, sum(l[now:]))

print(ans)

Submission status: Accepted

Solution code:
import time
startTimeProblem=time.time()

import fileinput, sys, itertools, functools
from math import *
from bisect import *
from heapq import *
from collections import *

def lcm(a, b):  
    return (a*b)/gcd(a, b)

class InputHelper:
    def __init__(self):
        self.myinput = fileinput.input()

    def isLocal(self):
        return not fileinput.isstdin()

    def int(self):
        return int(self.myinput.readline().rstrip())

    def ints(self):
        return [int(_) for _ in self.myinput.readline().rstrip().split()]

    def str(self):
        return self.myinput.readline().rstrip()

    def strs(self):
        return [_ for _ in self.myinput.readline().rstrip().split()]

class OutputHelper:
    def int(self, a):
        print(a)    

    def ints(self, a):  
        print(" ".join([str(_) for _ in a]))
    
    def intsNL(self, a):
        for _ in a:
            print(_)
    
    def str(self, s):
        print(s)

    def strs(self, s):
        print(" ".join([_ for _ in s]))

    def strsNL(self, s):
        for st in s:
            print(st)

class ListNode:
    def __init__(self, val):
        self.val = val
        self.next = None
        self.prev = None

In = InputHelper()
Out = OutputHelper()

######################################

N, K = In.ints()
V = In.ints()

class Solution():
    def __init__(self, K, V):
        self.ans = 0
        self.k = K
        self.posSum = 0
        self.negPreSum = [0]
        self.V = V

    @functools.lru_cache(None)
    def rec(self, fromIncl, toIncl):
        self.k -= 1
        canCallNext = self.k>0 and fromIncl!=toIncl

        #taketh left part
        leftVal = self.V[fromIncl]
        if leftVal>=0:
            self.posSum+=leftVal
        else:
            bipos = bisect_left(self.negPreSum, -leftVal)
            self.negPreSum.insert(bipos, -leftVal)

        negIdx = max(len(self.negPreSum)-1-self.k, 0)
        self.ans = max(self.ans, self.posSum-sum(self.negPreSum[0:negIdx+1]))

        if canCallNext:
            self.rec(fromIncl+1, toIncl)
        
        if leftVal>=0:
            self.posSum-=leftVal
        else:
            self.negPreSum.pop(bipos)
        
        #taketh right
        rightVal = self.V[toIncl]
        if rightVal>=0:
            self.posSum+=rightVal
        else:
            bipos = bisect_left(self.negPreSum, -rightVal)
            self.negPreSum.insert(bipos, -rightVal)

        negIdx = max(len(self.negPreSum)-1-self.k, 0)
        self.ans = max(self.ans, self.posSum-sum(self.negPreSum[0:negIdx+1]))

        if canCallNext:
            self.rec(fromIncl, toIncl-1)

        if rightVal>=0:
            self.posSum-=rightVal
        else:
            self.negPreSum.pop(bipos)

        self.k += 1


sol = Solution(K, V)
sol.rec(0, N-1)
Out.int(sol.ans)

######################################

if len(sys.argv)>2 and sys.argv[2]=="TIMEIT":
    fin = (time.time()-startTimeProblem)*1000
    print("{:.2f}".format(fin) + "ms")

Submission status: Accepted

Solution code:
# solution

def solve(string):
    n, k, *v = map(int, string.split())
    ans = 0
    for i in range(k + 1):
        for j in range(k - i + 1):
            base = sorted(v[:i] + v[max(n - k + i + j, i):])
            ans = max(ans, sum([b for l, b in enumerate(base) if b >= 0 or j <= l]))
    return str(ans)


if __name__ == '__main__':
    print(solve('\n'.join([input(), input()])))

Submission status: Accepted

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

ans = 0
for x in range(N+1):
    for y in range(N+1):
        if x+y > N or x+y > K:
            break
        rest = min(K-x-y, x+y)
        As = Vs[:x] + Vs[N-y:]
        As.sort()
        score = sum(As)
        for i in range(rest):
            if As[i] < 0:
                score -= As[i]
        ans = max(ans, score)

print(ans)

Submission status: Accepted

Solution code:
def solve():
    N, K = map(int, input().split())
    V = list(map(int, input().split()))
    V *= 2
    ans = 0
    for i in range(N+1):
        for j in range(N-1,2*N):
            num = j-i+1
            if num>K or num>N or num == 0:
                continue
            lis = V[i:j+1]
            lis.sort()
            margin = K-num
            m = sum(lis)
            k = 0
            while k < margin and k < num and lis[k]<0 :
                m -= lis[k]
                k += 1
            ans = max(ans,m)
    return ans
print(solve())

Submission status: Accepted

Solution code:
#template
def inputlist(): return [int(k) for k in input().split()]
#template
N,K = inputlist()
V = inputlist()
n = min(N,K)
ans = 0
from collections import deque
for a in range(n+1):
    for b in range(n+1):
        li = []
        if a+b > n:
            continue
        c = K-(a+b)
        que = deque(V)
        for i in range(a):
            k = que.popleft()
            li.append(k)
        for j in range(b):
            s = que.pop()
            li.append(s)
        li.sort()
        index = 0
        for i in range(len(li)):
            if li[i] < 0:
                index +=1
        na = min(index,c)
        suma = sum(li[na:])
        ans = max(ans,suma)

print(ans)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
V = list(map(int,input().split()))
Vi = V[::-1]
t = min(n,k)
ans = 0
for i in range(1,t+1):#選ぶ個数
    for a in range(0,i+1):
        b = i-a
        houseki = V[0:a] + Vi[0:b]
        houseki.sort()
        tmp=sum(houseki)
        for idx,val in enumerate(houseki):
            if idx==k-i:break
            if val<0:tmp-=val
        ans = max(ans,tmp)
print(ans)

Submission status: Accepted

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

#take i and remove K-i
answer=0
for i in range(K+1):
  if i>N: break
  
  take_cand=[]
  if i==N:
    take_cand=[vlist]
  else:
    for j1 in range(i+1):
      j2=i-j1
      take_cand.append(vlist[:j1]+vlist[N-j2:])
  
  #print(i,take_cand)
  for take in take_cand:
    take.sort(reverse=True)
    for _ in range(K-i):
      if len(take)>0 and take[-1]<0:
        take.pop()
    
    answer=max(sum(take),answer)

print(answer)

Submission status: Accepted

Solution code:
import copy,heapq

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

ans=0
left=copy.copy(V)
for i in range(1,N):
    left[i]+=left[i-1]
right=copy.copy(V)
for i in range(1,N):
    right[-i-1]+=right[-i]
for i in range(0,N+1):
    for j in range(0,N-i+1):
        dispose=K-i-j
        if 0>dispose:
            continue
        test=0
        q=[]
        if i>0:
            test+=left[i-1]
            q+=V[:i]
        if j>0:
            test+=right[-j]
            q+=V[N-j:N]

        heapq.heapify(q)
        while dispose>0 and q:
            x=heapq.heappop(q)
            if 0>x:
                test-=x
                dispose-=1
            else:
                break
        ans=max(ans,test)

print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
l = list(map(int, input().split()))
ans = 0
for i in range(1, min(n, k) + 1):
  for j in range(i + 1):
    l_tmp = l[:j] + l[n - i + j:]
    l_tmp.sort()
    for m in range(min(k - i, i)):
      if l_tmp[m] < 0:
        l_tmp[m] = 0
    ans = max(ans, sum(l_tmp))
print(ans)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
v = list(map(int,input().split()))
ma = 0
kaisu = min(n,k)
for a in range(kaisu+1):
    for b in range(kaisu-a+1):
        push = k-(a+b)
        li = v[:a]+v[n-b:]
        li.sort(reverse=True)
        for c in range(push):
            if li:
                if li[-1] < 0:
                    li.pop()
        ma = max(ma,sum(li))
print(ma)

Submission status: Accepted

Solution code:
def main():
    n, k = [int(e) for e in input().split()]
    V = [int(e) for e in input().split()]

    ans = 0
    vc = min(n, k)
    for vci in range(1, vc + 1):
        for vcii in range(vci + 1):
            Hand = []
            for li in range(vcii):
                Hand.append(V[li])

            for ri in range(vci - vcii):
                Hand.append(V[-ri - 1])

            Hand.sort()
            for i in range(min(k - vci, len(Hand))):
                if Hand[i] < 0:
                    Hand[i] = 0

            ans = max(sum(Hand), ans)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
V = list(map(int,input().split()))
ans = 0
for i in range(n+1):
    for j in range(n+1-i):
        removed = V[:i] + V[n-j:]
        if len(removed) > k:break
        removed.sort()
        get = sum(removed)
        for l in range(min(k-len(removed),len(removed))):
            if removed[l] >= 0:break
            get -= removed[l]
        ans = max(ans,get)
print(ans)