Problem:


Score : 400 points

Problem Statement

Your friend gave you a dequeue D as a birthday present.

D is a horizontal cylinder that contains a row of N jewels.

The values of the jewels are V_1, V_2, ..., V_N from left to right. There may be jewels with negative values.

In the beginning, you have no jewel in your hands.

You can perform at most K operations on D, chosen from the following, at most K times (possibly zero):

Operation A: Take out the leftmost jewel contained in D and have it in your hand. You cannot do this operation when D is empty.

Operation B: Take out the rightmost jewel contained in D and have it in your hand. You cannot do this operation when D is empty.

Operation C: Choose a jewel in your hands and insert it to the left end of D. You cannot do this operation when you have no jewel in your hand.

Operation D: Choose a jewel in your hands and insert it to the right end of D. You cannot do this operation when you have no jewel in your hand.

Find the maximum possible sum of the values of jewels in your hands after the operations.

Constraints

All values in input are integers.

1 \leq N \leq 50

1 \leq K \leq 100

-10^7 \leq V_i \leq 10^7

Input

Input is given from Standard Input in the following format:

N K
V_1 V_2 ... V_N

Output

Print the maximum possible sum of the values of jewels in your hands after the operations.

Sample Input 1

6 4
-10 8 2 1 2 6

Sample Output 1

14

After the following sequence of operations, you have two jewels of values 8 and 6 in your hands for a total of 14, which is the maximum result.

Do operation A. You take out the jewel of value -10 from the left end of D.

Do operation B. You take out the jewel of value 6 from the right end of D.

Do operation A. You take out the jewel of value 8 from the left end of D.

Do operation D. You insert the jewel of value -10 to the right end of D.

Sample Input 2

6 4
-6 -100 50 -2 -5 -3

Sample Output 2

44

Sample Input 3

6 3
-6 -100 50 -2 -5 -3

Sample Output 3

0

It is optimal to do no operation.



Sample input:
6 4
-10 8 2 1 2 6


Sample output:
14

Submission status: Accepted

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

ans=-10**9
for l in range(min(N,K)+1):
    for r in range(max(1,min(N,K)+1-l)):
        for d in range(max(1,K+1-l-r)):
            h=V[:l]
            heapq.heapify(h)
            for i in range(r): heapq.heappush(h, V[-1-i])
            for i in range(min(d,len(h))): heapq.heappop(h)
            ans=max(ans,sum(h))
print(ans)

Submission status: Accepted

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

ans = 0
have = []
val = 0

for l in range(0, min(k, n) + 1):
    if l > 0:
        have = V[0 : l]
        have.sort()
        val = sum(V[0 : l])

    for r in range(0, min(k - l, n - l) + 1):
        if r > 0:
            have.append(V[-r])
            have.sort()
            val += V[-r]

        d = 0
        t_val = val
        while d < min(l + r, k - l - r):
            if have[d] > 0: break
            t_val -= have[d]
            d += 1  # 戻す

        ans = max(ans, t_val)

print(ans)

Submission status: Accepted

Solution code:
N,K = map(int, input().split())
d = list(map(int, input().split()))
ans = 0
for le in range(min([K+1,N+1])):
    for ri in range(min([K-le+1,N+1])):
        if (le+ri)>K: break
        if (le+ri)>=N:
            cur = d
        else:
            cur = (d[0:le] + d[(N-ri):] if le!=0 else d[(N-ri):])
        t = K - le - ri
        for ti in range(t):
            if not cur: break
            mi = min(cur)
            if mi>0: break
            cur.remove(mi)
        ans = max(ans, sum(cur))
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import deque
import heapq

N, K=map(int, input().split())
V=list(map(int, input().split()))
lim=min(N, K)
ans=0
for num in range(lim+1):
    for A in range(num+1):
        B=num-A
        d=deque(V)
        hands=[]
        while d and len(hands)<A:
            hands.append(d.popleft())
        while d and len(hands)<A+B:
            hands.append(d.pop())
        heapq.heapify(hands)
        cnt=K-num
        while len(hands) and hands[0]<0 and cnt>0:
            cnt-=1
            heapq.heappop(hands)
        ans=max(ans, sum(hands))
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):
    Mr = N + 1 if l != 0 else N
    for r in range(N - min(N, K) + l, Mr):
        lst = sorted(V[:l] + V[r:], reverse=True)
        s_lst = sum(lst)
        x = lst[-1]
        for _ in range(min(l + N - r, K - (l + N - r))):
            x = lst.pop()
            if x >= 0:
                break
            s_lst -= x
        ans = max(ans, s_lst)
print(ans)

Submission status: Accepted

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

ans = -1e9
for leftops in range(min(N,K)+1):
  for rightops in range(min(N,K)-leftops+1):
    X = V[:leftops] if leftops > 0 else []
    X = X + V[-rightops:] if rightops > 0 else X
    work = sum(X)
    #print(leftops,rightops,work)
    #print(X)
    X.sort()
    
    if len(X) == 0:
      ans = max(ans,0)
      continue
      
    for k in range(min(K-leftops-rightops,len(X))):
      if X[k] < 0:
        work -= X[k]
      else:
        break
    ans = max(ans,work)
    
print(ans)

Submission status: Accepted

Solution code:
import heapq
from collections import deque

N, K=map(int, input().split())
V=list(map(int, input().split()))
limitAB=min(N, K)
ans=0
for num in range(limitAB+1):
  for A in range(num+1):
    B=num-A
    d=deque(V)
    h=[]
    while d and len(h)<A:
      heapq.heappush(h, d.popleft())
    while d and len(h)<A+B:
      heapq.heappush(h, d.pop())
    cnt=0
    while h and h[0]<0 and cnt<K-(A+B):
      heapq.heappop(h)
      cnt+=1
    ans=max(ans, sum(h))
print(ans)

Submission status: Accepted

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

ans = 0
for i in range(min(N+1,K+1)):
  que1 = V[:i]
  for j in range(min(N+1-i,K+1-i)):
    que2 = que1 + V[N-j:]
    que2.sort()
    for k in range(min(K+1-i-j,i+j+1)):
      ans = max(ans,sum(que2[k:]))
print(ans)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
V=list(map(int,input().split()))
Vrev=V[::-1]
# 左からA個取る
# 右からB個取る
# A+B<=min(N,K)
# K-(A+B)個詰め直す。負の数で絶対値の大きいものから順に。

# A,Bを、0からA+B=min(N,K)まで全探索
MAX=min(N,K)
ans=0
for a in range(MAX+1):
  for b in range(MAX-a+1):
    jewels=V[:a]+Vrev[:b]
    jewels=sorted(jewels)
    drop=K-(a+b)
    for i in range(drop):
      if i>=len(jewels):
        break
      if jewels[i]>=0:
        break
      else:
        jewels[i]=0
    if ans<sum(jewels):
      ans=sum(jewels)
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify

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

W = V[::-1]

patterns = []

for i in range(1, N+1): # 何個取り出すパターンなのか

  for left in range(i+1): # 左側から何個抽出するのか
    right = i - left
    heap = V[:left] + W[:right]
    heapify(heap)
    patterns.append(heap)

  
ans = 0

for pattern in patterns:
  length = len(pattern)
  subable = K - length

  if subable < 0:
    continue
  
  while subable > 0 and pattern:
    useless = heappop(pattern)
    subable -= 1
    if useless > 0:
      heappush(pattern, useless)
      ans = max(ans, sum(pattern))
      break
  else:
    ans = max(ans, sum(pattern))

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

VALUES = []
for l in range(k + 1):
    for r in range(k - l + 1):
        if l + r > n:
            continue
        JEWELS = D[:l] + D[n - r:]
        JEWELS.sort()
        
        back = k - (l + r)
        for _ in range(back):
            if not JEWELS:
                break
            if JEWELS[0] >= 0:
                break
            JEWELS.pop(0)
        
        VALUES.append(sum(JEWELS))

print(max(VALUES))

Submission status: Accepted

Solution code:
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

        score = 0
        S = []

        for i in range(l):
            score += V[i]
            S.append(V[i])

        for i in range(r):
            score += V[-(i+1)]
            S.append(V[-(i+1)])

        d = K - l - r
        S.sort()
        for i in range(d):
            if i > len(S)-1:
                break
            if S[i] > 0:
                break
            score -= S[i]

        ans = max(ans, score)

print(ans)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
V = list(map(int,input().split()))
ans = []
for i in range(1,min(K,N)+1):
    for a in range(i+1):
        b = i-a
        AB = V[:a]
        if b > 0:
            AB += V[-b:]
        AB.sort(reverse = True)
        for j in range(K-i):
            if AB and AB[-1] < 0:
                AB.pop()
        ans.append(sum(AB))
print(max(ans))

Submission status: Accepted

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

i = 0
ans = 0

for number in range(min(n+1, k+1)):
    for i in range(number+1):
        right = n - number + i
        vv = v[:i] + v[right:]

        vv.sort()
        tmp_ans = sum(vv)
        qb = min(k - number, len(vv))
        #print(vv, qb)
        for j in range(qb):
            if vv[j] < 0:
                tmp_ans -= vv[j]
            else:
                break

        ans = max(ans, tmp_ans)

print(ans)

Submission status: Accepted

Solution code:
from _collections import deque
from _ast import Num


def parser():
    while 1:
        data = list(input().split(' '))
        for number in data:
            if len(number) > 0:
                yield (number)


input_parser = parser()


def gw():
    global input_parser
    return next(input_parser)


def gi():
    data = gw()
    return int(data)


MOD = int(1e9 + 7)

import numpy
from collections import deque
from math import sqrt
from math import floor
# https://atcoder.jp/contests/abc145/tasks/abc145_e
# E - All-you-can-eat
"""
DP1[i][j] =the maximum sum of deliciousness of dishes, which are chosen from 1st- to i-th dishes,
such that he can finish them in j minutes

still WA!!!

"""


def gcd(a, b):
    if a < b:
        return gcd(b, a)
    elif a % b:
        return gcd(b, a % b)
    else:
        return b


N = gi()
K = gi()
V = [0] * N

for i in range(N):
    V[i] = gi()


def c(l):
    free = K - len(l)
    s = 0
    for v in l:
        if v < 0 and free:
            free -= 1
        else:
            s += v
    return s


ans = -1e9
for i in range(-1, N):
    for j in range(i + 1, N + 1):
        sub = V[0:i + 1] + V[j:N]
        if len(sub) > K:
            continue
        sub.sort()
        ans = max(ans, c(sub))

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

ans = 0  # 何もしないと0なので、ansの初期値は0


# pick->取り出す操作をする回数(listより多く取り出さないように注意)
for pick in range(min(K+1, N+1)):
    # 右から取り出す数
    for right in range(pick+1):
        left = pick-right  # 左から取り出す数
        pick_list = V[:right]+V[N-left:]

        # queueに戻す操作
        pick_list = sorted(pick_list)
        tmp_ans = sum(pick_list)  # 戻す前の合計値
        rem = min(K-pick, len(pick_list))  # 戻す操作をできる回数
        for i in range(rem):  # 負の値のものをできるだけ戻す
            if pick_list[i] < 0:
                tmp_ans -= pick_list[i]
            else:
                break
        ans = max(tmp_ans, ans)
print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
v=list(map(int,input().split()))
ans=0
d=[]
for i in range(min(n+1,k+1)):
    for j in range(min(n-i+1,k-i+1)):
        d=v[:i]+v[n-j:]
        d.sort(reverse=True)
        for _ in range(k-i-j):
            if d and d[-1]<0:
                d.pop()
        ans=max(ans,sum(d))

print(ans)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
V = list(map(int,input().split()))
cmax = 0
for k in range(1,min(K,N)+1):
    for i in range(k+1):
        A = V[:i]+V[N-(k-i):]
        A = sorted(A,reverse=True)
        a = min(k,K-k)
        for j in range(a):
            if A[-1]<0:
                A.pop()
        cmax = max(cmax,sum(A))
print(cmax)

Submission status: Accepted

Solution code:
#import heapq
import copy

N,K=map(int,input().split())
V=list(map(int,input().split()))
V.append(0)#右から取る時用

S=[0]*(N+1)#累積和
for i in range(N):
    S[i+1]=S[i]+V[i]

#左からi番目まで見たときに，持っている負の宝石
left=[[] for _ in range(N+1)]
for i in range(N):
    left[i+1]=copy.deepcopy(left[i])
    if V[i]<0:
        left[i+1].append(V[i])
        left[i+1].sort()
       
        
ans=0
#左からi個，右からj個とったときについて考える
for i in range(N+1):
    temp=S[i]
    rem=copy.deepcopy(left[i])
    #heapq.heapify(rem)
    for j in range(N+1-i):
        if i+j>K:
            break
        temp+=S[-1]-S[N-j]
        if V[N-j]<0:
            #heapq.heappush(rem,V[N-j])
            rem.append(V[N-j])
            rem.sort()
        ret=K-(i+j)#負の宝石を返却できる回数
        if ret>0:
            for k in range(min(ret,len(rem))):
                temp-=rem[k]
        ans=max(ans,temp)
        temp=S[i]
        
print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
b = a[::-1]

ans = 0
for left in range(n+1):
    for right in range(n+1):
        if left + right > k or left+right > n:
            break
        operate = k - left - right
        v = a[:left] + b[:right]
        v.sort(reverse=True)
        for _ in range(operate):
            if len(v) == 0 or v[-1] >= 0:
                break
            v.pop()
        ans = max(ans, sum(v))

print(ans)

Submission status: Accepted

Solution code:
import heapq
import numpy as np
N, K = map(int,input().split())
v = list(map(int,input().split()))
res = 0
if N==1:
    print(max([0,v[0]]))
    exit()

for i in range(N):
    for j in range(N):
        if 1<=i+j<=K and i+j<=N:
            tmp = 0
            gem = []
            heapq.heapify(gem)
            for k in range(i):
                heapq.heappush(gem, v[k])
                tmp += v[k]
            for k in range(N-1,(N-1)-(j),-1):
                heapq.heappush(gem, v[k])
                tmp += v[k]
            rest = K - (i+j)
            while 1:
                if tmp != 0 and rest > 0:
                    rest -= 1
                    elem = heapq.heappop(gem)
                    if elem >= 0:
                        heapq.heappush(gem, elem)
                        break
                    tmp -= elem
                else:
                    break
            res = max([res,tmp])
print(int(res))

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
V = [int(i) for i in input().split()]
ans = 0
for pick in range(min(N+1,K+1)):
  for right in range(pick+1):
    left = pick - right
    picklist = V[:right] + V[N-left:]
    picklist = sorted(picklist)
    ans1 = sum(picklist)
    rem = min(K-pick, len(picklist))
    for i in range(rem):
      if picklist[i] < 0:
        ans1 -= picklist[i]
      else:
        break
    ans = max(ans, ans1)
print(ans)

Submission status: Accepted

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

answer = 0
for i in range(min(N + 1, K + 1)):
  for j in range(i + 1):
    left = j
    right = i - j
    
    q = []
    for k in range(left):
      q.append(V[k])
    for k in range(N - right, N):
      q.append(V[k])
    q.sort()
    
    tmp = sum(q)
    for k in range(min(K - i, len(q))):
      if q[k] < 0:
        tmp -= q[k]
      else:
        break
    answer = max(answer, tmp)
    
print(answer)

Submission status: Accepted

Solution code:
N, K=map(int, input().split())
V=list(map(int, input().split()))
NKmin=min(N, K)
out=0
for a in range(NKmin+1):
  for b in range(NKmin+1-a):
    zan=K-a-b
    if a==0 and b==0:
      continue
    elif b==0:
      tmp=V[:a]
    else:
      tmp=V[:a]+V[-b:]
    tmp.sort()
    s=sum(tmp)
    u=min(zan, len(tmp))
    for i in range(u):
      if tmp[i]<0:
        s+=-tmp[i]
      else:
        break
        
    if out<s:
      out=s
print(out)

Submission status: Accepted

Solution code:
# ABC128 D - equeue
n,k=map(int,input().split())
v=list(map(int,input().split()))
c=min(n,k)
ans=0

for a in range(c+1):
    for b in range(c-a+1):
        t=v[:a]+v[n-b:]
        t.sort()
        for i in range(k-(a+b)):
            if len(t) and t[0]<0:
                t.pop(0)
        ans=max(ans,sum(t))
print(ans)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
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 LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    N, K = LI()
    V = LI()
    in_deq = deque()
    ans = 0
    for v in V:
        in_deq.append(v)
    for toru in range(K+1):
        for left_toru in range(toru+1):
            deq = copy.copy(in_deq)
            modosu = K - toru
            temochi = []
            right_toru = toru - left_toru
            # print('left_toru: {}, right_toru: {}, modosu: {}'.format(left_toru, right_toru, modosu))
            while len(deq) and left_toru > 0:
                x = deq.popleft()
                temochi.append(x)
                left_toru -= 1
            while len(deq) and right_toru > 0:
                x = deq.pop()
                temochi.append(x)
                right_toru -= 1
            temochi = sorted(temochi)[::-1]
            while len(temochi) > 0 and modosu > 0:
                extra = temochi[-1]
                if extra > 0:
                    break
                temochi = temochi[:-1]
                modosu -= 1
            ans = max(ans, sum(temochi))
    print(ans)
main()

Submission status: Accepted

Solution code:
from heapq import heappush, heappop


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

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

ans = 0
for back in range(K + 1):
    getV = min(N, K - back)
    for left in range(getV + 1):
        r = getV - left
        S = 0
        hq = []
        for i in range(left):
            heappush(hq, V[i])
            S += V[i]
        for j in range(r):
            heappush(hq, V[N - 1 - j])
            S += V[N - 1 - j]
        for k in range(back):
            if len(hq) > 0 and hq[0] < 0:
                S -= heappop(hq)

        ans = max(ans, S)

print(ans)

Submission status: Accepted

Solution code:
import numpy as np

def calculate(arr,n,k):
    max = 0

    maxSum = min(n,k)
    # A+B的和

    for i in range(0,maxSum+1):

        for l in range(0,i+1):
            larr = arr[:l]
            if i-l == 0:
                rarr = np.array([])
            else:
                rarr = arr[-(i-l):]

            ab = np.concatenate([larr,rarr])

            abs = np.sort(ab,axis=0)

            # 扔东西
            # k - i

            thawMax = (k-i)

            for th in range(thawMax+1):
                abs[:th] = 0
                tmpSum = np.sum(abs,axis=0)

                if tmpSum > max:
                    max = tmpSum


    return int(max)



S = input().split(" ")
N = int(S[0])
K = int(S[1])

arr = [int(s) for s in input().split(" ")]
arr = np.array(arr)

result = calculate(arr,N,K)

print(result)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

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

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

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

  ans=-inf
  a=min(n,k)
  for i in range(a+1):
    sm=0
    for j in range(a+1-i):
      if j!=0:
        _q=l[:i]+l[-j:]
      else:
        _q=l[:i]

      q=[]
      for x in _q:
        heapq.heappush(q,x)
      ans=max(ans,sum(q))

      for _ in range(k-i-j):
        if len(q)>0:
          heapq.heappop(q)
          ans=max(ans,sum(q))
        else:
          break

  return ans

# main()
print(main())

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
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(K//2+1):
        for j in range(min(K-i+1,N)):
            l=V[:j]+V[max(j,N-(K-i-j)):]
            l.sort()
            for k in range(i+1):
                ans=max(ans,sum(l[k:]))
    print(ans)
            
        

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#  Copyright: this code was written at 2020. for AtCoder by Silviase

# Aをi回,Bをj回行ったとする
#   - i+j <= k を満たす
#   - i+j >= n なら全部取ったことにする
#   - 戻す回数はmin(k, 負の要素数)である
# 以上のことを踏まえfor文を回す

n, k = map(int, input().split())
val = list(map(int, input().split()))
left_acc = [0]
right_acc = [0]
for i in range(len(val)):
    left_acc.append(left_acc[len(left_acc) - 1] + val[i])
    right_acc.append(right_acc[len(right_acc) - 1] + val[len(val) - 1 - i])

res = 0

for i in range(0, k + 1):
    for j in range(0, k - i + 1):
        # print("i, j = ", i, j)
        valnew = []
        if i + j > n:
            valnew = val
        else:
            for l in range(1, i+1):
                valnew.append(val[l - 1])
            for l in range(1, j+1):
                valnew.append(val[n - l])
        valnew.sort()
        valsum = sum(valnew)
        for l in range(k-i-j):
            if l >= len(valnew):
                break
            else:
                valsum = max(valsum, valsum - valnew[l])
        res = max(res, valsum)
        # print(valnew)

print(res)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, K = [int(x) for x in input().split()]
V = [int(x) for x in input().split()]

ans = 0
for i in range(K + 1):
    for j in range(K + 1 - i):
        k = K - i - j
        tmp = list()
        tmp.extend(V[:min(i, N)])
        tmp.extend(V[max(i, N - j):N])
        tmp.sort(reverse=True)
        for _ in range(k):
            if len(tmp) > 0 and tmp[-1] < 0:
                tmp.pop()
        ans = max(ans, sum(tmp))

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, K = [int(x) for x in input().split()]
V = [int(x) for x in input().split()]

ans = 0
for i in range(K + 1):
    for j in range(K + 1 - i):
        for k in range(K + 1 - i - j):
            tmp = list()
            tmp.extend(V[:min(i, N)])
            tmp.extend(V[max(i, N - j):N])
            tmp.sort(reverse=True)
            for _ in range(k):
                if len(tmp) > 0 and tmp[-1] < 0:
                    tmp.pop()
            ans = max(ans, sum(tmp))

print(ans)

Submission status: Accepted

Solution code:
import bisect

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


ans = 0
R = min(N, K)
for r in range(R+1):
  for a in range(r+1):
    left = V[:a]
    b = r - a
    if b == 0:
      right = []
    else:
      right = V[-b:]
    
    v = left + right
    v.sort()
    n_nega = bisect.bisect_left(v, 0)
    k = min(n_nega, K-r)
    ans = max(ans, sum(v[k:]))


print(ans)

Submission status: Accepted

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

def main():
    N,K = map(int,input().split())
    V = list(map(int,input().split()))
    
    ans = -(10**10)
    for pick in range(min(N+1,K+1)):
        throw = min(pick,K-pick)
        for left in range(pick+1):
            right = pick-left
            p = []
            minus = 0
            for i in range(left):
                if V[i] < 0:
                    minus += 1
                p.append(V[i])
            for i in range(right):
                if V[-i-1] < 0:
                    minus += 1
                p.append(V[-i-1])
            p.sort()
            if minus >= throw:
                rest = p[throw:]
            else:
                rest = p[minus:]
            ans = max(ans,sum(rest))
    
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

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

# 最終的に「持っているもの」の価値の合計を高めたい
# Dから取り出すことをpop、Dに詰めることをenqueueとする
ans = 0
for pop_cnt in range(K + 1):
    enqueue_cnt = K - pop_cnt

    if pop_cnt > N:
        continue

    for l in range(pop_cnt + 1):
        holding = []

        r = pop_cnt - l
        holding += V[:l]
        holding += V[N - r:]

        holding.sort()
        tmp_ans = sum(holding)

        for e in range(enqueue_cnt):
            if e >= len(holding):
                break

            if holding[e] < 0:
                tmp_ans += -holding[e]

        ans = max(ans, tmp_ans)

print(ans)

Submission status: Accepted

Solution code:
#coding: utf-8
import math
import heapq
import bisect
import numpy as np
#from scipy.misc import comb

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

ans = 0

# iが左からとる回数、jが右からとる回数
for i in range(K+1):
  for j in range(K+1-i):
    if i+j > N:
      break
    now = sorted(V[:i]+V[N-j:])
    tmp = min(K-i-j,bisect.bisect_left(now, 0))
    ans = max(ans,sum(now[tmp:]))

print(ans)

Submission status: Accepted

Solution code:
import bisect
n,K = map(int, input().split(' '))
a = list(map(int, input().split(' ')))
ans = [0]
if K>2*n:
    K = 2*n
if K == 1:
    print(max(a[0],a[n-1],0))
    exit()
for k in range((K+1)//2,min(K+1,n+1)):
    r = K-k
    for i in range(k+1):
        ls = a[:i]+a[n-k+i:]
        ls.sort()
        if r == 0:
            ans.append(sum(ls))
        elif ls[r-1]<0:
            ans.append(sum(ls[r:]))
        else:
            x = bisect.bisect_left(ls,0)
            ans.append(sum(ls[x:]))
print(max(ans))

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
import sys
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
    
def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return sorted([list(map(int, input().split())) for _ in range(n)])

def main():
    n,k = inpm()
    v = inpl()
    a = [0 for _ in range(n+1)]
    b = [0 for _ in range(n+1)]
    ans = 0
    for i in range(n):
        a[i+1] = a[i] + v[i]
        b[i+1] = b[i] + v[n-1-i]
    for x in range(min(n+1,k+1)):
        for y in range(min(n-x+1,k-x+1)):
            que = []
            for i in range(x):
                que.append(v[i])
            for i in range(y):
                que.append(v[n-1-i])
            que.sort()
            l = len(que)
            pre = a[x] + b[y]
            for z in range(min(l,k-x-y)):
                if que[z]>=0:
                    break
                pre -= que[z]
                ans = max(ans,pre)
            ans = max(ans,pre)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import bisect
n,k=map(int, input().split())
V=list(map(int, input().split()))
ans=0
for i in range(k+1):
  for j in range(k+1-i):
    if i+j>n:
      break  
    #手に取りだしたもの
    A=sorted(V[:i]+V[n-j:])
    a=min(k-i-j,bisect.bisect_left(A, 0))
    ans=max(ans,sum(A[a:]))
print(ans)

Submission status: Accepted

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

for i in range(n+1):
    for j in range(n+1):
        num = i + j
        if num > n or num > k: continue
        item = v[:i] + v[n-j:]
        item.sort()
        rem = k - num
        s = sum(item)
        for x in item:
            if x >= 0: break
            if rem:
                s -= x
                rem -= 1
            else: break
        ans = max(ans, s)

print(ans)

Submission status: Accepted

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

R = min(N, K)
ans = -10**7+1
for i in range(R+1):
    for j in range(i+1):
        A, B = j, i-j
        jeweler = []
        if A != 0:
            jeweler += V[:A]
        if B != 0:
            jeweler += V[-B:]
        
        jeweler.sort()
        rem_k = K-(A+B)
        can = sum(jeweler)
        for k in range(min(rem_k, len(jeweler))):
            if jeweler[k] < 0:
                can += -jeweler[k]
        if ans < can:
            ans = can
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(1, M+1):
    for a in range(i+1):
        L = sorted(V[:a] + V[N-(i-a):], reverse=True)
        for _ in range(K-i):
            if L and L[-1] < 0:
                L.pop()
            else:
                break
        ans = max(ans, sum(L))
print(ans)

Submission status: Accepted

Solution code:
import bisect

n,k = map(int, input().split())
v = list(map(int, input().split()))
ans = 0
for i in range(k+1):
  for j in range(k+1-i):
    if i > n-j:
      break
    now = sorted(v[:i]+v[n-j:])
    tmp = min(k-i-j,bisect.bisect_left(now, 0))
    ans = max(ans,sum(now[tmp:]))
print(ans)

Submission status: Accepted

Solution code:
import bisect

n, k = map(int, input().split())
*v, = map(int, input().split())
candidate = []
for i in range(k+1):
    for j in range(k+1-i):
        if i + j >= n:
            candidate.append(v)
        elif j == 0:
            candidate.append(v[:i])
        else:
            candidate.append(v[:i]+v[j*(-1):])
ans = 0
for cand in candidate:
    cand.sort()
    idx = bisect.bisect(cand, -1)
    rem = k-len(cand)
    p = min(idx, rem)
    if ans < sum(cand[p:]):
        ans = sum(cand[p:])
print(ans)