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
from bisect import bisect_left


read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def main():
    N, K, *V = map(int, read().split())

    ans = 0
    for k in range(min(N, K) + 1):
        for left in range(k + 1):
            right = k - left
            tmp = V[:left] + (V[-right:] if right else [])
            tmp.sort()

            idx = bisect_left(tmp, 0)
            if idx > K - k:
                idx = K - k

            this_ans = sum(tmp[idx:])
            if ans < this_ans:
                ans = this_ans

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
V = list(map(int,input().split()))
Vrev = V[::-1]
ans = 0
for a in range(N+1):
    for b in range(min(K-a,N-a)+1):
        VV = V[:a] + Vrev[:b]
        VV.sort(reverse=True)
        for k in range(min(K-a-b,len(VV))):
            if VV[-1] < 0:
                VV.pop()
        ans = max(sum(VV),ans)
print(ans)

Submission status: Accepted

Solution code:
import sys

N, K = map(int, sys.stdin.readline().strip().split())
V = list(map(int, sys.stdin.readline().strip().split()))

ans=0
act = min(N, K)
for i in range(act + 1): # 左
    for j in range(N - act + i, N+1): # 右
        count = V[0:i] + V[j:N]
        count.sort()
        ans = max(ans, sum(count))
        for x in range(1, K - len(count) + 1): # 正負関係なく小さいものを捨てる 
            # print(sum(count[x:]))
            ans = max(ans, sum(count[x:]))
print(ans)

Submission status: Accepted

Solution code:
import heapq

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

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

ans = 0
for i in range(1, K+1):
    if i > N:
        continue
    for j in range(i+1):
        tmp = 0
        q = V[:j] + V[N-i+j:]
        heapq.heapify(q)
        for _ in range(min(i, K-i)):
            tmp_min = heapq.heappop(q)
            ans = max(ans, sum(q))
            if tmp_min > 0:
                ans = max(ans, sum(q)+tmp_min)
                break
        ans = max(ans, sum(q))

print(ans)

Submission status: Accepted

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

ans = -(10**9)
for A in range(0,K+1,1):
    for B in range(0,min(K,N)-A+1,1):
        tmp = V[0:A] + V[N-B:N]
        tmp.sort()
        for i in range(0,min(K-A-B,A+B),1):
            tmp[i]=max(tmp[i],0)
        ans = max(ans,sum(tmp))
print(ans)

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

MAX = min(N, K) + 1

ans = 0
for a in range(MAX):
    for b in range(MAX):
        if a + b >= MAX:
            continue
        jewels = []
        for i in range(a):
            jewels.append(V[i])
        for j in range(b):
            jewels.append(V[-(j + 1)])
        jewels = sorted(jewels)
        total = sum(jewels)
        if K - (a + b) <= 0:
            ans = max(total, ans)
            continue
        for i in range(K - a - b):
            if i < len(jewels) and jewels[i] < 0:
                total += abs(jewels[i])
        ans = max(total, ans)
print(ans)

Submission status: Accepted

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


def get_jewelries(box, left_pop, right_pop):
    if left_pop + right_pop >= len(box):
        return box[:]

    left = box[:left_pop]
    right = box[-right_pop:] if right_pop else []

    return left + right


candidates = []
pop_max = min(k, n)
for pop_count in range(pop_max+1):
    residue = k - pop_count

    for left_pop in range(pop_count+1):
        right_pop = pop_count - left_pop
        jewelries = get_jewelries(V, left_pop, right_pop)
        jewelries.sort(reverse=True)

        for _ in range(residue):
            if not jewelries:
                break
            if jewelries[-1] < 0:
                jewelries.pop()

        value = sum(jewelries)
        candidates.append(value)

print(max(candidates))

Submission status: Accepted

Solution code:
from collections import deque
import heapq
N,K = map(int,input().split())
A = list(map(int,input().split()))
res = 0
# 左からa個
for a in range(N+1):
  # 右からb個
  for b in range(N+1):
    if a+b>N or a+b>K: continue
    hands = []
    A1 = deque(A[::])
    for _ in range(a):
      hands.append(A1.popleft())
    for _ in range(b):
      hands.append(A1.pop())
    hands.sort()
    hands = deque(hands)
    rem = K - a - b
    for _ in range(rem):
      if hands and hands[0] < 0:
        hands.popleft()
      else:
        break
    res = max(res, sum(hands))

print(res)

Submission status: Accepted

Solution code:
import sys
import copy
import heapq
from collections import deque
input = lambda: sys.stdin.readline().rstrip()
INF = 10**9 + 7


def solve():
    N, K = map(int, input().split())
    V = deque(list(map(int, input().split())))

    ans = -INF
    for n in range(1, N + 1):
        if n > K:
            break
        for rn in range(n + 1):
            ln = n - rn
            tv = copy.copy(V)
            pv = 0
            mv = []
            heapq.heapify(mv)
            for _ in range(rn):
                v = tv.pop()
                if v >= 0:
                    pv += v
                else:
                    heapq.heappush(mv, v)
            for _ in range(ln):
                v = tv.popleft()
                if v >= 0:
                    pv += v
                else:
                    heapq.heappush(mv, v)

            mvlen = min(K - n, len(mv))
            for _ in range(0, mvlen):
                heapq.heappop(mv)

            #print(ln, rn, pv, mv)
            ans = max(ans, pv + sum(mv))

    print(max(0, ans))


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    N, K = map(int, input().split())
    V = list(map(int, input().split()))
    ans = 0
    for l in range(K+1):
        for r in range(K-l+1):
            if l+r > N or l+r>K:
                continue
            now = []
            val = 0
            for i in range(l):
                now.append(V[i])
                val += V[i]
            for j in range(r):
                now.append(V[-j-1])
                val += V[-j-1]

            d = K-l-r
            now.sort()
            for i in range(d):
                if i >= len(now):
                    break
                if now[i] > 0:
                    break
                val -= now[i]
            ans=max(ans,val)

    print(ans)

resolve()

Submission status: Accepted

Solution code:
# import string
import unittest
from io import StringIO
import sys
sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    N, K = map(int, input().split())
    V = list(map(int, input().split()))
    ans = 0
    for l in range(K+1):
        for r in range(K-l+1):
            if l+r > N:
                continue
            now = []
            val = 0
            for i in range(l):
                now.append(V[i])
                val += V[i]
            for j in range(r):
                now.append(V[-j-1])
                val += V[-j-1]

            d = K-l-r
            now.sort()
            for i in range(d):
                if i >= len(now):
                    break
                if now[i] > 0:
                    break
                val -= now[i]
            ans=max(ans,val)

    print(ans)

resolve()

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit
from bisect import bisect_left


def main():
    input = stdin.buffer.readline
    n, k = map(int, input().split())
    v = list(map(int, input().split()))

    ans = 0

    for i in range(1, k + 1):
        if i < n:
            for j in range(i + 1):
                cand = v[: j] + v[n - i + j:]
                cand.sort()
                idx = min(bisect_left(cand, 0), k - i)
                if idx > 0 or i > 0:
                    ans = max(ans, sum(cand[idx:]))

        else:
            cand = v
            cand.sort()
            idx = bisect_left(cand, 0)
            ans = max(ans, sum(cand[idx:]))

    print(ans)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Accepted

Solution code:
jewel, query = map(int, input().split())
t = min(jewel, query)
dq = [int(i) for i in input().split()]
ans = []

for i in range(t+1):
  for j in range(i+1):
    have = dq[:j] + dq[(jewel-i+j):]
    drop = query - len(have)

    for k in range(drop):
      if not have:
        break
      
      cand = min(have)
      if cand < 0:
        have.remove(cand)
      else:
        break
        
    ans.append(sum(have))
    
print(max(ans))

Submission status: Accepted

Solution code:

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

MAX = 0
for k in range(1, K+1):
    for ka in range(k+1):
        for kb in range(k+1-ka):
            kcd = k - ka - kb
            
            if (ka+kb <= kcd) or (ka+kb > N):
                continue
            
            #print(ka, kb, kcd)
            s = V[:ka] + V[-kb:] if kb != 0 else V[:ka]
            s.sort()
            #print(s[kcd:], sum(s[kcd:]))
            MAX = max(MAX, sum(s[kcd:]))

print(MAX)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)

n,k = map(int,input().split())
v = list(map(int,input().split()))
ans=0
for l in range(k+1):
    for r in range(k-l+1):
        if l+r > n :break

        d=k-l-r
        now=0
        s=[]

        for i in range(l):
            now+=v[i]
            s.append(v[i])

        for i in range(n-r,n):
            now+=v[i]
            s.append(v[i])

        s.sort()
        for i in range(d):
            if(i >= len(s)):break
            if s[i] > 0 :break

            now -= s[i]

        ans=max(now,ans)
print(ans)

Submission status: Accepted

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

ans = 0
for left in range(min(n, k+1)):
    for right in range(min(n-left+1, k-left+1)):
        l = v[:left]
        l+=v[::-1][:right]
        l.sort()
        temp = sum(l)
        for t in range(max(0, min(len(l), k-left-right))):
            if l[t]<0:
                temp-=l[t]
        ans = max(ans, temp)
print(ans)

Submission status: Accepted

Solution code:
import heapq
from collections import deque
from functools import lru_cache

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

for l in range(0,K + 1):
  for r in range(0,K - l + 1):
    d = K - r - l
    tmp = 0
    have = []
    if l + r > N:
      continue
    for i in range(0,l):
      tmp += V[i]
      have.append(V[i])
    for j in range(N - r,N):
      tmp += V[j]
      have.append(V[j])
    h = len(have)
    #print(have)
    have = sorted(have)
    for k in range(0,d):
      #print(have,sum(have))
      if k >= h:
        break
      if have[k] > 0:
        break
      tmp -= have[k]
    ans = max(tmp,ans)
    
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

m = min(k, n)
res = 0
for A in range(0, m + 1):
    for B in range(0, m + 1):
        if A + B > m:
            continue
        if B == 0:
            L = v[:A]
        else:
            L = v[:A] + v[-B:]
        L.sort()
        L = deque(L)
        num = k - (A + B)
        for i in range(num):
            if len(L) == 0:
                continue
            elif len(L) == 1:
                if L[0] < 0:
                    L.pop()
            else:
                Remove = L.popleft()
                if Remove > 0:
                    L.appendleft(Remove)
        res = max(res, sum(L))

print(res)

Submission status: Accepted

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

#左からl個、右からr個取り出す
for l in range(K + 1):
    for r in range(K - l + 1):
        if l + r > N: continue
        d = K - l - r
        now = 0
        having = []
        for i in range(l):
            now += V[i]
            having.append(V[i])
        for i in range(N-r, N):
            now += V[i]
            having.append(V[i])

        having.sort()
        #d回まで持っている宝石(価値がマイナス)を戻す
        for i in range(d):
            if i >= len(having): break
            if having[i] >= 0: break
            now -= having[i]
        ans = max(ans, now)

print(ans)

Submission status: Accepted

Solution code:
import heapq
N, K = map(int, input().split())
d = [int(x) for x in map(int, input().split())]
e = d[::-1]

res = 0
num = min(N, K)
for i in range(num + 1):
    for j in range(num - i, -1, -1):
        s = d[:i] + e[:j]
        if not s:
            continue
        heapq.heapify(s)
        res = max(res, sum(s))
        l = min(i + j, K - (i + j))
        while l:
            heapq.heappop(s)
            res = max(res, sum(s))
            l -= 1
print(res)

Submission status: Accepted

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

res = 0
num = min(k, n)
for i in range(num + 1):
    for j in range(num + 1 - i):
        l = min(k - (i + j), i + j)
        s = d[:i] + d[-j:] if j != 0 else d[:i]
        heapify(s)
        for _ in range(l):
            tmp = heappop(s)
            if tmp > 0:
                heappush(s, tmp)
        res = max(res, sum(s))
print(res)

Submission status: Accepted

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

res = 0
num = min(k, n)
for a in range(num + 1):
    for b in range(num + 1 - a):
        l = min(k - (a + b), a + b)
        s = d[:a] + d[-b:] if b != 0 else d[:a]
        heapify(s)
        for _ in range(l):
            tmp = heappop(s)
            if tmp > 0:
                heappush(s, tmp)
                break
        res = max(res, sum(s))
print(res)

Submission status: Accepted

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

res = 0
num = min(k, n)
for a in range(num + 1):
    for b in range(num + 1 - a):
        trash = k - (a + b)
        s = d[:a] + d[-b:] if b != 0 else d[:a]
        heapify(s)
        for _ in range(min(trash, a + b)):
            tmp = heappop(s)
            if tmp > 0:
                heappush(s, tmp)
                break
        res = max(res, sum(s))
print(res)

Submission status: Accepted

Solution code:
N,K = list(map(int,input().split()))
V = list(map(int,input().split()))
out = 0
for left in range(0,K+1):
    for right in range(0,K-left+1):
        if left==0 and right==0:
            continue
        if left + right <= N:
            if right!=0:
                box = V[0:left] + V[N-right:N]
            else:
                box = V[0:left]
            S = sum(box)
            box.sort(reverse=True)
            t = -1
            Life = K-(left+right)
            while Life>0 and abs(t)<=len(box) and box[t]<0:
                S = S-box[t]
                Life += -1
                t += -1
            if S>out:
                out = S
print(max(out,0))

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 = -float("inf")

left = v[:]
right = v[::-1]

import bisect

for i in range(n + 1):
    for j in range(n + 1 - i):
        if i + j > k:
            continue
        left_and_right = left[:i] + right[:j]
        left_and_right.sort()
        cnt = k - (i + j)
        idx = bisect.bisect_left(left_and_right, 0)
        minus = sum(left_and_right[:min(cnt, idx)])
        ans = max(sum(left_and_right) - minus, ans)

print(ans)

Submission status: Accepted

Solution code:
# 左から取り出すパターンは最大50通り
# 右から取り出すパターンは最大50通り
# その組み合わせは2500通り
# その全通りに対して、マイナスの石を引けるだけ引くパターンを試すと50
# 125000
# すべて試す

import sys
readline = sys.stdin.readline

N,K = map(int,readline().split())
V = [0] + list(map(int,readline().split())) + [0]
N += 2
K += 2

leftsum = 0
leftminus = []
ans = -(10 ** 9)
for left in range(min(N,K)):
  leftsum += V[left]
  if V[left] < 0:
    leftminus += [V[left]]
  rightsum = 0
  rightminus = []
  limit = min(N - (left + 1) , K - (left + 1))
  for right in range(N - 1, N - limit - 1, -1):
    rightsum += V[right]
    if V[right] < 0:
      rightminus += [V[right]]
    allsum = leftsum + rightsum
    rest = max(K - ((left + 1) + (N - right)),0)
    allminus = sorted(leftminus + rightminus)
    allsum -= sum(allminus[:rest])
    if allsum > ans:
      ans = allsum
print(ans)

Submission status: Accepted

Solution code:
def resolve():
    N, K = list(map(int, input().split()))
    V = list(map(int, input().split()))
    start = (K+1)//2 if K%2==1 else K//2
    maxvalue = 0
    for npop in range(start, K+1):
        if npop >= N:
            npush = K - N
            negs = sorted([v for v in V if v < 0])
            posis = [v for v in V if v >= 0]
            maxvalue = max(maxvalue, sum(posis)+(sum(negs)-sum(negs[:npush])))
            continue

        for nleft in range(npop+1):
            nright = npop-nleft
            picked = V[:nleft] + V[N-nright:]
            negs = sorted([v for v in picked if v < 0])
            posis = [v for v in picked if v >= 0]
            npush = min(K-npop, len(negs))
            maxvalue = max(maxvalue, sum(posis)+(sum(negs)-sum(negs[:npush])))
    print(maxvalue)
            


if '__main__' == __name__:
    resolve()

Submission status: Accepted

Solution code:
from collections import deque
from copy import deepcopy
import heapq

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

minus=[[[0]*(N+1) for _ in range(N+1)] for _ in range(N+1)]

vdeque=deque(V)

for left in range(N+1):
    for right in range(N-left+1):
        v=deepcopy(vdeque)
        q=[]

        tleft=left
        while tleft>0:
            vi=deque.popleft(v)
            if vi<0:
                heapq.heappush(q,vi)
            tleft-=1
        
        tright=right

        while tright>0:
            vj=deque.pop(v)
            if vj<0:
                heapq.heappush(q,vj)
            tright-=1
        
        for k in range(1,N+1):
            if len(q)>0:
                minus[k][left][right]=minus[k-1][left][right]-heapq.heappop(q)
            else:
                minus[k][left][right]=minus[k-1][left][right]

leftacum=[0]*(N+1)
rightacum=[0]*(N+1)

for i in range(N):
    leftacum[i+1]=leftacum[i]+V[i]
    rightacum[i+1]=rightacum[i]+V[N-i-1]

ans=-10**10

for left in range(N+1):
    for right in range(N-left+1):
        k=min(N,K-left-right)
        if k<0:
            continue

        ans=max(ans,leftacum[left]+rightacum[right]+minus[k][left][right])

print(ans)

Submission status: Accepted

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

ans = 0
num = min(k, n)
for a in range(num + 1):
    for b in range(num + 1 - a):
        trash = k - (a + b)
        get = v[:a] + v[-b:] if b != 0 else v[:a]
        heapify(get)
        for _ in range(min(trash, a + b)):
            temp = heappop(get)
            if temp > 0:
                heappush(get, temp)
                break
        SUM = sum(get)
        if ans < SUM:ans = SUM
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
from collections import deque, defaultdict
from itertools import combinations, combinations_with_replacement
import bisect
from math import factorial, sqrt, log, ceil, floor

def main():
    #N, M = map(int, input().split())
    N, K = map(int, input().split())
    Vs = list(map(int, input().split()))

    max_value = None
    for l in range(min([K+1, N+1])):
        for r in range(min([K+1-l, N-l+1])):
            for b in range(K - l - r + 1):
                values = list(Vs[:l])
                if r > 0:
                    values += list(Vs[-r:])
                values = sorted(values)
                for i in range(b):
                    if values and values[0] < 0:
                        values.pop(0)
                    else:
                        break
                value = sum(values)
                if max_value is None or max_value < value:
                    max_value = value

    print(max_value)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
from heapq import heappush, heappop
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):
        rest = k - i - j
        if i + j > n or rest < 0:
            continue
        tans = 0
        q = deque(v)
        poppen = []
        for _ in range(i):
            tans += q[0]
            heappush(poppen, q.popleft())
        for _ in range(j):
            tans += q[-1]
            heappush(poppen, q.pop())
        for _ in range(rest):
            if not poppen or poppen[0] >= 0:
                break
            tans -= heappop(poppen)
        ans = max(ans, tans)
print(ans)

Submission status: Accepted

Solution code:
import bisect

abcd = []
n, k = map(int, input().split()) 
v_list = list(map(int, input().split())) 

for a in range(0, k+1):
    for b in range(0, k+1-a):
        for c in range(0, k+1-a-b):
            d = k-a-b-c
            abcd.append([a,b,c,d])


ans = 0
for curr_abcd in abcd:
    a,b,c,d = curr_abcd
    cd = c+d
    if a + b >= n:
        have = sorted(v_list)
    else:
        have = sorted(v_list[0:a] + v_list[n-b:n]) 

    minus_cnt = bisect.bisect_right(have,0)
    have = have[ min(minus_cnt, cd) : ]
    curr_sum = sum(have) 
    ans = max(ans, curr_sum)

print(ans)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
import heapq
def main():
    n,k=map(int,input().split())
    V=list(map(int,input().split()))
    ans=0
    for a in range(min(k+1,n+1)):
        for b in range(min(k-a,n-a)+1):
            cd=k-(a+b)
            H=[]
            sum_V=0
            for i in range(n):
                v=V[i]
                if i+1<=a or i>=n-b:
                    sum_V+=v
                    if v<0:
                        heapq.heappush(H,V[i])
            while H and cd>0:
                sum_V-=heapq.heappop(H)
                cd-=1
            ans=max(sum_V,ans)
    print(ans)


if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    n, k, *v = map(int, open(0).read().split())
    w = v[::-1]

    ans = 0
    m = min(n, k)
    for i in range(m + 1):
        for j in range(m + 1 - i):
            d = k - (i + j)
            g = v[:i] + w[:j]
            ps = sum(x for x in g if x > 0)
            ng = [x for x in g if x < 0]
            ng.sort()
            val = ps + sum(ng[d:])
            ans = max(ans, val)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
v=list(map(int,input().split()))
times=min(n,k)
ans=0
for i in range(times+1):
    l=v[:i]
    for j in range(times-i+1):
        r=l+v[n-j:]
        rest=k-i-j
        val=sum(r)
        r=sorted(r)
        if len(r)>0:
            for p in range(min(rest,len(r))):
                if r[p]<0:
                    val-=r[p]
                else:
                    break
        if val>ans:
            ans=val
print(ans)

Submission status: Accepted

Solution code:
import sys
import collections
import itertools

sys.setrecursionlimit(10 ** 8)
ni = lambda: int(sys.stdin.readline())
nm = lambda: map(int, sys.stdin.readline().split())
nl = lambda: list(nm())
ns = lambda: sys.stdin.readline().rstrip()

N, K = nm()
V = nl()
assert len(V) == N
INF = 10 ** 9


def solve():
    ans = 0
    for i in range(K + 1):
        if i > N:
            break
        for j in range(K + 1 - i):
            if i + j > N:
                break
            v = V[:i] + V[N - j :]
            v.sort()
            s = sum(v)
            k = 0
            while k < K - i - j:
                if k >= len(v):
                    break
                if v[k] >= 0:
                    break
                s -= v[k]
                k += 1
            if ans < s:
                ans = s
                # print(f"> ans={ans} i={i}, j={j}, k={k}", file=sys.stderr)
    return ans


print(solve())

Submission status: Accepted

Solution code:
import heapq  # heapqライブラリのimport
N,K=map(int,input().split())
V=list(map(int,input().split()))
ans=0
for i in range(1,min(N,K)+1):
 for t in range(i+1):
  B=V[0:i-t]+V[N-t:N] 
  total=sum(B)
  cut=0
  for j in  range(min(i,K-i)):
   heapq.heapify(B)
   cut=min(cut,cut+heapq.heappop(B))
  ans=max(ans,total-cut)
print(ans)

Submission status: Accepted

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

if k<n*2:
    ans=0
    for i in range(k+1):
        for j in range(k-i+1):
            v_r=v[:i]
            v_l=v[(n-j):]
            sute_cnt=k-(i+j)
            v_new=v_r+v_l
            v_new.sort()
            # print(i, j, v_r, v_l, sute_cnt, v_new)
            s=sum(v_new)
            if not v_new:
                continue
            for indx in range(len(v_new)):
                if v_new[indx]<0 and sute_cnt>0:
                    s-=v_new[indx]
                    sute_cnt-=1
                else:
                    break
            ans=max(ans,s)
    print(ans)

else:
    ans=0
    for i in range(n):
        if v[i]>=0:
            ans+=v[i]
    print(ans)

Submission status: Accepted

Solution code:
from collections import deque
n,k=map(int,input().split())
v=list(map(int,input().split()))
cs_l=[0]
cs_r=[0]
cs1,cs2=0,0
for i in range(n):
  cs1+=v[i]
  cs2+=v[-i-1]
  cs_l.append(cs1)
  cs_r.append(cs2)

ans=0
for i in range(1,k+1):# 取得する操作をi回行う
  for l in range(i+1): # 左からl個取る
    r=i-l
    if r+l>=n:
      point=cs_r[-1]
      minus=[vi for vi in v if vi<0]
      n_minus=min(n-k,len(minus))
    else:
      point=cs_l[l]+cs_r[r]
      minus=[vi for vi in v[:l] if vi<0]
      if r>0:
        minus+=[vi for vi in v[-r:] if vi<0]
      n_minus=min(k-r-l,len(minus))
    if n_minus>0:
      minus.sort()
      point-=sum(minus[:n_minus])
    ans=max(ans,point)

print(ans)

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit


def main():
    input = stdin.buffer.readline
    n, k = map(int, input().split())
    v = list(map(int, input().split()))

    max = 0

    for i in range(k):
        if i <= n:
            for j in range(i + 1):
                candidate = v[0:j + 1]
                candidate.extend(v[n - i + j:n])
                candidate.sort()
                for d in range(k - i):
                    tmp = sum(candidate[d:n])
                    if tmp > max:
                        max = tmp
        else:
            candidate = v
            candidate.sort()
            for d in range(k - i):
                tmp = sum(candidate[d:n])
                if tmp > max:
                    max = tmp
    print(max)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Accepted

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

if k <= n:
    ans = - 10 ** 9
    for i in range(k + 1):
        for j in range(i + 1):
            tmp = v[:j]
            if i != j:
                tmp += v[-(i - j):]
            tmp.sort()
            ans = max(ans, sum(tmp[k - i:]))
            if k != i:
                ans = max(ans, sum(tmp[k - i - 1:]))

elif k >= 2 * n:
    v.sort(reverse = True)
    ans = 0
    for num in v:
        if num <= 0:
            break
        ans += num

else:
    ans = - 10 ** 9
    for i in range(n + 1):
        for j in range(i + 1):
            tmp = v[:j]
            if i != j:
                tmp += v[-(i - j):]
            tmp.sort(reverse = True)
            ans_tmp = 0
            for l, num in enumerate(tmp):
                if l >= 2 * i - k and num <= 0:
                    break
                ans_tmp += num
            ans = max(ans, ans_tmp)

print(ans)

Submission status: Accepted

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

import heapq

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

max_try = min(n, k)
ans = 0

for a in range(0, max_try+1):
    for b in range(0, max_try+1-a):
        c = k-(a+b)
        # print(a, b, c, "", end="")
        # print(a, b, c)
        ans_tmp = 0
        garbage = []
        heapq.heapify(garbage)
        for i in range(a):
            num = v[i]
            ans_tmp += num

            if num < 0:
                heapq.heappush(garbage, num)

        for i in range(b):
            num = v[-1-i]
            ans_tmp += num

            if num < 0:
                heapq.heappush(garbage, num)

        # print(garbage)
        for i in range(c):
            # print(garbage)
            if len(garbage) == 0:
                break
            num = -heapq.heappop(garbage)
            # print(num)
            ans_tmp += num
        # print()
        # print(ans_tmp)
        ans = max(ans, ans_tmp)

print(ans)