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

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

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

print(ans)

Submission status: Accepted

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

R = min(N, K)
l = []
ans = 0
for a in range(R + 1):
  for b in range(R + 1 - a):
    l = V[:a] + V[N - b:]
    l.sort()
    for i in range(K - a - b + 1):
      ans = max(ans, sum(l[i:]))
print(max(ans, 0))

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, log2
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

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

N, K = MAP()
V = LIST()
R = min(N, K)

max_ = 0
for A in range(R+1):
	for B in range(R+1):
		if A+B > R:
			continue
		if B == 0:
			lis = V[:A]
		else:
			lis = V[:A] +  V[-B:]
		# print(A, B)
		# print(lis)
		lis.sort()
		for i in range(K-(A+B)):
			if lis and lis[0] < 0:
				lis.pop(0)
		tmp = sum(lis)
		max_ = max(max_, tmp)
print(max_)

Submission status: Accepted

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

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

I = []

for i in range(min(n, k)+1):
    for j in range(min(n, k)-i+1):
        I.append([i, j])

Vr = V[::-1]

maxi = 0

for l in I:
    H = V[0:l[0]] + Vr[0:l[1]]
    H.sort()
    t = min(len(H), k - len(H))
    t = max(0, t)
    minus = sum(s < 0 for s in H)
    score = sum(H[min(minus, t):])
    maxi = max(maxi, score)

print(maxi)

Submission status: Accepted

Solution code:
def solve():
    A, K = map(int, input().split())
    V = list(map(int, input().split()))
    ans = 0
    for left in range(min(K, A) + 1):
        for right in range(min(K, A) - left + 1):
            S = [0] + V[:left] + V[A - right:]
            S.sort()
            drop, rest = 0, K - (left + right)
            while drop < rest and S[drop] < 0: drop += 1
            ans = max(ans, sum(S) - sum(S[:drop]))
    return ans

print(solve())

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)

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


ans = 0
for i in range(K+1):
  hand = V[:i]
  for j in range(K-i+1):
    if j != 0:
      x = hand + V[max(N-j, i):]
    else:
      x = hand
    rest = K - i - j
    summ = sum(v for i, v in enumerate(sorted(x)) if i >= rest or v > 0)
    ans = max(ans, summ)
    # print(f"K={K}, i={i}, j={j}, rest={rest}, sum={summ}, x={x}")
print(ans)

Submission status: Accepted

Solution code:
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+1):
        if L+R <= min(N,K):
            S = max(0,K-(L+R))
#            print(S,V[:L],V[N-R:])
            A = sorted(V[:L]+V[N-R:])
            for k in range(len(A)):
                if A[k] < 0 and S > 0:
                    A[k] = 0
                    S -= 1
            ans = max(ans,sum(A))
print(ans)

Submission status: Accepted

Solution code:
N,K=map(int, input().split())
V=list(map(int, input().split()))
ans=0
from heapq import heapify,heappop
for j in range(1,min(N,K)+1):
    for k in range(j+1):
        x=V[:k]+V[N-j+k:]
        heapify(x)
        b=K-j
        while len(x)>0 and x[0]<0 and b>0:
            heappop(x)
            b-=1
        ans=max(ans,sum(x))
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):#何個取るか
    if i>K:
        break
    for r in range(i+1):

        l=i-r
        a=V[:r]
        b=V[N-l:]
        f=max(0,K-i)
        c=a+b
        c.sort()
        k=0
        t=0
        for j in c:
            if t<f and j<0:
                t+=1
                continue
            k+=j
        ans=max(ans,k)
print(ans)

Submission status: Accepted

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

# 何個捨てるか
ans = 0
for i in range(K):
    # 右から何個目まで取るか
    if K-i >= N:
        pick = q
        pick = sorted(pick)
        for m in range(i+1):
            ans = max(sum(pick[m:]),ans)        
    else:
        pick = q[:K-i]
        pick = sorted(pick)
        ans = max(sum(pick[i:]),ans)
        for j in range(min(N,K-i)):
            pick = []
            pick = q[:j]+q[-(K-i-j):]
            pick = sorted(pick)
            for m in range(i+1):
                ans = max(sum(pick[m:]),ans)        
print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
V = list(map(int, input().split()))
ans = 0
for pull in range(k + 1):
    for back in range(k):
        if pull + back != k:
            continue
        for l in range(pull+1):
            r = pull - l
            if r > 0:
                hand = V[:l] + V[-r:]
            else:
                hand = V[:l]
            if pull >= n:
                hand = V
            hand = sorted(hand, reverse=True)
            for _ in range(back):
                if len(hand) == 0:
                    break
                if hand[-1] < 0:
                    hand.pop()
                else:
                    break
            ans = max(ans, sum(hand))
print(ans)

Submission status: Accepted

Solution code:
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-a+1):
        items = V[:a] + V[N-b:]
        items.sort()
        for c in range(K-a-b+1):
            ans = max(ans, sum(items[c:]))
print(ans)

Submission status: Accepted

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

for cd in range(K):
    ab = min(N, K-cd)
    for left_ab in range(ab+1):
        right_ab = ab - left_ab
        if right_ab > 0:
            pick = V[:left_ab] + V[-right_ab:]
        else:
            pick = V[:left_ab]
        pick.sort()
        neg = 0
        while neg < len(pick):
            if pick[neg]<0:
                neg+=1
                continue
            else:
                break
        v = sum(pick[min(neg,cd):])
        value = max(value,v)
        
print(value)

Submission status: Accepted

Solution code:
import sys
from heapq import heappop, heappush

def main():
    input = sys.stdin.readline
    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, K) - left + 1):
            heap = []
            for v in V[:left]:
                heappush(heap, v)

            for v in V[N - right:]:
                heappush(heap, v)

            cnt = left + right
            while cnt < K and len(heap) > 0:
                v = heappop(heap)
                if v > 0:
                    heappush(heap, v)
                    break

                cnt += 1

            ans = max(ans, sum(heap))

    return ans


if __name__ == '__main__':
    print(main())

Submission status: Accepted

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

s = 0
for i in range(min(N, K) + 1):
  # res = C + D
  res = K - i
  
  # i = A + B
  for j in range(i + 1):
    # j: B, k: A
    k = i - j
    
    # Jewel in hand
    Q = sorted(V[:j] + V[N - k:])
    
    # Number of negative jewels
    minus = sum([q < 0 for q in Q])
    
    # Drop some of negative, and sum up
    score = sum(Q[min(minus, res):])
    
    # Update score
    s = max(s, score)

print(s)

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 - a, k - a) + 1):
        v_use = v[:a] + v[-b:] if b >= 1 else v[:a]
        t = k - a - b
        s = 0
        for j in sorted(v_use):
            if j < 0 and t > 0:
                s += -j
                t -= 1
        ans = max(ans, sum(v_use) + s)

print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
V = list(map(int, input().split()))
M = min(N, K)
ans = 0
for p in range(M+1):
  for q in range(M-p+1):
    left = []
    right = []
    if p > 0:
      left = V[:p]
    if q > 0:
      right = V[-q:]
    have = sorted((left+right).copy())
    if len(have) > 0:
      for i in range(min(len(have),K-p-q+1)):
        if have[i] > 0:
          break
      ans = max(sum(have[i:]),ans)
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(n):
    for b in range(a,n+1):
        c = 0
        if a+n-b <= k:
            p = k-(a+n-b)
            s = v[:a]+v[b:]
            s.sort()
            for t in s:
                if p >= 1 and t < 0:
                    p -= 1
                else:
                    c += t

        ans = max(c,ans)

print(ans)

Submission status: Accepted

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

results = []
for a in range(n + 1):
    for b in range(min(n - a, k - a) + 1):
        p = v[:a] + v[n - b:]
        p.sort()
        for i in range(k - a - b + 1):
            results.append(sum(p[i:]))
print(max(results))

Submission status: Accepted

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

ans = 0
if n == 1:
    ans = max(0, v[0])
else:
    ans = 0 if k < n else sum(v)
    for i in range(min(k + 1, n)):
        for j in range(i + 1):
            t = v[:j]
            if j != i:
                t += v[j - i:]
            t.sort()
            for p in range(k - i):
                if len(t) > 0 and t[0] < 0:
                    t.pop(0)
                else:
                    break
            if len(t) == 0:
                t = [0]
            ans = max(ans, sum(t))
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
#num= list(map(int, input().split()))
#from operator import itemgetter
n, k= map(int, input().split())
v= list(map(int, input().split()))

sum_max = 0
for t in range(min(2*n+1, k+1)):
  if t > 0:
    for put in range(t//2 + 1):
      pick = t - put
      for left in range(min(pick+1,n+1)):
        right= min(pick,n) - left
        if left!=0:
          vs=v[0:left]
        else:
          vs=[]
        if right!=0:
          vs.extend(v[-right:])
        vs.sort()
        for i in range(put):
          if vs !=[]:
            if vs[0] < 0:
              del vs[0]
            else:
              break
          else:
            break
#        print("pick"+str(pick)+"put"+str(put)+"left"+str(left)+"right"+str(right)+"="+str(sum(vs)))
        sum_max = max(sum_max, sum(vs))
print(sum_max)

Submission status: Accepted

Solution code:
import heapq


def main():
    N, K = map(int, input().split())
    V = list(map(int, input().split()))
    if N <= K:
        V.sort()
        total = sum(V)
        ans = max(total, 0)
        for i in range(min(K-N, N)):
            total -= V[i]
            ans = max(ans, total)
        print(ans)
    else:
        left = [0] * (K+1)
        right = [0] * (K+1)
        for i in range(K, 0, -1):
            lv = V[:i]
            rv = V[-i:]
            left[i] = sum(lv)
            right[i] = sum(rv)
            lheap = list(lv)
            rheap = list(rv)
            heapq.heapify(lheap)
            heapq.heapify(rheap)
            lmsum = 0
            rmsum = 0
            for j in range(1, i):
                if i+j > K:
                    continue
                lmsum += heapq.heappop(lheap)
                left[i+j] = max(left[i+j], left[i] - lmsum)
                rmsum += heapq.heappop(rheap)
                right[i+j] = max(right[i+j], right[i] - rmsum)
        for i in range(1, K+1):
            left[i] = max(left[i], left[i-1])
            right[i] = max(right[i], right[i-1])
        ans = 0
        for i in range(K+1):
            ans = max(max(left[i], 0) + max(right[K-i], 0), ans)
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math, string, itertools, fractions, heapq, collections, re, array, bisect, copy, functools, random
import sys
from collections import deque, defaultdict, Counter; from heapq import heappush, heappop
from itertools import permutations, combinations, product, accumulate, groupby
from bisect import bisect_left, bisect_right, insort_left, insort_right
from operator import itemgetter as ig
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20; INF = float("INF"); ans = 0; tmp = 0; ansli = []; tmpli = []; candili = []
eps = 1.0 / 10 ** 10; mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]; ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)]; ddn9 = ddn + [(0, 0)]
"""for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:"""
def wi(): return list(map(int, sys.stdin.readline().split()))
def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]#WideIntPoint
def ws(): return sys.stdin.readline().split()
def i(): return int(sys.stdin.readline())
def s(): return input()
def hi(n): return [i() for _ in range(n)]
def hs(n): return [s() for _ in range(n)]#HeightString
def mi(n): return [wi() for _ in range(n)]#MatrixInt
def mip(n): return [wip() for _ in range(n)]
def ms(n): return [ws() for _ in range(n)]

n, k = wi()
v = wi()
v = deque(v)
pq = []
po = 0
cnt = 0
qwerty = min(n + 1, k + 1)
for i in range(qwerty):
    if i != 0:
        heappush(pq, v[i - 1])
    for j in range(qwerty - i):
        if j != 0:
            heappush(pq, v[-j])
        while k - i - j - cnt > 0:
            if pq != []:
                po = 0
                po = heappop(pq)
                if po < 0:
                    cnt += 1
                    tmpli.append(po)
                else:
                    heappush(pq, po)
                    cnt = 0
                    break
            else:
                break
        cnt = 0
        ans = max(ans, sum(pq))
        for bb in tmpli:
            heappush(pq, bb)
        tmpli = []
    pq = []
    for g in range(i + 1):
        if g != 0:
            heappush(pq, v[g - 1])

print(ans)

Submission status: Accepted

Solution code:
import heapq


def main():
    N, K = map(int, input().split())
    V = list(map(int, input().split()))
    if N <= K:
        V.sort()
        total = sum(V)
        ans = max(total, 0)
        for i in range(min(K-N, N)):
            total -= V[i]
            ans = max(ans, total)
        print(ans)
    else:
        left = [0] * (K+1)
        right = [0] * (K+1)
        for i in range(K, 0, -1):
            lv = V[:i]
            rv = V[-i:]
            left[i] = sum(lv)
            right[i] = sum(rv)
            lheap = list(lv)
            rheap = list(rv)
            heapq.heapify(lheap)
            heapq.heapify(rheap)
            lmsum = 0
            rmsum = 0
            for j in range(1, i):
                if i+j > K:
                    continue
                lmsum += heapq.heappop(lheap)
                left[i+j] = max(left[i+j], left[i] - lmsum)
                rmsum += heapq.heappop(rheap)
                right[i+j] = max(right[i+j], right[i] - rmsum)
        for i in range(1, K):
            left[i] = max(left[i], left[i-1])
            right[i] = max(right[i], right[i-1])
        ans = 0
        for i in range(K+1):
            ans = max(max(left[i], 0) + max(right[K-i], 0), ans)
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
d=list(map(int,input().split()))
ans=0
for l in range(min(n,k)+1):
    for r in range(min(n-l,k-l)+1):
        tl=d[:l]+d[-r:] if r>0 else d[:l]
        tk=k-l-r
        s=0
        for t in sorted(tl):
            if t<0 and tk>0:
                s+=-t
                tk-=1
            ans=max(ans,sum(tl)+s)
print(ans)

Submission status: Accepted

Solution code:
# まず取り出しきっちゃってから捨てる
# 左右からいくつずつ取り出すか

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

max_value = 0 # 何もとらない

for L in range(N+1):
  for R in range(N+1):
    if L+R > K:
      break
    if L+R > N:
      break
    #get = V[:L] + V[-R:]
    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(L,R,rest,get,value)
      
      
   
print(max_value)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
V=list(map(int,input().split()))
total = 0
if N<=K:
  for i in range(N):
    if V[i] > 0:
      total += V[i]
  print(total)
else:
  max = 0
  for L in range(K+1):
    for R in range(K-L+1):
#      print(L,R)
      p = K-L-R
      V0 = []
      if L>0:
        V0 = V0 + V[0:L]
#        print(V[0:L])
      if R>0:
        V0 = V0 + V[N-R:N]
#        print(V[N-R:N])
      V0.sort()
#      print(V0)
      for ii in range(len(V0)):
        if p <= 0:
            break
        if V0[ii] < 0:
          V0[ii] = 0
          p -= 1
        else:
          break
#      print(V0)
      su = sum(V0)
#      print(su)
      if max < su:
        max = su
  print(max)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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

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

        ans = max(ans, sumOut)

print(ans)

Submission status: Accepted

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

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

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

print(s)

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

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


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

lri_list = func(K)

result = 0
for l,r,i in lri_list:
#     print(l,r,i)
    if r>0:
        tmp_v = v_list[:l] + v_list[-r:]
    else:
        tmp_v = v_list[:l]
#     print(tmp_v)
    tmp_v = sorted(tmp_v)
#     print(tmp_v)
    
    tmp_sum = sum(tmp_v)
    
    for v in tmp_v:
        if i<=0:
            break
        if v<0:
            tmp_sum += -v
            i -= 1
    if result < tmp_sum:
        result = tmp_sum
#     print(tmp_sum)
print(result)

Submission status: Accepted

Solution code:
from sys import stdin

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

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

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

#for i in range(k+1):
#  print(l[i])

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

print(ans)

Submission status: Accepted

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

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

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

    print(maximum)


main()

Submission status: Accepted

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

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

Submission status: Accepted

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


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

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

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

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

print(ans)

Submission status: Accepted

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

ans = 0

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

Submission status: Accepted

Solution code:
N,K = list(map(int,input().split(" ")))
Vs = list(map(int,input().split(" ")))
rev = Vs[::-1]
ans = -(10e15)
for b in range(K+1):
    lr = min(K - b,N)
    for l in range(lr + 1):
        rlim = min(lr - l,N)
        for r in range(rlim+1):
            temoti = []
            temoti.extend(Vs[:l])
            temoti.extend(rev[:r])
            temoti.sort()
            tempans = sum(temoti)
            toridasi = 0
            for num in temoti:
                if toridasi == b: #上限回数取り出してたら終わり
                    break
                if num < 0:
                    tempans -= num
                    toridasi += 1
                else:
                    break

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

Submission status: Accepted

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

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

ans = 0

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

print(ans)

Submission status: Accepted

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

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

print(ans)

Submission status: Accepted

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

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

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

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

print(ans)

Submission status: Accepted

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