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 heapq as hq

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

ans=0
for i in range(1,min(N,K)+1): #取り出す個数
    for j in range(i+1):
        A=[]
        hq.heapify(A) #左から取り出す個数
        for k in range(j):
            hq.heappush(A,V[k])
        for k in range(i-j):
            hq.heappush(A,V[N-k-1])
        p=min(i,K-i) #しまえる個数
        while p>0:
            if A[0]<0:
                hq.heappop(A)
                p-=1
            else:
                break
        ans=max(sum(A),ans)
print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
v=list(map(int,input().split()))
ans=-10**18
for l in range(min(n,k)+1):
  for r in range(min(n,k)+1):
    if l+r>n or l+r>k:
      continue
    trg=v[:l]+v[n-r:]
    trg.sort(reverse=True)
    for i in range(k-l-r+1):
      ans=max(ans,sum(trg[:len(trg)-i]))
print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate
    #from itertools import product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    N,K = map(int, input().split())
    V_l = list(map(int, input().split()))
    V_r = list(reversed(V_l))
    res = 0
    for i in range(K+1):
        if i<=N:
            for l in range(i+1):
                n = []
                r = i - l
                a = V_l[:l] + V_r[:r]
                for j in a:
                    if j<0:
                        n.append(j)
                n.sort()
                temp = sum(a)-sum(n[:K-i])
                res = max(res, temp)

    print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#abc128d
n,k=map(int,raw_input().split())
v=map(int,raw_input().split())
res=[]
for i in range(n+1):
 for j in range(min(n-i,k-i)+1):
  p=v[:i]+v[n-j:]
  p.sort()
  for x in range(k-i-j+1):
   res.append(sum(p[x:]))
print max(res)

Submission status: Accepted

Solution code:
# coding: utf-8
import copy

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

ans = -10**20
for l in range(n+1):
  for r in range(n+1-l):
    able = True
    d = k - ( l + r )
    if d < 0:
      able = False
      break
    t = v[0:l] + rev[0:r]
    m = sum(t)
    t.sort()
    d = min(d,l+r)
    for i in range(d):
      if 0 > t[i]:
        m -= t[i]
      else:
        break
    ans = max(ans,m)

print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
import copy
import numpy as np

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

lcs = [0]+np.cumsum(v)
rcs = [0]+np.cumsum(rev)
# print(lcs,rcs)

ans = -10**20
for l in range(n+1):
  for r in range(n+1-l):
    able = True
    d = k - ( l + r )
    if d < 0:
      able = False
      break
    # m = lcs[l] + rcs[r]
    t = v[0:l] + rev[0:r]
    m = sum(t)
    # print(t,l,r,m)
    t.sort()
    # print(t)
    d = min(d,l+r)
    for i in range(d):
      if 0 > t[i]:
        m -= t[i]
      else:
        break
    # print(m)
    ans = max(ans,m)

print(ans)

Submission status: Accepted

Solution code:
import sys
from bisect import *
from heapq import *
from collections import *
from itertools import *
from functools import *
from math import *

sys.setrecursionlimit(100000000)
input = lambda: sys.stdin.readline().rstrip()

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 or i + j > K:
            continue
        removed = sorted(V[:i] + V[N-j:])
        sm = sum(removed)
        for k in range(K - i - j):
            if k < len(removed) and removed[k] < 0:
                sm -= removed[k]
        ans = max(ans, sm)
print(ans)

Submission status: Accepted

Solution code:
import bisect
n, k = map(int, input().split())
V = list(map(int, input().split()))
max_dequeue = min(n, k)

max_value = 0
for dequeue_num in range(max_dequeue + 1):
  for left in range(dequeue_num + 1):
    right = dequeue_num - left
    #print("left", left, "right", right, "dn", dequeue_num)
    jewel_taken = sorted(V[:left] + V[n - right:])
    #print("jt", jewel_taken)
    pos_zero = bisect.bisect(jewel_taken, 0)
    ret_num = min(k - dequeue_num, pos_zero)
    #print(pos_zero, k - dequeue_num)
    #print(jewel_taken[ret_num:])
    #print()
    max_value = max(max_value, sum(jewel_taken[ret_num:]))
print(max_value)

Submission status: Accepted

Solution code:
import heapq
n, k = map(int, input().split())
v = list(map(int, input().split()))

result = []
for i in range(min(n, k)+1):
    for j in range(min(n, k)+1-i):
        x = v[:i]+v[n-j:]
        c = k - (i + j)
        x.sort()
        for t in range(min(len(x), c)):
            if x[0]<0:
                x.pop(0)
            else:
                break
        result.append(sum(x))
print(max(result))

Submission status: Accepted

Solution code:
from collections import deque
N, K = map(int, input().split())
V = list(map(int, input().split()))
R = min(N, K)
ans = 0
for A in range(R+1):
    for B in range(R+1):
        d = deque(V)
        if A + B > R:
            continue
        x = []
        for _ in range(A):
            if 0 < len(d):
                x.append(d.popleft())
        for _ in range(B):
            if 0 < len(d):
                x.append(d.pop())
        x.sort()
        drop = K - (A + B)
        for _ in range(drop):
            if 0 < len(x) and x[0] < 0:
                x.pop(0)
        ans = max(ans, sum(x))
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

n, k = [int(x) for x in input().split()]
v = [int(x) for x in input().split()]
v_rev = v[::-1]
ans = -float("inf")

for a in range(min(n, k) + 1):
    b_list = [i for i in range(min(n, k) - a + 1)]
    for b in b_list:
        c = k - (a + b)
        left = v[:a]
        right = v_rev[:b]
        minus_list = []
        for i in left:
            if i < 0:
                minus_list.append(i)
        for j in right:
            if j < 0:
                minus_list.append(j)
        minus_list.sort()
        res = sum(left) + sum(right) - sum(minus_list[:c])
        # print(a, b, c, res)
        # print(left, right, minus_list)
        ans = max(ans, res)
print(ans)

Submission status: Accepted

Solution code:
n, k, *V = map(int, open(0).read().split())
def calc(i, j, k):
    W = sorted(V[:i] + V[:-j-1:-1], reverse=True)
    for _ in range(k):
        if W[-1] < 0:
            W.pop()
    return sum(W)

ans = 0
r = min(n, k)+1
for i in range(r):
    for j in range(r-i):
        for k_ in range(min(i+j, k+1-i-j)):
            ans = max(ans, calc(i, j, k_))
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

inputs = open(0).readlines()
n, k = map(int, inputs[0].split())
V = deque(map(int, inputs[1].split()))
def calc(ii, jj, kk):
    W = []
    for i in range(ii):
        W.append(V[i])
    for j in range(jj):
        W.append(V[-j-1])
    W.sort(reverse=True)
    for _ in range(kk):
        if W[-1] < 0:
            W.pop()
    return sum(W)

ans = 0
for i in range(min(n, k)+1):
    for j in range(min(n, k)+1-i):
        for k_ in range(min(i+j, k+1-i-j)):
            ans = max(ans, calc(i, j, k_))
print(ans)

Submission status: Accepted

Solution code:
#128_D
import heapq
n, k = map(int, input().split())
v = list(map(int, input().split()))

ans = 0
for x in range(1, min(n, k)+1):
    for l in range(0, x+1):
        r = x - l
        v_ = v[:l] + v[n-r:]
        heapq.heapify(v_)
        for _ in range(k-x):
            if len(v_) == 0:
                break
            if v_[0] < 0:
                heapq.heappop(v_)
            else:
                break
        ans = max(ans, sum(v_))
        
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

n, k = map(int, input().split())
v = deque(list(map(int, input().split())))
m = min(n, k)
ans = 0
for i in range(m + 1):
    for j in range(m + 1 - i):
        w = deque(v)
        a = []
        for _ in range(i):
            p = w.pop()
            a.append(p)
        for _ in range(j):
            p = w.popleft()
            a.append(p)
        a.sort()
        for l in range(min(k - i - j, len(a))):
            if a[l] < 0:
                a[l] = 0
            else:
                break
        if sum(a) > ans:
            ans = sum(a)
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(1,n+1):
    vt =  v[i:][::-1] + v[:i]
    # print(vt)

    for j in range(0, min(n,k)+1):
        tmp = sorted(vt[:j])
        tmp_n = sum(tmp)
        for l in range(min(k-j, j)):
            if(tmp[l] < 0):
                tmp_n -= tmp[l]
        ans = max(ans, tmp_n)

print(ans)

Submission status: Accepted

Solution code:
N,K = map(int,(input().split()))
V = list(map(int,(input().split())))
left = [0]*(N+1)
right = [0]*(N+1)
ans = []

for i in range(1,N+1):
    left[i] = left[i-1] + V[i-1]

for i in range(1,N+1):
    right[i] = right[i-1] + V[N-i]


for i in range(min(N+1,K+1)):
    negal = []

    l = i
    for count in range(l):
        if l > 0 and V[count] < 0:
            negal.append(V[count])

    for j in range(min(N+1-i,K+1-i)):
        negar = []

        r = j
        for count in range(1,r+1):
            if r > 0 and V[N-count] < 0:
                negar.append(V[N-count])

        b = max(0,K-i-j)
        now = left[i] + right[j]

        nega = []
        nega.extend(negal)
        nega.extend(negar)
        nega.sort()
        s = 0
        for k in range(min(b,len(nega))):
            s += nega[k]
        
        if nega:
            ans.append(now-s)
        else:
            ans.append(now)

print(max(ans))

Submission status: Accepted

Solution code:
from functools import lru_cache
import sys
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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


@lru_cache(maxsize=None)
def solve(l, r):
    get = V[:l] + (V[-r:] if r != 0 else [])
    get.sort()
    minus = [x for x in get if x < 0]
    plus = [x for x in get if x >= 0]

    s = sum(plus) + sum(minus[K-l-r:])

    if (l + r) < N and (l + r) < K:
        get_left = solve(l + 1, r)
        get_right = solve(l, r + 1)
        s = max(s, get_left, get_right)

    return s


ans = solve(0, 0)

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
INF = 10 ** 9
MOD = 10 ** 9 + 7

def main(): 
    n,k = map(int,input().split())
    v = list(map(int,input().split()))
    
    
    ans = 0
    for l in range(n+1):
        for r in range(n-l,-1,-1):
            take = k - r - l
            if take < 0:
                continue
            tot = sum(v[:l])
            if r != 0:
                tot += sum(v[-r:])
            
            if take == 0:
                ans = max(ans,tot)
            else:
                minus = []
                for i in range(l):
                    if v[i] < 0:
                        minus.append(v[i])
                for i in range(n-1,n-r-1,-1):
                    if v[i] < 0:
                        minus.append(v[i])
                minus.sort()
                tot -= sum(minus[:take])
                ans = max(ans,tot)
    
    print(ans)
   
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import bisect
from collections import Counter, deque
# import copy
# from heapq import heappush, heappop, heapify
# from fractions import gcd
# import itertools
# from operator import attrgetter, itemgetter
import math

import sys

# import numpy as np

ipti = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n, k = list(map(int,ipti().split()))
    v = list(map(int,ipti().split()))

    #取り出せる宝石の数の最大
    pop_max = min(k,n)
    ans = 0

    for pop in range(pop_max + 1):
        push = k - pop
        for left in range(pop + 1):
            right = pop - left
            got_jewel = v[0:left]
            if right > 0:
                got_jewel.extend(v[-right:])

            got_jewel.sort()
            negative_count = bisect.bisect_left(got_jewel, 0)
            n_push = min(push, negative_count)
            value = sum(got_jewel[n_push:])
            ans = max(ans, value)

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq as pq
from collections import deque
from itertools import accumulate
N,K = map(int,input().split())
v = list(map(int,input().split()))
acc = [0]+list(accumulate(v,lambda x,y: x+y))
anss = -1
M = min(K,N)
for k in range(M+1):
    for i in range(k+1):
        ans = 0
        ls = deque(v)
        heap = []
        j = k-i
        ans += acc[i]+acc[-1]-acc[-1-j]
        for q in range(i):
            if ls:
                pq.heappush(heap,ls.popleft())
            else:
                break
        for q in range(j):
            if ls:
                pq.heappush(heap,ls.pop())
            else:
                break
        for i in range(K-k):
            if heap:
                x = pq.heappop(heap)
                if x < 0:
                    ans -= x
                else:
                    break
        anss = max(ans,anss)
print(anss)

Submission status: Accepted

Solution code:
"""from collections import *
from itertools import *
from bisect import *
from heapq import *

import math
from fractions import gcd
import sys
#input = sys.stdin.readline


"""
import copy
from collections import *
from heapq import *
N,K=map(int,input().split())
VVV=list(map(int,input().split()))
value=0

VV=deque(VVV)
Llst=[[]]
V=copy.copy(VV)
for i in range(min(K,N)):
    Llst.append(copy.copy(Llst[-1]))
    a=V.popleft()
    Llst[-1].append(a)

Rlst=[[]]
V=copy.copy(VV)
for i in range(min(K,N)):
    Rlst.append(copy.copy(Rlst[-1]))
    a=V.pop()
    Rlst[-1].append(a)

#print(Llst,Rlst)
for l in range(min(K,N)+1):
    for r in range(min(K,N)+1-l):
        lst=Llst[l]+Rlst[r]
        lst.sort(reverse=True)
        for i in range(K-l-r):
            if lst:
                if lst[-1]<0:
                    lst.pop()
                else:
                    break
            else:
                break
        value=max(value,sum(lst))
print(value)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
from bisect import bisect_left

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

amax = min(n,k)
ans = 0
for a in range(amax+1):
    bmax = amax - a
    for b in range(bmax+1):

        getlist = v[:a] + v[n-b:]
        getlist.sort()
        cdmax = k - a - b
        zero_index = bisect_left(getlist, 0)
        start = min(zero_index, cdmax)
        tmp = sum(getlist[start:])
        ans = max(ans, tmp)

print(ans)

Submission status: Accepted

Solution code:
import heapq

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

num = min(N, K)

lst = []

for i in range(1,num+1):
    for j in range(i+1):
        lst.append([j,i-j,K-i])

MAX = -100000000

for A, B, p in lst:
    tmp = sum(V[:A]) + sum(V[N-B:])
    D = V[:A] + V[N-B:]
    heapq.heapify(D)
    for _ in range(p):
        if not D:
            break
        k = heapq.heappop(D)
        if k >= 0:
            break
        else:
            tmp -= k
    if tmp > MAX:
        MAX = tmp

print(MAX)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
l = list(map(int,input().split()))

def count(a,b):
    if a+b >= n:
        ans = l
    else:
        if b == 0:
            ans = l[:a]
        else:
            ans = l[:a]+l[-b:]

    check = sum(ans)
    
    if k-a-b> 0:
        ans.sort()

        for i in range(min(k-a-b,len(ans))):
            if ans[i] < 0:
                check -= ans[i]
            else:
                break
    return check
sub = 0
for i in range(min(n,k)+1):
    for j in range(min(n,k)-i+1):
        sub = max(sub,count(i,j))
print(sub)

Submission status: Accepted

Solution code:
import heapq
from collections import deque
from copy import copy
n,k = map(int,input().split())
d = deque(list(map(int,input().split())))
maxvalue = 0
for i in range(k+1):
    for j in range(k-i+1):
        jewel = []
        x = copy(d)
        for _ in range(i):
            if x:
                jewel.append(x.popleft())
        for _ in range(j):
            if x:
                jewel.append(x.pop())
        heapq.heapify(jewel)
        for _ in range(k-i-j):
            if jewel:
                a = heapq.heappop(jewel)
                if a >= 0:
                    jewel.append(a)
                    break
        maxvalue = max(maxvalue,sum(jewel))
print(maxvalue)

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()

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

ans = 0
for l in range(K+1):
    left = V[:l]
    for r in range(K+1):
        if l+r > K or l+r > N:
            break
        if r != 0:
            pick = left + V[-r:]
        else:
            pick = left
        for i in range(K+1):
            if l+r+i >K:
                break
            if l+r >= i:
                pick.sort()
                ans = max(ans, sum(pick[i:]))
print(ans)

Submission status: Accepted

Solution code:
#python3
from collections import deque
from heapq import heappop, heappush
def main():
    n, k = map(int, input().split())
    vs = [int(i) for i in input().split()]
    ans = 0
    for l in range(k+1):
        for r in range(k-l+1):
            dl = k-l-r
            q = deque(vs)
            hav = []
            for _ in range(l):
                if len(q) == 0:
                    continue
                v = q.popleft()
                heappush(hav, v)
            for _ in range(r):
                if len(q) == 0:
                    continue
                u = q.pop()
                heappush(hav, u)
            for i in range(dl):
                if len(hav) == 0:
                    break
                val = heappop(hav)
                if val > 0:
                    heappush(hav, val)
            ans = max(ans, sum(hav))
    print(ans)
main()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,k = LI()
    v = LI()
    ans = -float("inf")
    for l in range(min(k,n)+1):
        vl = v[:l]
        for r in range(min(k,n)+1-l):
            vr = v[n-r:]
            s = max(0,k-l-r)
            nv = vl+vr
            nv.sort(reverse = True)
            while s > 0 and nv and nv[-1] < 0:
                nv.pop()
                s -= 1
            su = sum(nv)
            if ans < su:
                ans = su
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=1000000007
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n,k=LI()
  l=LI()

  cnt=min(n,k)
  ans=0
  for i in range(cnt+1):
    for j in range(cnt-i+1):
      q=[]
      for _i in range(i):
        heapq.heappush(q,l[_i])

      for _j in range(j):
        heapq.heappush(q,l[-(_j+1)])

      ln=len(q)
      for _ in range(min(k-i-j,ln)):
        x=heapq.heappop(q)
        if x>0:
          q.append(x)
          break
      # print(q)
      ans=max(ans,sum(q))

  return ans

# main()
print(main())

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
V = list(map(int, input().split()))

# 取り出しの計算量を下げるために累積和を計算しておく
V_rui_left = [0]
V_rui_right = [0]
for i in range(n):
    V_rui_left.append(V_rui_left[-1]+V[i])
    V_rui_right.insert(0, V_rui_right[0]+V[n-i-1])
V_rui_right = V_rui_right[::-1]

# 取り出す操作の回数 i
# 最大(k-i) 回の入れる操作が可能
ans = 0
for i in range(k+1):
    # 取り出し方をすべて見る
    score = 0
    if i >= n:
        Get = V
        score = V_rui_left[-1] - V_rui_left[0]
        Get = sorted(Get)

        # print(Get)
        
        ans = max(ans, score)
        for j in range(min(k-i, len(Get))):
            if Get[j] < 0:
                score -= Get[j]
            ans = max(ans, score)
    # x個左から取り出し、i-x個は右から取るとする
    else:
        for x in range(i+1):
            get = 0
            get += V_rui_left[x] - V_rui_left[0]
            get += V_rui_right[i-x] - V_rui_right[0]
            Get = []
            Get = V[:x] + V[n-(i-x):]
            
            Get = sorted(Get)
            # print(Get)

            score = get
            ans = max(ans, score)
            # 入れる操作
            for j in range(min(k-i, len(Get))):
                if Get[j] < 0:
                    score -= Get[j]
                ans = max(ans, score)

print(ans)

Submission status: Accepted

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

ans = 0
for p in range(min(k, n) + 1):
    for q in range(min(k, n) - p + 1):
        t = []
        for i in range(p):
            t.append(v[i])
        for i in range(q):
            t.append(v[n - 1 - i])
        t.sort()
        s = sum(t)
        for i in range(min(k - p - q, len(t))):
            if t[i] < 0:
                s -= t[i]
        ans = max(ans, s)

print(ans)

Submission status: Accepted

Solution code:
import heapq

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

ans = [V[0]]
for i in range(min(N, K)+1):
  for j in range(i+1):
    #print(i-j, j)
    # i-j個左から、i個右から取る
    lst = V[:i-j] + V[2*N-j:]
    #print(lst)
    heapq.heapify(lst)
    for _ in range(K-i):
      if len(lst) == 0:
        break
      elif min(lst) >= 0:
        ans.append(sum(lst))
        break
      else:
        heapq.heappop(lst)
        ans.append(sum(lst))
        #print(ans)
print(max(ans))

Submission status: Accepted

Solution code:
#  --*-coding:utf-8-*--

import bisect

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

QA = []
SA = 0
M = 0

N2 = min(N, K)

for a in range(N2+1):
    if a > 0:
        v = V[a-1]
        if v < 0:
            bisect.insort_left(QA, v)

        SA += v

    Q = QA[:]
    S = SA

    for b in range(N2-a+1):
        if b > 0:
            v = V[-b]
            if v < 0:
                bisect.insort_left(Q, v)

            S += v

        M = max(M, S - sum(Q[:min(len(Q), K-a-b):]))

print(M)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, K: int, V: "List[int]"):
    m = 0
    for k in range(0,min(K+1,N+1)):
        for l in range(k+1):
            r = k - l
            d = K - k
            arr = sorted(V[:l]+V[N-(k-l):])
            sum = 0
            n = []
            for a in arr:
                if a < 0 and d > 0:
                    d-=1
                    continue 
                sum += a
                n.append(a)
            m = max(sum,m)
    print(m)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    V = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, K, V)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
v = list(map(int,input().split()))
 
m=[]
for i in range(min(k,n)+1):
    for j in range(min(k,n)-i+1):

        t=sorted(v[:i]+v[:~j:-1])
 
        while t and(k-i-j)*t[0]<0:
            t.pop(0)
            j+=1
        m.append(sum(t))
print(max(m))

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from heapq import heappop
import heapq
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
 
N, K = MAP()
V = LIST()
V = deque(V)
 
# R = A + B
max_R = min(N, K)
# A, B 全探索
ans = 0
for R in range(1, max_R+1):
    for i in range(0, R+1):
        minus_count = 0
 
        v = deepcopy(V)
        pocket = []
        heapq.heapify(pocket)
        A = i
        B = R - i
        for a in range(A):
            a_pop = v.popleft()
            if a_pop < 0:
                minus_count += 1
            heappush(pocket, a_pop)
        for b in range(B):
            b_pop = v.pop()
            if b_pop < 0:
                minus_count += 1
            heappush(pocket, b_pop)
        dump = K - R
        dump_time = min(minus_count, dump)

        if dump_time > 0:
            for d in range(dump_time):
                x = heappop(pocket) 
 
        wa = sum(pocket)
        if ans <= wa:
            ans = wa
print(ans)