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 sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
# INF =  float("inf")
INF = 10**18
import bisect
import statistics
mod = 10**9+7
# mod = 998244353

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

m = 0
for i in range(1, K+1):
    if i <= N:
        for j in range(1,i+1):
            VV = deque(copy.deepcopy(V))
            a = []
            heapq.heapify(a)
            for k in range(j):
                v = VV.popleft()
                heapq.heappush(a,v)
            for k in range(i-j):
                v = VV.pop()
                heapq.heappush(a, v)
            ans = sum(a)
            for k in range(K-i):
                if len(a) > 0:
                    v = heapq.heappop(a)
                    if v < 0:
                        ans -= v
            m = max(m,ans)
    else:
        ans = sum(V)
        a = copy.deepcopy(V)
        heapq.heapify(a)
        for k in range(K-N):
            if len(a) > 0:
                v = heapq.heappop(a)
                if v < 0:
                    ans -= v
        m = max(m, ans)
        break

print(m)

Submission status: Accepted

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

a=list(map(int,input().split()))
a_reverse=list(reversed(a))
b=sorted(a)
s=sum(a)

ans=[]

for i in range(k+1):
  if i>n:
    I=i-n
    for j in range(I): 
      if j<n:
        ans1=s-b[j]
    ans.append(ans1)
  elif i==n:
    ans.append(s)
  elif i==0:
    ans.append(0)
  else:
    for h in range(i+1):
      H=i-h
      c=[]
      for x in range(h):
        c.append(a[x])
      for y in range(H):
        c.append(a_reverse[y])
        
      c.sort()
      S=sum(c)
      for g in range(1,k-i+1):
        if g<=i:
          if c[g-1]<0:
            S-=c[g-1]

      ans.append(S)
      
print(max(ans))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# 問題：https://atcoder.jp/contests/abc128/tasks/abc128_d

n, k = map(int, input().strip().split())
value = list(map(int, input().strip().split()))
res = 0
for l in range(k+1):
    for r in range(k-l+1):
        if l + r > n:
            continue
        d = k - l - r
        now = 0
        s = []
        for i in range(l):
            now += value[i]
            s.append(value[i])
        for i in range(r):
            now += value[n-i-1]
            s.append(value[n-i-1])
        s.sort()
        for i in range(d):
            if i >= len(s):
                break
            if s[i] > 0:
                break
            now -= s[i]
        res = max(res, now)

print(res)

Submission status: Accepted

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

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()


def main():
	n,k=MI()
	V=LI()

	ans=0

	for a in range(min(n+1,k+1)):
		for b in range(min(n-a+1,k-a+1)):
			S=[]
			S+=V[:a]
			S+=V[n-b:]
			S.sort()
			tmp=sum(S)
			cnt=max(0,k-a-b)
			for i in range(min(a+b,cnt)):

				if S[i]<0:
					tmp-=S[i]
				else:
					break
			ans=max(ans,tmp)
	print(ans)










if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

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

for a in range(n+1):
    for b in range(n+1):
        if a+b>n:
            break
        if a+b>k:
            break
        if a+b==n:
            val=sum(v)
            ans=max(ans,val)
            # print(a,b,val)
            continue
        tmp=v[:a]+v[::-1][:b]
        val=sum(tmp)
        c=k-a-b
        tmp.sort()
        for i in range(min(c,a+b)):
            if tmp[i]<0:
                val-=tmp[i]
            else:
                break
        ans=max(ans,val)
        # print(a,b,val)
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

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

for a in range(n+1):
    for b in range(n+1):
        if a+b>n:
            break
        if a+b>k:
            break
        if a+b==n:
            val=sum(v)
            ans=max(ans,val)
            # print(a,b,val)
            continue
        tmp=v[:a]+v[::-1][:b]
        val=sum(tmp)
        c=k-a-b
        tmp.sort()
        for i in range(min(c,a+b)):
            if tmp[i]<0:
                val-=tmp[i]
            else:
                break
        ans=max(ans,val)
        # print(a,b,val)
print(ans)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
V=list(map(int,input().split()))
r,ans=min(N,K),0
for a in range(r+1):
  for b in range(r-a+1):
    tmp,minus=0,[]
    for i in range(a):
      tmp+=V[i]
      if V[i]<0:
        minus.append(V[i])
    for j in range(b):
      tmp+=V[N-j-1]
      if V[N-j-1]<0:
        minus.append(V[N-j-1])
    tmp-=sum(sorted(minus)[:K-(a+b)])
    ans=max(ans,tmp)
print(ans)

Submission status: Accepted

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

ans = 0

for a in range(K + 1):
    for b in range(K - a + 1):

        # a+b>Nとなるような操作は実現不可能
        if a + b > N:
            continue

        # 左からa個、右からb個取り出す
        get = []
        get += V[:a]
        get += list(reversed(V))[:b]
        # (a+b)回操作した時点でのスコア
        tmp = sum(get)

        # まだ操作出来るなら、負の数を取り除く
        get.sort()
        for i in range(min(K - a - b, len(get))):
            if get[i] < 0:
                tmp += -get[i]
        ans = max(ans, tmp)

print(ans)

Submission status: Accepted

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

ans = 0

for a in range(K + 1):
    for b in range(K - a + 1):
        if a + b > N:
            continue
        # 左からa個、右からb個取り出す
        get = []
        get += V[:a]
        get += list(reversed(V))[:b]
        # (a+b)回操作した時点でのスコア
        tmp = sum(get)

        # まだ操作出来るなら、負の数を取り除く
        get.sort()
        for i in range(min(K - a - b, len(get))):
            if get[i] < 0:
                tmp += -get[i]
        ans = max(ans, tmp)

print(ans)

Submission status: Accepted

Solution code:
N, K, *V = map(int, open(0).read().split())

# i: 操作回数
# j: 取り出す個数
# k: 左から取り出す範囲 [0, k)
ans = 0
for i in range(K + 1):
    for j in range(min(N + 1, i + 1)):
        for k in range(j + 1):
            right = N - j + k
            tmp = V[:k] + V[right:]
            tmp.sort()
            ans = max(ans, sum(tmp) - sum([t for t in tmp if t < 0][: i - j]))
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappop, heapify


N, K, *V = map(int, open(0).read().split())

# i: 操作回数
# j: 取り出す個数
# k: 左から取り出す範囲 [0, k)
ans = 0
for i in range(K + 1):
    for j in range(min(N + 1, i + 1)):
        for k in range(j + 1):
            right = N - j + k
            tmp = V[:k] + V[right:]

            put_out_cnt = i - j
            heapify(tmp)
            while tmp and put_out_cnt > 0:
                heappop(tmp)
                put_out_cnt -= 1
            ans = max(ans, sum(tmp))
print(ans)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
V = list(map(int,input().split()))
#print(V)
max_v = 0
have_minus = []
for left in range(N):
  for right in range(left,N + 1)[::-1]:
    if len(V[:left]) + len(V[right:]) > K: 
      break
    #print (V[:left], V[right:])
    sum_ = sum(V[:left]) + sum(V[right:])
    have_minus = [num for num in V[:left]+V[right:] if num < 0]
    have_minus.sort()
    #print (f"have_minus={have_minus}" )
    d = max(0,K - (len(V[:left]) + len(V[right:])))
    for i in range(min(d, len(have_minus))):
        sum_ -= have_minus[i]   
    #print (f"sum_ = {sum_}")    
    
    max_v = max(max_v ,sum_)
print(max_v)

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):
        tmp,minus=0,[]
        for i in range(a):
            t=V[i]
            tmp+=t
            if t<0:
                minus.append(t)
        for j in range(b):
            t=V[N-1-j]
            tmp+=t
            if t<0:
                minus.append(t)
        tmp-=sum(sorted(minus)[:K-(a+b)])
        ans=max(ans,tmp)
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,k = inpl()
a = inpl()
res = 0
for ope in range(k+1):
    for pick in range(ope+1):
        if pick > n: continue
        back = ope - pick
        for lp in range(pick+1):
            rp = pick - lp
            # print(ope,back,lp,rp)
            q = []
            for i in range(lp):
                q.append(a[i])
            for i in range(rp):
                q.append(a[-i-1])
            q.sort()
            ans = sum(q)
            res = max(res,ans)
            for i in range(back):
                if i >= pick: break
                ans -= q[i]
                res = max(res,ans)
print(res)

Submission status: Accepted

Solution code:
from bisect import bisect_left
N,K = map(int,input().split())
V = list(map(int,input().split()))
vmax = -10**9
for n in range(min(N,K)+1):
    A = V[:n]
    for m in range(min(N,K)-n+1):
        B = V[N-m:]
        B = B+A
        B = sorted(B)
        ind = bisect_left(B,0)
        k = min(ind,K-n-m)
        v = sum(B[k:])
        vmax = max(vmax,v)
print(vmax)

Submission status: Accepted

Solution code:
n, k, *a = map(int, open(0).read().split())

ans = 0
for l in range(0, k + 1):
    for r in range(0, k + 1 - l):
        if l == r == 0 or l + r > n:
            continue
        b = sorted(a[:l] + a[n - r:])
        c = min(k - l - r, len(b) - 1)
        ans = max(ans, sum(b[c:] if b[c] < 0 else filter(lambda x: x > 0, b)))
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(0, k + 1):
    for r in range(0, k + 1 - l):
        if l == r == 0 or l + r > n:
            continue
        a = sorted(v[:l] + v[n - r:])
        m = min(k - l - r, len(a) - 1)
        ans = max(ans, sum(a[m:] if a[m] <
                           0 else filter(lambda x: x > 0, a)))
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):
    for r in range(n+1)[::-1]:
        if l <= r and 0 <= (l+n-r) <= k: # l+n-r個拾う
            q = v[:l] + v[r:n]
            q.sort(reverse = True)
            
            for i in range(k-(l+n-r)):
                if q == []:
                    break
                if q[-1] < 0:
                    q.pop()
                else:
                    break

            ans = max(ans, sum(q))
        else:
            continue

print(ans)

Submission status: Accepted

Solution code:
import sys
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり

N,K = MI()
V = LI()

ans = 0
for i in range(K+1):  # 操作回数
    for j in range(N+1):  # 左から取る個数
        for k in range(N+1):  # 右から取る個数
            if j + k > min(N,i):
                break
            l = i-j-k  # 戻す個数
            if l > j+k:
                continue
            A = [V[m] for m in range(j)] + [V[N-1-m] for m in range(k)]
            A.sort(reverse=True)
            ans = max(ans,sum(A[m] for m in range(j+k-l)))
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(n + 1):
    for right in range(n + 1):
        if left == 0 and right == 0:
            continue
        rest = k - left - right
        if left + right > n or rest < 0:
            break
        arr = v[:left] + v[n - right:]
        minus = 0
        neg = [x for x in arr if x < 0]
        if len(neg) > 0:
            neg.sort()
            minus = sum(neg[:rest])
        ans = max(ans, sum(arr) - minus)

print(ans)

Submission status: Accepted

Solution code:
import sys

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

ans = 0

for i in range(N+1):
    if K < i:
        continue
    score = sum(V[0:i])
    # print("i", i, "l score", score)
    ans = max(ans, score)
    for j in range(N+1):
        if N < i + j or K < i + j:
            continue
        tmp = score
        tmp += sum(V[N-j:])
        ans = max(ans, tmp)
        # print("i", i, "j", j, "lr score", tmp)

        # 捨てる最大個数
        k = K - i - j
        if k < 0:
            continue
        negs = []
        for n in range(0, i):
            if V[n] < 0:
                negs.append(V[n])
        for n in range(N-j, N):
            if V[n] < 0:
                negs.append(V[n])
        negs.sort()
        # print(negs)
        tmp -= sum(negs[:k])
        ans = max(ans, tmp)
        # print("i", i, "j", j, "k", k, "lrd score", tmp)

print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left
N,K = map(int,input().split())
V = list(map(int,input().split()))
vmax = -10**9
for n in range(min(N,K)+1):
    A = V[:n]
    for m in range(min(N,K)-n+1):
        B = V[N-m:]
        B = sorted(A+B)
        ind = bisect_left(B,0)
        k = min(K-m-n,ind)
        cnt = sum(B[k:])
        vmax = max(vmax,cnt)
print(vmax)

Submission status: Accepted

Solution code:
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 + 1 - l):
        if l + r > n:
            continue
        suteru = k - l - r
        get = []
        for i in range(l):
            get.append(v[i])
        for i in range(n - 1, n - 1 - r, -1):
            get.append(v[i])
        get.sort()
        minus = 0
        while minus < min(suteru, len(get)) and get[minus] < 0:
            minus += 1
        ans = max(ans, sum(get[minus:]))
print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし

N,K = MI()
V = LI()

ans = 0
for i in range(K+1):  # 操作回数
    for j in range(N+1):  # 左から
        for k in range(N+1):  # 右から
            if j + k > min(N,i):
                break
            l = i-j-k
            if l > j+k:
                continue
            A = [V[m] for m in range(j)] + [V[N-1-m] for m in range(k)]
            A.sort(reverse=True)
            ans = max(ans,sum(A[m] for m in range(j+k-l)))
print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
v=list(map(int,input().split()))
finans=0
for l in range(n+1):
  for r in range(n-l+1):
    if l+r>k:
      continue
    ans=[]
    for i in range(l):
      ans.append(v[i])
    for i in range(n-1,n-r-1,-1):
      ans.append(v[i])
    ans.sort()
    i=-1
    for i in range(min(len(ans),k-(r+l))):
      if ans[i]>0:
        i-=1
        break
    ans1=0
    for j in range(i+1,len(ans)):
      ans1+=ans[j]
    finans=max(finans,ans1)
print(finans)

Submission status: Accepted

Solution code:
import copy
from collections import deque
N,K = map(int,input().split())
A = list(map(int,input().split()))
ans = 0
for k in range(K+1): #0-K
  for left in range(N+1): #0-N
    for right in range(N-left+1):
      push = k - (left + right)
      if push < 0 or push > left+right:
        continue
      Acopy = copy.copy(A)
      Acopy = deque(Acopy)
      B = []
      for t in range(left):
        temp = Acopy.popleft()
        B.append(temp)
      for t in range(right):
        #print(left,right)
        temp = Acopy.pop()
        B.append(temp)
      B.sort()
      wa = sum(B)-sum(B[:push])
      ans = max(ans,wa)
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 > N or l+r > K: break
        arr = V[:l]
        if r: arr += V[-r:]
        arr.sort()
        rem = K - l - r
        tmp = 0
        for a in arr:
            if a < 0 and rem:
                rem -= 1
            else:
                tmp += a
        ans = max(ans, tmp)
print(ans)

Submission status: Accepted

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

ans = 0
ab_max = min(n,k)
for l in range(ab_max+1):
    for r in range(ab_max+1):
        if l+r > k: continue
        if l > n-r: continue
        ls = vl[:l]
        rs = vl[n-r:]
        # print(ls,rs)
        vals = ls + rs
        rem = k-(l+r)
        # print(rem)
        vals.sort()
        curr_sum = sum(vals)
        for i in range(rem):
            if i >= len(vals): break
            if vals[i] < 0: curr_sum -= vals[i]
            else: break
        # print(curr_sum)
        ans = max(ans,curr_sum)

print(ans)

Submission status: Accepted

Solution code:
import random

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

if K==0:
    print(0)
    exit()

if 0:
    V=[random.randint(-10**7,10**7) for i in range(N)]

ans=-float("inf")

for i in range(N+1):
    for j in range(N-i+1):
        if i+j>K:
            continue
        tmp=[V[k] for k in range(i)]
        for k in range(j):
            tmp.append(V[-1-k])
        tmp.sort()
        rest=K-i-j
        minus=0
        base=sum(tmp)
        for k in range(min(rest,len(tmp))):
            if tmp[k]<0:
                minus+=tmp[k]
            else:
                break
        test=base-minus
        ans=max(ans,test)

print(ans)

Submission status: Accepted

Solution code:
from itertools import*
n,k=map(int,input().split())
v=list(map(int,input().split()))
ans=0
for i in range(k+1):
  if i>n:break
  for j in range(i+1):
    c=0
    d=sorted(v[:j]+v[n-i+j:])
    l=k-len(d)
    for m in d:
      if m<0 and l:
        l-=1
        continue
      c+=m
    ans=max(ans,c)
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(min(n, k) + 1):
    for r in range(min(n, k) - l + 1):
        bag = sorted(v[:l] + v[n - r:])
        minus = sum(vi for vi in bag[:k - l - r] if vi < 0)
        ans = max(ans, sum(bag) - minus)
print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate

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

ans = 0
for l in range(min(n, k) + 1):
    for r in range(min(n, k) - l + 1):
        bag = sorted(v[:l] + v[n - r:])
        minus = sum(vi for vi in bag[:k - l - r] if vi < 0)
        ans = max(ans, sum(bag) - minus)
print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate

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

ans = 0
acc = [0] + list(accumulate(v))
for l in range(min(n, k) + 1):
    for r in range(min(n, k) - l + 1):
        minus = sorted(v[:l] + v[n - r:])
        bag = acc[l] - acc[0] + acc[n] - acc[n - r]
        bag -= sum(vi for vi in minus[:k - l - r] if vi < 0)
        ans = max(ans, bag)
print(ans)

Submission status: Accepted

Solution code:
import bisect, copy, heapq, math, sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
def celi(a,b):
    return -(-a//b)
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

ans=0
for i in range(k+1):
    toru=i
    ireru=k-i
    # print(toru)
    for j in range(toru+1):
        l,r=j,n-(toru-j)
        if l>r:
            lst=v[:]
        else:
            lst=v[:l]+v[r:]
        # print(lst)
        lst.sort(reverse=True)
        for l in range(ireru):
            if lst and lst[-1]<0:
                lst.pop()
        ans=max(ans,sum(lst))

print(ans)

Submission status: Accepted

Solution code:

"""
まず貪欲的なアルゴリズムを組めるか考えてみる。
所持している宝石のうち、価値が負であるものはできるだけ、筒に入れたい。できれば価値の低い順に。
所持している宝石のうち、価値が0以上であるものは、筒に入れる意味がない。
筒にある宝石のうち、価値が正のものはできるだけ取り出したい。できれば価値の高い順に。

ここまで考えると、宝石を筒に入れる作業は最後にやればよいことがわかる。
むしろ最後に寄せないと、筒の中に残っている価値の高い宝石を取り出すときに、入れた宝石が邪魔になる。
また、最後に行うため、左から入れるか右から入れるかは関係ない。
あと入れる宝石は任意で選べるため、負の宝石のうち、価値の低いものを順番に入れれば良い。

ここまでくると、愚直にシミュレートすれば良いことがわかる。
取り出す作業をA回やる、と決める。O(min(N,K))
    左からL回、右からR(=A-L)回取り出すと決める。O(min(N,K))
        P = V[:L]+V[::-1][:R] とする。（Pは取り出した宝石の価値の配列）。
        P.sort()で価値が低い順に並べて、左から価値が負のものをK-A個まで捨てる。O(NlogN)

計算量としてはO(min(N,K)**2*NlogN)で十分高速
"""

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

ans = 0
for A in range(min(N,K)+1):
    for L in range(A+1):
        R = A-L
        P = V[:L]+V[::-1][:R]
        P.sort()
        for i in range(min(K-A,A)):
            if P[i] < 0:
                P[i]=0
        ans = max(ans,sum(P))
print(ans)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
V=list(map(int,input().split()))
import heapq
turn=min(N,K)
m=0
for A in range(turn+1):
  for B in range(turn+1-A):
    h=[]
    heapq.heapify(h)
    if A>0:
      h=V[:A]+h
    if B>0:
      h=h+V[len(V)-B:]
    heapq.heapify(h)  

    ans=sum(h)
    for i in range(K-A-B):
      if h!=[]:
        f=heapq.heappop(h)
 
        if f<0:
          ans-=f
    m=max(ans,m)


    
print(m)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools, bisect
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def SL(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]

def perm(n, r): return math.factorial(n) // math.factorial(r)
def comb(n, r): return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

sys.setrecursionlimit(1000000)
dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
MOD = 1000000007
INF = float("inf")

def main():
    N, K = LI()
    V = LI()
    V2 = V + V

    ans = 0
    for k in range(1, min(K + 1, N + 1)):
        for i in range(len(V) - k, len(V) + 1):
            neg = []
            tmp = 0
            for vi in V2[i:i + k]:
                if vi < 0:
                    neg.append(vi)
                tmp += vi
            tmp -= sum(sorted(neg)[:K - k])
            ans = max(ans, tmp)

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

    for a in range(max(1, k+1)):  # 左から取る個数
        for b in range(max(1, k-a+1)):  # 右から取る個数
            if a+b > n: break
            arr = []
            if a > 0: arr += v[:a]
            if b > 0 and a < n: arr += v[max(a, 0, n-b):]
            arr.sort()
            for j in range(max(1, a+b)):  # 戻す個数
                if a+b+j > k: break
                score = sum(arr[j:])
                ans = max(ans, score)
                #print(a, b, j, score, arr)
    print(ans)

if __name__ == '__main__':
    abc128_d()

Submission status: Accepted

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N,K=MI()
    V=LI()
    
    ans=0
    import heapq
    
    #左からa個，右からb個とって，あまり分で負数を捨てる
    for a in range(K+1):
        for b in range(K+1):
            if a+b>min(K,N):
                break
            hq=[]
            heapq.heapify(hq)
            for i in range(a):
                heapq.heappush(hq,V[i])
            for j in range(b):
                heapq.heappush(hq,V[N-1-j])
                
            temp=0
            rem=K-(a+b)
            for i in range(a+b):
                v=heapq.heappop(hq)
                if v>=0:
                    temp+=v
                else:
                    if rem>0:
                        rem-=1
                    else:
                        temp+=v
                        
            ans=max(ans,temp)
            
    print(ans)
                
            

main()

Submission status: Accepted

Solution code:
import sys
import heapq
def input(): return sys.stdin.readline().rstrip()

def main():
    n, k = map(int, input().split())
    v = list(map(int, input().split()))
    ans = 0
    for i in range(n):
        for j in range(i, n):
            h=[0]
            heapq.heapify(h)
            count = 0
            for p in range(i-1):
                heapq.heappush(h, v[p])
                count += 1
            for m in range(j+1, n):
                heapq.heappush(h, v[m])
                count += 1
            while h[0] < 0 and count < k:
                t = heapq.heappop(h)
                count += 1
            if count <= k:
                ans = max(ans,sum(h))
    counts = n
    heapq.heapify(v)
    while h[0] < 0 and counts < k:
        t = heapq.heappop(v)
        counts += 1
    if counts <= k:
        ans = max(ans,sum(v))
    print(ans)
   
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,K =map(int, input().split())
V=list(map(int, input().split()))
res=0
for l in range(K+1):
    for r in range(K+1-l):
        if l+r>N: continue
        t=V[:l]+V[N-r:]
        t.sort()
        S=sum(t)
        for c in range(min(K-l-r,l+r)):
            if t[c]<0:
                S-=t[c]
        res=max(res,S)
print(res)

Submission status: Accepted

Solution code:
def max2(x,y):
    return x if x > y else y
def min2(x,y):
    return x if x < y else y

N, K = map(int, input().split())
V = list(map(int, input().split()))
res = 0
for l in range(K+1):
    for r in range(K+1-l):
        if l+r>N:
            continue
        temp=V[:l]+V[N-r:]
        temp.sort()
        S = sum(temp)
        for cnt in range(min2(K-l-r,l+r)):
            if temp[cnt]<0:
                S -= temp[cnt]
            else:
                break
        res = max2(res, S)
print(res)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
from random import randint
from time import time

class PriorityQueue(object):
    def __init__(self):
        self.queue = []
    def push(self, value):
        heappush(self.queue, value)
    def pop(self):
        return heappop(self.queue)
    def __len__(self):
        return len(self.queue)
    def __contains__(self, item):
        return item in self.queue

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

ans = 0

#取得する操作を何回行うか？
for i in range(0,m+1):

	#操作残り回数
	lef = m-i

	hp = PriorityQueue()
	#左側からどれだけ取るか？
	for j in range(0,i+1):
		if j>n :
			break

		#左側からj個取る
		for k in range(0,j):
			hp.push(v[k])

		#右側から i-j個取る
		for k in range(0,i-j):
			if n-1-k < j:
				break
			hp.push(v[n-1-k])

		#minusは戻す
		for k in range(0,lef):
			if len(hp) == 0:
				break
			top = hp.pop()
			if top>=0 :
				hp.push(top)
				break

		ss = 0
		while len(hp)>0:
			ss += hp.pop()

		ans = max(ans,ss)

print(ans)

Submission status: Accepted

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

ans = -10**9
for back in range(n+1):
    for left in range(min(k-back+1, n+1)):
        for right in range(min(k-back-left+1, n-left+1)):
            hand = []
            hand.extend(v[:left])
            if right>0:
                hand.extend(v[-right:])
            hand.sort()
            ans = max(ans, sum(hand[back:]))

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 i in range(m+1): #A
  for j in range(m+1-i): #B
    l=[]
    l=l+v[0:i]+v[n-j:n]
    l.sort()
    for kk in range(min(k-i-j, i+j)):
      if l[kk]<0:
        l[kk]=0
    ans=max(ans, sum(l))
print(ans)