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 heapq import heappush, heappop, heapify

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

# N jewels in dequeue D
# at most K operations
# 1 <= N <= 50
# 1 <= K <= 100
# -10000000 <= Vi <= 10000000

# Operation A, B: Remove left or right
# Operation C, D: Add to left or right

S = 0
for take in range(min(N, K) + 1):
    for takeL in range(take + 1):
        takeR = take - takeL
        hand = []
        for i in range(takeL):
            heappush(hand, V[i])
        for i in range(takeR):
            if N - i - 1 < takeL:
                break
            heappush(hand, V[N- i - 1])
        S = max(sum(hand), S)
        for _ in range(K - take):
            if not hand or hand[0] >= 0:
                break
            heappop(hand)
            S = max(sum(hand), S)
print(S)

Submission status: Accepted

Solution code:
from collections import deque
from copy import deepcopy

N, K = map(int, input().split())
V = list(map(int, input().split()))
q = deque()
for v in V:
    q.append(v)
ans = 0
jotai = []
for l in range(K + 1):
    for r in range(K + 1 - l):
        if l + r <= N:
            jotai.append([l, r, K - l - r])

for i in range(len(jotai)):
    d = deepcopy(q)
    tmp = []
    for l in range(jotai[i][0]):
        tmp.append(d.popleft())
    # print(tmp)
    for r in range(jotai[i][1]):
        tmp.append(d.pop())
    # print(tmp)
    for k in range(jotai[i][2]):
        if tmp and min(tmp) < 0:
            tmp.remove(min(tmp))
    # print(tmp)
    ans = max(sum(tmp), ans)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
from copy import deepcopy

N, K = map(int, input().split())
V = list(map(int, input().split()))
q = deque()
for v in V:
    q.append(v)
ans = 0
jotai = []
for l in range(K + 1):
    for r in range(K + 1 - l):
        if l + r <= N and l + r  <= K:
            jotai.append([l, r, K - l - r])

for i in range(len(jotai)):
    d = deepcopy(q)
    tmp = []
    for l in range(jotai[i][0]):
        tmp.append(d.popleft())
    # print(tmp)
    for r in range(jotai[i][1]):
        tmp.append(d.pop())
    # print(tmp)
    for k in range(jotai[i][2]):
        if (tmp and min(tmp) < 0):
            tmp.remove(min(tmp))
    # print(tmp)
    ans = max(sum(tmp), ans)
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
from heapq import *
n,k=[int(i) for i in input().split()]
a=[int(i) for i in input().split()]

#print(n,k,a)
ans = 0
k=min(k,2*n)
for l in range(min(n,k)+1):
    for r in range(min(k-l,n-l)+1):
        for sute in range(min(k-l-r,l+r)+1):
            check = a[:l]+a[n-r:]
            heapify(check)
#            print(l,r,sute,check)
            c=0
            while(c < sute and check and check[0] < 0):
                heappop(check)
                c+=1
            ans = max(ans, sum(check))
print(ans)

Submission status: Accepted

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


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


def cal(r, k, K, V):
    l = k - r
    if l == 0:
        A = V[:r]
    elif r == 0:
        A = V[-l:]
    else:
        A = V[:r] + V[-l:]
    A.sort()
    for i, a in enumerate(A):
        if i < min(k, K-k) and a < 0:
            A[i] = 0
        else:
            break
    return sum(A)


def main():
    N, K = LI()
    V = LI()
    ans = 0
    for k in range(1, min(N, K)+1):
        for l in range(k+1):
            ans = max(ans, cal(l, k, K, V))
    print(ans)
    return


main()

Submission status: Accepted

Solution code:
n,k=list(map(int, input().split()))
V=list(map(int, input().split()))
ans=0
r=min(n,k)
for a in range(r+1):
    for b in range(r+1-a):
        if b==0:
            v=V[:a]
        else:
            v=V[:a]+V[-b:]
        v.sort()
        for i in range(k+1-a-b):
            if i>=len(v):
                break
            if v[i]>0:
                break
        ans=max(ans,sum(v[i:]))
print(ans)

Submission status: Accepted

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

ans = []
for k_l in range(K+1):
    rem = K - k_l
    for k_r in range(rem+1):
        if k_l + k_r > N:
            continue
        rem_ = rem-k_r
        v = V[:k_l]+V[N-k_r:]
        #print(k_l,k_r,rem_,v)
        v.sort()
        for i in range(rem_):
            if i < len(v) and v[i] < 0:
                v[i] = 0
        #print(v)
        ans.append(sum(v))


print(max(ans))

Submission status: Accepted

Solution code:
n,k=list(map(int, input().split()))
V=list(map(int, input().split()))
ans=0
r=min(n,k)
for a in range(r+1):
    for b in range(r+1-a):
        if b==0:
            v=V[:a]
        else:
            v=V[:a]+V[-b:]
        v.sort()
        for i in range(k+1-a-b):
            if i>=len(v):
                break
            if v[i]>=0:
                break
        ans=max(ans,sum(v[i:]))
print(ans)

Submission status: Accepted

Solution code:
import numpy as np 

N, K = map(int, input().split())
vs = np.array([int(v) for v in input().split()])
ak = min(N + 1, K + 1)
max_value = 0

for a in range(ak):
    bk = min(N - a + 1, K - a + 1)
    for b in range(bk):
        n_remove = K - a - b
        l = np.sum(vs[:a]) if a > 0 else 0
        r = np.sum(vs[-b:]) if b > 0 else 0
        
        if a > 0 and b > 0:
            pos = np.r_[vs[:a], vs[-b:]]
            order = np.argsort(pos)
            pos = pos[order]
        elif a > 0:
            pos = vs[:a]
            order = np.argsort(pos)
            pos = pos[order]
        elif b > 0:
            pos = vs[-b:]
            order = np.argsort(pos)
            pos = pos[order]
        else:
            pos = np.array([])

        n_minus = len(np.where(pos < 0)[0])
        
        value = l + r - np.sum(pos[:n_minus]) if n_minus < n_remove else l + r - np.sum(pos[:n_remove])
        
        max_value = max(value, max_value)

print(max_value)

Submission status: Accepted

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

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

def calc(l, r):
    # Kより多く操作するケースは不可
    if l+(N-r)>K:
        return -INF
    ngtv=[]
    res=0
    # 左から取る分
    for i in range(l):
        res+=V[i]
        if V[i]<0:
            ngtv.append(V[i])
    # 右から取る分
    for i in range(N-1, r-1, -1):
        res+=V[i]
        if V[i]<0:
            ngtv.append(V[i])
    # マイナス分をソートしておく
    ngtv.sort()
    # 取った分の操作回数
    k=l+(N-r)
    i=0
    # まだ操作できるかつマイナスが残ってる限り、捨てる
    while k<K and i<len(ngtv):
        res-=ngtv[i]
        i+=1
        k+=1
    return res

ans=-INF
# 左右どこまで取るかを全通り試す
for l in range(N+1):
    for r in range(l, N+1):
        ans=max(ans, calc(l, r))
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from bisect import bisect
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 - left):
        if left > n - right or left + right > k:
            continue
        li = sorted(v[:left] + v[n - right:])
        rem = min(bisect(li, 0), k - left - right)
        ans = max(ans, sum(li[rem:]))
print(ans)

Submission status: Accepted

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

for l in range(K + 1):
	for r in range(K - l + 1):
		inHand = []
		if l + r > N:  # Nを超えてしまうありえない場合を処理
			break
		# inHandに左からl個、右からr個の要素を追加
		inHand = V[: l]
		inHand.extend(V[N - r:])
		tmp = sum(inHand)  # 現時点でのinHandの和をtmpとして負の要素をtmpから引いていく
		# inHand中の負の要素を消せるだけ消す
		inHand.sort()
		for i in range(min(K - l - r, l + r)):
			if inHand[i] >= 0:
				break
			tmp -= inHand[i]
		ans = max(ans, tmp)

print(ans)

Submission status: Accepted

Solution code:
# abcde	s=input()	s='abcde'
# abcde	s=list(input())	s=['a', 'b', 'c', 'd', 'e']
# 5(1つだけ)	a=int(input())	a=5
# 1 2	| x,y = s_inpl()   |	x=1,y=2
# 1 2 3 4 5 ... n 　	li = input().split()	li=['1','2','3',...,'n']
# 1 2 3 4 5 ... n 　	li = inpl()	li=[1,2,3,4,5,...,n]
# FFFTFTTFF 　	li = input().split('T')	li=['FFF', 'F', '', 'FF']

# INPUT
# 3
# hoge
# foo
# bar
# ANSWER
# n=int(input())
# string_list=[input() for i in range(n)]

import math
import copy
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
from bisect import bisect_left, bisect_right
# import numpy as np

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]

def i_inpl(): return int(input())
def s_inpl(): return map(int,input().split())
def l_inpl(): return list(map(int, input().split()))
INF = float("inf")

############
############
############


N, K = s_inpl()
V = l_inpl()
rV = V[::-1]
ans = 0
for l in range(K+1):
    for r in range(K+1-l):
        if l + r > N:
            continue
        d = K - l - r
        get_l = []
        current_score = 0
        for i in range(l):
            current_score += V[i]
            get_l.append(V[i])
        for i in range(r):
            current_score += rV[i]
            get_l.append(rV[i])
        get_l.sort()
        for i in range(d):
            if i >= len(get_l):
                break
            if get_l[i] > 0:
                break
            current_score -= get_l[i]

        ans = max(ans, current_score)

print(ans)

Submission status: Accepted

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

    m = 0 
    r = min(N, K)
    for a in range(r+1):
        for b in range(r+1-a):
            if b == 0:
                v = V[:a]
            else:
                v = V[:a] + V[-b:]
            v.sort()    
            for i in range(K+1-a-b):
                if i >= len(v):
                    break
                if  v[i] >= 0:
                    break
            s = sum(v[i:])
            if s > m:
                m = s

    print(m)


main()

Submission status: Accepted

Solution code:
import math
from functools import reduce
from collections import deque

def s(generator, splitter, mapper):
    return [ mapper(s) for s in generator().split(splitter) ]

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

n,k = get_nums_l()
v = get_nums_l()

# 左側でpos回操作するときの最大得点
left = [0]*(k+1)
leftmark = [0]*(k+1)
# 右側
right = [0]*(k+1)

for i in range(1,k+1):
    score = max(left[i-1], sum(v[:i]))
    leftmark[i] = i
    for ii in range(i//2):
        ii += 1
        score_ = sum(sorted(v[:i-ii],reverse=True)[:i-(ii*2)])
        if score_ > score:
            score = score_
            leftmark[i] = i-ii
    left[i] = score

for i in range(1,k+1):
    score = max(right[i-1],sum(v[max(leftmark[k-i],(n-i)):]))
    for ii in range(i//2):
        ii += 1
        score = max(score, sum(sorted(v[max(leftmark[k-i],n-i+ii):],reverse=True)[:min(n-leftmark[k-i], i-(ii*2))]))
    right[i] = score

ans = 0

for i in range(k+1):
    ans = max(ans, left[i] + right[k-i])
print(ans)

Submission status: Accepted

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

for l in range(K + 1):
	for r in range(K - l + 1):
		inHand = []
		if l + r > N:  # Nを超えてしまうありえない場合を処理
			break

		# inHandに左からl個、右からr個の要素を追加
		inHand = V[: l]
		inHand.extend(V[N - r:])
		tmp = sum(inHand)  # 現時点でのinHandの和をtmpとして負の要素をtmpから引いていく

		# inHand中の負の要素を消せるだけ消す
		inHand.sort()
		for i in range(min(K - l - r, l + r)):
			if inHand[i] >= 0:
				break
			tmp -= inHand[i]

		ans = max(ans, tmp)

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 A in range(M+1):
    for B in range(M+1-A):
        C = K - (A+B)
        p = []
        m = []
        for i in range(A):
            if V[i] >= 0:
                p.append(V[i])
            else:
                m.append(V[i])
        for i in range(B):
            if V[N-1-i] >= 0:
                p.append(V[N-1-i])
            else:
                m.append(V[N-1-i])
        m.sort()
        if C < len(m):
            m = m[C:]
        else:
            m = [0]
        tmp = sum(m)+sum(p)
        ans = max(ans, tmp)
print(ans)

Submission status: Accepted

Solution code:
def d_equeue(N, K, V):
    ans = 0
    for l in range(K + 1):
        for r in range(K - l + 1):  # 左右から宝石を何個取り出すか
            if l + r > N:
                continue

            # 決めた「取り出す個数」に従い宝石を取り出す
            get_jewelry = V[:l] + V[N - r:]
            now_value = sum(get_jewelry)

            # 価値が負の宝石を、価値が小さなものから戻す
            d = K - l - r  # 戻す操作にかける回数
            get_jewelry.sort()
            for i in range(d):
                if i >= len(get_jewelry) or get_jewelry[i] > 0:
                    break  # 戻せないか、戻す必要がない
                now_value -= get_jewelry[i]
            ans = max(ans, now_value)
    return ans

N, K = [int(i) for i in input().split()]
V = [int(i) for i in input().split()]
print(d_equeue(N, K, V))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
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):
        hand = []
        if l+r > n:
            continue

        hand = list(v[:l])
        hand.extend(list(v[len(v)-r:]))
        d = k - l - r

        now = sum(hand)
        hand.sort()

        for i in range(min(d, len(hand))):
            if hand[i] >= 0:
                break
            now -= hand[i]

        ans = max(ans, now)

print(ans)

Submission status: Accepted

Solution code:
[N,K] = list(map(int,input().split()))
V = list(map(int,input().split()))
C = [0]*(N+1)
for i in range(N):
  C[i+1] = C[i]+V[i]
ans = 0
for i in range(N+1):
  for j in range(N+1):
    if i+j > K or i+j > N:
      continue
    sum = C[i]+(C[N]-C[N-j])
    rem = K-i-j
    v = []
    for k in range(i):
      if V[k] < 0:
        v.append(V[k])
    for k in range(j):
      if V[N-1-k] < 0:
        v.append(V[N-1-k])
    v = sorted(v)
    for k in range(min(rem,len(v))):
      sum -= v[k]
    ans = max(ans,sum)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

N, K = map(int, input().split())
V = list(map(int, input().split()))
ans = 0
O = min(N, K)
for i in range(O+1):
    for j in range(O-i+1):
        if i + j > O:
            break
        DV = deque(V)
        S = 0
        nums = []
        for _ in range(i):
            nums.append(DV.popleft())
        for _ in range(j):
            nums.append(DV.pop())
        nums.sort()
        S = sum(nums)
        for n in range(min(K-i-j, len(nums))):
            if nums[n] >= 0:
                break
            S -= nums[n]
        ans = max(ans, S)
print(ans)

Submission status: Accepted

Solution code:
from copy import deepcopy

N, K = map(int, input().split())
V = tuple(map(int, input().split()))
max_score = -1000000000
for i in range(K+1):
    for j in range(K - i + 1):
        if i + j > N:
            continue
        # 左からi個取る
        hand = list(V[:i])
        # 右からj個取る
        hand.extend(V[N-j:])
        # 最大(K - i - j)個戻せる
        # print(i, j, hand)
        score = sum(hand)
        counter = 0
        for h in sorted(hand):
            counter += 1
            if K - i - j - counter < 0:
                break
            if h < 0:
                score -= h
        if max_score < score:
            max_score = score
print(max_score)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
vs = list(map(int,input().split()))
rvs = list(reversed(vs))
def get_cand(vs):
    sums = [0]
    trushes = [[]]
    pre = 0
    trush = []
    for v in vs:
        sums.append(v+pre)
        pre += v
        if v < 0:
            trush.append(-v)
        trushes.append(list(tuple(trush)))
    return sums, trushes
lsums, ltrushes = get_cand(vs)
rsums, rtrushes = get_cand(rvs)

total = []
for i in range(len(lsums)):
    for j in range(len(rsums)):
        if i + j > min(n, k):
            continue
        trushes = sorted(ltrushes[i] + rtrushes[j], reverse = True)
        total.append(lsums[i] + rsums[j] + sum(trushes[:k - i - j]))

print(max(total))

Submission status: Accepted

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

Q = min(N,K)+1
res = 0
for a in range(Q):
    for b in range(Q-a):
        W = V[:a] + V[N-b:]
        W.sort()
        for k in range(min(K-a-b,len(W))):
            if W[k] < 0:
                W[k] = 0
            else:
                break
        res = max(res,sum(W))

print(res)

Submission status: Accepted

Solution code:
import heapq
from itertools import chain

R = lambda: map(int, input().split())
n, k = R()
v = list(R())
r = 0
for i in range(1, min(n, k) + 1):
    for j in range(i):
        s = 0
        h = []
        for m in chain(range(i - j), range(n - j, n)):
            x = v[m]
            s += x
            if x < 0:
                heapq.heappush(h, x)
        j = i
        while h and j < k:
            s -= heapq.heappop(h)
            j += 1
        r = max(r, s)
print(r)

Submission status: Accepted

Solution code:
inf = float('inf')

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

volume = max(N, K)
take_max = min(N, K)

dpl = [[-inf] * (volume + 1) for _ in range(N + 1)]
dpr = [[-inf] * (volume + 1) for _ in range(N + 1)]
dpl[0][0] = dpr[0][0] = 0

for i, vv in enumerate(v, 1):
    for take in range(i + 1):
        dpl[i][take] = dpl[i - 1][take]
        if take > 0:
            dpl[i][take] = max(dpl[i][take], dpl[i - 1][take - 1] + vv)

for i, vv in enumerate(reversed(v), 1):
    for take in range(i + 1):
        dpr[i][take] = max(dpr[i][take], dpr[i - 1][take])
        if take > 0:
            dpr[i][take] = max(dpr[i][take], dpr[i - 1][take - 1] + vv)

ans = 0
for take_frm_left in range(take_max + 1):
    for take_frm_right in range(take_max + 1):
        if take_frm_left + take_frm_right > take_max: break
        for use_frm_left in range(take_frm_left + 1):
            remove_frm_left = take_frm_left - use_frm_left
            vl = dpl[take_frm_left][use_frm_left]
            for use_frm_right in range(take_frm_right + 1):
                remove_frm_right = take_frm_right - use_frm_right
                if (take_frm_left + take_frm_right + remove_frm_left + remove_frm_right) > K: continue
                vr = dpr[take_frm_right][use_frm_right]
                # print(vl + vr, take_frm_left, use_frm_left, take_frm_right, use_frm_right)
                ans = max(ans, vl + vr)
print(ans)

Submission status: Accepted

Solution code:
n,k,*v=map(int,open(0).read().split())
m=0
for i in range(n):
 for j in range(min(k,n)-i+1):
  t=sorted(v[:i]+v[:~j:-1])
  while t and(k-i-j)*t[0]<0:t.pop(0);j+=1
  m=max(m,sum(t))
print(m)

Submission status: Accepted

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

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

ans = 0
for i in range(k+1):
    for nl in range(i+1):
        nr = min(k - nl, n-nl)
        ansl, ansr = 0, 0
        for n_trash in range(nl):
            ansll, ansrr = 0, 0
            hands = sorted(v[:nl-n_trash])
            for vv in hands:
                if vv < 0 and n_trash > 0:
                    n_trash -= 1
                else:
                    ansll += vv
            ansl = max(ansl, ansll)

        for n_trash in range(nr):
            ansrr = 0
            hands = sorted(v[-(nr-n_trash):])
            # print(hands, nr, n_trash)
            for vv in hands:
                if vv < 0 and n_trash > 0:
                    n_trash -= 1
                else:
                    ansrr += vv
            ansr = max(ansr, ansrr)
        # print(ansl, ansr)
        ans = max(ans, ansl + ansr)

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(K+1):
    for r in range(K-l+1):
        if l + r < N:
            bag = V[:l] + V[N-r:] + [0]
            rest_ope = K-l-r
        else:
            bag = V[:]
            rest_ope = K - N
        for _ in range(rest_ope):
            min_bag = min(bag)
            if min_bag < 0 and rest_ope > 0:
                bag.remove(min_bag)
                rest_ope -= 1
        else:
            ans = max(ans, sum(bag))

print(ans)

Submission status: Accepted

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

res = 0

for i in range(min(n, k)+1):
    for j in range(min(n, k)+1 - i):
        if j != 0:
            v_sub = v[:i] + v[-j:]
        else:
            v_sub = v[:i]
        if len(v_sub) > 0:
            v_sub.sort()
            for r in range(k - (i + j)+1):
                res = max(res, sum(v_sub))
                v_sub.pop(0)
                if len(v_sub) == 0:
                    break

print(res)

Submission status: Accepted

Solution code:
import heapq
import copy

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

M = min(N, K)

ans = 0
for i in range(M + 1):
    for j in range(M - i + 1):
        l = V[:i] + V[N - 1:N - j - 1:-1]
        t = sum(l)
        l.sort()
        for n in range(min(K - i - j, len(l))):
            if l[n] >= 0:
                break
            t -= l[n]
        if t > ans:
            ans = t

print(ans)

Submission status: Accepted

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

value = max_value = 0
for j in range(K//2+1):
    for i in range(K-j+1):
        if K-j >= N:
            value = V
        else:
            if i == K-j:
                value = V[:K-j]
            else:
                value = V[:i]+V[-(K-j-i):]
        value.sort()
        # print(i,j,value)


        jj = min(len(value)-1,j)
        if value[jj] <= 0:
            s = sum(value[jj:])
        else:
            s = sum([i for i in value if i>0])

        if  s > max_value:
            max_value = s
print(max_value)

Submission status: Accepted

Solution code:
from collections import deque
from copy import deepcopy

length,kaisu=map(int,input().split())
A=deque(map(int,input().split()))
maxhist=[0]
for left in range(kaisu+1):
  for right in range(kaisu-left+1):
    l=deepcopy(A)
    point=[]
    dropable=kaisu-left-right
    for i in range(left):
      try:
        num=l.popleft()
        point.append(num)
      except:
        pass
    for j in range(right):
      try:
        num2=l.pop()
        point.append(num2)
      except:
        pass
    droptime=0
    while(droptime<dropable):
      if point==[]:
        break
      elif min(point)>0:
        break
      else:
        try:
          point.sort(reverse=True)
          point.pop(-1)
          droptime+=1
        except:
          break
    maxhist.append(sum(point))
print(max(maxhist))

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
vs = list(map(int, input().split()))
m = 0
r = min(n, k)
for a in range(r+1):
    for b in range(r-a+1):
        cd = k - (a + b)
        if b == 0:
            hold = sorted(vs[:a])
        else:
            hold = sorted(vs[:a] + vs[-b:])
        ap = hold[min(len([1 for x in hold if x < 0]), cd):]
        s = sum(ap)
        m = max(s, m)
print(m)

Submission status: Accepted

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

Q = min(N,K)+1
res = 0
for a in range(Q):
    for b in range(Q-a):
        W = V[:a] + V[N-b:]
        W.sort()
        for k in range(min(K-a-b,len(W))):
            if W[k] < 0:
                W[k] = 0
            else:
                break
        res = max(res,sum(W))

print(res)

Submission status: Accepted

Solution code:
import itertools

n, k = [int(i) for i in input().split()]
v = [int(i) for i in input().split()]
v2 = list(reversed(v))

answer = 0
for i in range(k+1):
    for j in range(k-i+1):
        for l in range(k-i-j+1):
            if i + j >= n:
                持っている宝石 = v[:]
            else:
                持っている宝石 = v[:i] + v2[:j]
            持っている宝石.sort()
            価値の合計 = sum(持っている宝石)

            for o in range(l):
                if o < len(持っている宝石):
                    if 持っている宝石[o] < 0:
                        価値の合計 -= 持っている宝石[o]
            answer = max(answer, 価値の合計)

print(answer)

Submission status: Accepted

Solution code:
import sys
from collections import deque
input = sys.stdin.readline

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

for i in range(K+1): #左から
    for j in range(K-i+1): #右から
        hand = deque()
        if i + j <= N:
            for n in range(i): #左から
                hand.append(V[n]) 
            for m in range(j): #右から
                hand.append(V[N-m-1])
            for k in range(K-i-j):
                if len(hand) > 0 and min(hand) < 0:
                    hand.remove(min(hand)) 
            score.append(sum(hand))

print(max(score))

Submission status: Accepted

Solution code:
import heapq
import copy

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

M = min(N, K)

ans = 0
a = 0
ah = []
for i in range(M + 1):
    if i > 0:
        v = V[i - 1]
        a += v
        if v < 0:
            heapq.heappush(ah, v)

    b = a
    bh = copy.copy(ah)
    for j in range(M + 1):
        if (i + j) > M:
            break
        if j > 0:
            v = V[N - j]
            b += v
            if v < 0:
                heapq.heappush(bh, v)

        c = b
        ch = copy.copy(bh)
        for n in range(min(K - i - j, len(ch))):
            c += -heapq.heappop(ch)
        if c > ans:
            ans = c

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun May 26 20:56:05 2019

@author: Yamazaki Kenichi
"""
import heapq

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

def a(K):
    if K > N:
        return N
    else:
        return K

ans = 0
for i in range(K):
    for j in range(a(K-i)+1):
        tmp = 0
        minus = [0]
        for k in range(a(K-i)):
            tmp += V[k-j]
            heapq.heappush(minus,V[k-j])
#            print(tmp,minus)
        for k2 in range(i):
            if minus[0] < 0:
                tmp += (-heapq.heappop(minus))
            else:
                break
#        print(ans,tmp,i,j,k)
        ans = max(ans,tmp)
    
print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate


def make_dp(vvv, n, k):
    dp = [-(10 ** 9)] * (k + 1)
    dp[0] = 0

    for i in range(min(n, k)):
        i += 1
        vv = vvv[:i]
        vv.sort(reverse=True)
        sm = sum(vv)
        dp[i] = max(dp[i], sm)
        while i < k and vv and vv[-1] < 0:
            sm -= vv.pop()
            i += 1
            dp[i] = max(dp[i], sm)

    return list(accumulate(dp, func=max))


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

acl = make_dp(vvv, n, k)
vvv.reverse()
acr = make_dp(vvv, n, k)
acr.reverse()

ans = max(map(sum, zip(acl, acr)))
ans = min(ans, sum(v for v in vvv if v > 0))
print(ans)

Submission status: Accepted

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

sumval = 0
for l in range(min(K+1,N+1)):
    for r in range(min(K+1-l,N-l+1)):
        sV = sorted(V[:l]+ V[N-r:])
        # i_div = 0
        # for i_div in range(len(sV)):
        #     if sV[i_div] > 0:
        #         break
        # for sute in range(min(K-r-l+1,len(sV),i_div+1)):
        for sute in range(min(K-r-l+1,len(sV))):
            c = sum(sV[sute:])
            sumval = max(c,sumval)

print(sumval)

Submission status: Accepted

Solution code:
from itertools import accumulate


def make_dp(vvv, n, k):
    dp = [-(10 ** 9)] * (k + 1)
    dp[0] = 0

    for i in range(min(n, k)):
        i += 1
        vv = vvv[:i]
        vv.sort(reverse=True)
        sm = sum(vv)
        dp[i] = max(dp[i], sm)
        while i < k and vv and vv[-1] < 0:
            sm -= vv.pop()
            i += 1
            dp[i] = max(dp[i], sm)

    return list(accumulate(dp, func=max))


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

acl = make_dp(vvv, n, k)
vvv.reverse()
acr = make_dp(vvv, n, k)

ans = max(acl[i] + acr[k - i] for i in range(k + 1))
ans = min(ans, sum(v for v in vvv if v > 0))
print(ans)

Submission status: Accepted

Solution code:
n,k,*v=map(int,open(0).read().split())
m=[]
r=range
for i in r(n+1):
 for j in r(min(k,n)-i+1):
  t=sorted(v[:i]+v[:~j:-1])
  while t and(k-i-j)*t[0]<0:t.pop(0);j+=1
  m+=sum(t),
print(max(m))