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:
N,K = map(int,input().split())
V = list(map(int,input().split()))
answer = 0
for i in range(min(N,K)+1):
    for j in range(min(N,K)+1-i):
        tempV = V[0:i]+V[N-j:] + [0]
        tempV.sort()
        for k in range(K-i-j):
            if tempV[0] < 0:
                tempV.pop(0)
        if sum(tempV) > answer:
            answer = sum(tempV)
            
print(answer)

Submission status: Accepted

Solution code:
from heapq import heappop, heappush

def getlist():
	return list(map(int, input().split()))

N, K = getlist()
V = getlist()
VV = [V[-1 - i] for i in range(N)]

ans = 0
for i in range(K + 1):
	if i == 0:
		pass
	elif i >= N:
		Q = []
		for j in V:
			heappush(Q, j)
		for j in range(K - N):
			if Q:
				if Q[0] < 0:
					heappop(Q)
				else:
					break
		val = sum(Q)
		if val > ans:
			ans = val

	else:
		for a in range(i + 1):
			Q = []
			b = i - a
			
			for x in range(a):
				heappush(Q, V[x])
			for x in range(b):
				heappush(Q, VV[x])
			for j in range(K - i):
				if Q:
					if Q[0] < 0:
						heappop(Q)
					else:
						break
			val = sum(Q)
			if val > ans:
				ans = val

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, K, V):
    ans = 0
    for k in range(min(K, N)+1):
        for i in range(k+1):
            l = V[:i]
            r = V[N-(k-i):]
            # print(l, r)
            lr = l + r
            lr.sort(reverse=True)

            for _ in range(K-k):
                if lr and lr[-1] < 0:
                    lr.pop()
                else:
                    break
            ans = max(ans, sum(lr))

    return ans


def main():
    N, K = read_int_n()
    V = read_int_n()
    print(slv(N, K, V))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, K = list(map(int, input().split()))
Vs = list(map(int, input().split()))
Length = len(Vs)
maxv = 0
for i in range(K + 1):
    count = K - i
    left = count
    right = 0
    for m in range(count + 1):
        if 0 <= left <= Length and 0 <= right <= Length:
            for p in range(i + 1):
                temp = sorted(Vs[:left] + Vs[Length - right:])
                for o in range(p):
                    if temp:
                        temp.pop(0)
                    else:
                        break
                sumv = sum(temp)
                if sumv > maxv:
                    maxv = sumv
            left -= 1
            right += 1

print(maxv)

Submission status: Accepted

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

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

def max_choice(V, n, m):
    if len(V) <= n:
        n = len(V)
    a = -999999999
    for i in range(n+1):
        tlist = V[:i]
        tlist.extend(V[len(V)-n+i:])
        tlist.sort()
        for j in range(m):
            if tlist[j]<0:
                tlist[j] = 0
            else:
                break       
        a = max(a, sum(tlist))
    return a

ans = 0
for i in range(1, min(N, K)+1):
    ans = max(max_choice(V, i, min(K-i, i-1)), ans)
    
print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
V = [int(i) for i in input().split()]
L = [0] * (N+1)
R = [0] * (N+1)
L_m = [[] for _ in range(N+1)]
R_m = [[] for _ in range(N+1)]

for i in range(1, N+1):
    L[i] = L[i-1] + V[i-1]
    R[i] = R[i-1] + V[-i]
    L_m[i] = L_m[i-1].copy()
    R_m[i] = R_m[i-1].copy()
    if V[i-1] < 0:
        L_m[i].append(V[i-1])
    if V[-i] < 0:
        R_m[i].append(V[-i])

ans = 0

for i in range(K+1):
    for l in range(K+1-i):
        r = K - i - l
        if l + r >= N:
            ans = max(ans, R[-1] - sum(R_m[-1]))
            break
        if r < 0:
            break
        M = L_m[l] + R_m[r]
        M.sort()
        if len(M) >= i:
            m = sum(M[:i])
        else:
            m = sum(M)
        a = L[l] + R[r] - m
        ans = max(ans, a)

print(ans)

Submission status: Accepted

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

dp=[[[-1 for i in range(k+1)] for j in range(n+1)] for l in range(n+1)]

def f(a, b, d):
    if d == 0: return 0
    if a == b and d > 1 and v[a] > 0: return v[a]
    if a == b and d > 1 and v[a] <= 0: return 0
    if dp[a][b][d] != -1: return dp[a][b][d]
    maxi = max(v[a] + f(a+1, b, d - 1), v[b] + f(a, b - 1, d - 1))
    if v[a] < 0 and d > 1:
        maxi = max(maxi, f(a + 1, b, d - 2))
    if v[b] < 0 and d > 1:
        maxi = max(maxi, f(a, b - 1, d - 2))
    maxi = max(maxi, 0)
    dp[a][b][d]=maxi
    return maxi


print(f(0, n-1, k))

Submission status: Accepted

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

max_score = 0
for i in range(N+1):
    for j in range(N+1):
        if not (i+j>K or i+j>N):
    
            H=V[:i]+V[N-j:]
            H.sort()
            suteru=[]
            for k in range(min(len(H),K-i-j)):
                if H[k]>0:
                    break
                else:
                    suteru.append(H[k])
            max_score=max(sum(H)-sum(suteru),max_score)
       
print(max_score)

Submission status: Accepted

Solution code:
n,k = map(int,raw_input().split())
v = map(int,raw_input().split())
best = 0
for i in xrange(min(n,k+1)):
	for j in xrange(min(n+1-i,k+1-i)):
		take = v[0:i]+v[n-j:]
		rid = k-i-j
		take = sorted(take)
		temp = sum(take)
		for x in xrange(min(rid,len(take))):
			if take[x] < 0:
				temp -= take[x]
		if temp > best:
			best = temp
print best

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
v = list(map(int, input().split()))
sum_jewel = []
for i in range(1, min(n, k)+1):
    for j in range(i+1):
        take = v[:j] + v[n-i+j:]
        take.sort()
        for l in range(k-i):
            try:
                if take[0] < 0:
                    del take[0]
            except:
                pass
        value = 0
        for m in range(len(take)):
            value += take[m]
        sum_jewel.append(value)
print(max(sum_jewel))

Submission status: Accepted

Solution code:
N,K = map(int, input().strip().split(' '))
V = list(map(int, input().strip().split(' ')))
V += V
# まず宝石をi個取る、その後j個返す
# i個の取り方はi+1通り
# 返す時は負のもののみ、絶対値が大きいtopj個を返すので、取り方が決まるとそのときの最大点はすぐ決まる
# 0 <= i <= K, 0 <= j <= K-i
now_max = 0
for i in range(1, min(K+1, N+1)):
  for offset in range(i+1):
    jewel = sorted(V[-offset+N: -offset+i+N])
    remain_del = K-i
    while True:
      if len(jewel) == 0 or remain_del == 0 or jewel[0] > 0:
        break
      jewel.pop(0)
      remain_del -= 1
    now_max = max(now_max, sum(jewel))
print(now_max)

Submission status: Accepted

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

N,K = map(int,input().split())
V = [int(i) for i in input().split()]
#
if N == 1:
    print(max(0,V[0]))
    exit()

ans = 0
for i in range(K): # 戻す数
    for j in range(K-i+1):
        if j <= N-(K-i-j):
            ans_list = V[:j]+V[N-(K-i-j):]
            ans_list.sort()
            tmp = sum(ans_list)
            for k in range(min(len(ans_list),i)):
                if ans_list[k] < 0:
                    tmp -= ans_list[k]
            ans = max(ans,tmp)
        else:
            pass

print(max(ans,0))

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify, heapreplace

class Solution:
    def main(self):
        N, K = map(int, input().split())
        V = list(map(int, input().split()))
        res = 0
        for n_l in range(min(N, K)+1):
            for n_r in range(min(N-n_l, K-n_l)+1):
                array = sorted(V[:n_l] + V[N - n_r:])
                # print(n_l, n_r, array, end=' ')
                for n_d in range(0, min(K-n_l-n_r, len(array))):
                    if array[0] < 0:
                        array.pop(0)
                    else:
                        break
                res = max(res, sum(array))
                # print(array)
        print(res)


if __name__ == '__main__':
    Solution().main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import heapq
from collections.abc import Iterable
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


def solve(N: int, K: int, V: "List[int]"):

    lq = []
    acc_l = 0
    acc_ml = []
    ret = 0
    for li in range(min(N+1, K + 1)):
        if 0 < li:
            acc_l += V[li - 1]
            if V[li - 1] < 0:
                acc_ml.append(V[li - 1])

        if ret < acc_l:
            ret = acc_l
        acc_r = 0
        ms = [v for v in acc_ml]
        ms.sort()
        for _ri in range(min(N+1, K + 1) - li):
            if 0 < _ri:
                ri = N - _ri
                acc_r += V[ri]
                if V[ri] < 0:
                    ms.append(V[ri])
                    ms.sort()
            ci = min(len(ms), K - li - _ri)
            acc_c = sum(ms[:ci])
            acc = acc_l + acc_r - acc_c
            if ret < acc:
                ret = acc
    return ret


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    V = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    result = solve(N, K, V)
    if isinstance(result, Iterable) and not isinstance(result, str):
        result = '\n'.join([str(v) for v in result])
    print(result)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from copy import deepcopy
N, K = map(int, input().split())
V = list(map(int, input().split()))
Lsum = [0]
Rsum = [0]
Lnegs = [[]]
Rnegs = [[]]
for i in range(N):
    Lsum.append(Lsum[i]+V[i])
    Rsum.append(Rsum[i]+V[N-i-1])
    Lnegs_cp = deepcopy(Lnegs[i])
    if V[i] < 0:
        Lnegs_cp.append(V[i])
        # Lnegs_cp = sorted(Lnegs_cp)
    Lnegs.append(Lnegs_cp)
    Rnegs_cp = deepcopy(Rnegs[i])
    if V[N-i-1] < 0:
        Rnegs_cp.append(V[N-i-1])
        # Rnegs_cp = sorted(Rnegs_cp)
    Rnegs.append(Rnegs_cp)

ans = 0

for dig in range(min(N+1, K+1)):
    n_del = K - dig
    for ldig in range(dig+1):
        rdig = dig - ldig
        LRsum = Lsum[ldig] + Rsum[rdig]
        negs = []
        for neg in Lnegs[ldig]:
            negs.append(neg)
        for neg in Rnegs[rdig]:
            negs.append(neg)
        negs = sorted(negs)
        for i in range(min(n_del, len(negs))):
            LRsum -= negs[i]
        ans = max(ans, LRsum)

print(ans)

# for llim in range(N+1):
#     rlim = N - llim
#     lmax = -1001001001
#     for k0 in range(min(K, llim)):
#         kh = min(K, llim) - k0
#         s0 = Lsum[k0]
#         s1 = 0
#         for l in range(min(len(Lnegs[k0]),kh)):
#             s1 -= Lnegs[k0][l]
#         lmax = max(lmax, s0+s1)
#         rmax = -1001001001
#         for k1 in range(min(K - k0, rlim)):
#             kh = min(K - k0, rlim) - k1
#             s0 = Rsum[k1]
#             s1 = 0
#             for l in range(min(len(Rnegs[k1]),kh)):
#                 s1 -= Rnegs[k1][l]
#             rmax = max(rmax, s0+s1)
#         ans = max(ans, lmax + rmax)

# print(ans)

Submission status: Accepted

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

N, K = map(int, input().rstrip().split(' '))
X = [0] + list(map(int, input().rstrip().split(' ')))

sorted_left_X = []
sorted_right_X = []
sorted_remove_X = []
for i in range(N+1):
    sorted_left_X.append(sorted([x for x in X[:i] if x < 0]))
    sorted_right_X.append(sorted([x for x in X[::-1][:i] if x < 0]))
    
    sorted_remove_X.append(sorted([x for x in X[:i] if x < 0] + [x for x in X[::-1][:i] if x < 0]))

cum_X = []
cum = 0
for x in X:
    cum += x
    cum_X.append(cum)

if K > N:
    temp = sorted([x for x in X if x < 0])
    print(cum_X[-1] - sum(temp[:min(len(temp), K)]))
else:
    max_count = 0
    for k in range(1,K+1):
        for i in range(k+1):
            temp = sorted(sorted_left_X[i] + sorted_right_X[k-i])
            temp2 = sum(temp[:min(len(temp), K-k)])
            max_count = max(cum_X[i] - cum_X[0] + cum_X[-1] - cum_X[i+N-k] - temp2, max_count)

    print(max_count)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
v = list(map(int, input().split()))
maxvalue = 0
for l in range(n+1):
    for r in range(l, n+1):
        ava = sorted(v[:l] + v[r:])
        takeop = len(ava)
        if takeop <= k:
            value = sum(ava)
            for i in range(min(takeop, k - takeop)):
                if ava[i] >= 0:
                    break
                else:
                    value -= ava[i]
            maxvalue = max(maxvalue, value)
print(maxvalue)

Submission status: Accepted

Solution code:
import sys
# gcd
from fractions import gcd
# 切り上げ，切り捨て
# from math import ceil, floor
# リストの真のコピー（変更が伝播しない）
# from copy import deepcopy
# 累積和。list(accumulate(A))としてAの累積和
from itertools import accumulate
# l = ['a', 'b', 'b', 'c', 'b', 'a', 'c', 'c', 'b', 'c', 'b', 'a']
# S = Counter(l)  # カウンタークラスが作られる。S=Counter({'b': 5, 'c': 4, 'a': 3})
# print(S.most_common(2))  # [('b', 5), ('c', 4)]
# print(S.keys())  # dict_keys(['a', 'b', 'c'])
# print(S.values())  # dict_values([3, 5, 4])
# print(S.items())  # dict_items([('a', 3), ('b', 5), ('c', 4)])
from collections import deque
# import math
# from functools import reduce
#
# input関係の定義
# fin = open('in_3.txt', 'r')
# sys.stdin = fin
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def li(): return list(input().rstrip())
# template


def iterate_tokens():
    for line in sys.stdin:
        for word in line.split():
            yield word


if __name__ == '__main__':

    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    V = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"

    # write code

    left = []
    right = []
    left.append(0)
    right.append(0)
    left.append(max(V[0], 0))
    right.append(max(V[-1], 0))
    for i in range(2, 2*N+1):
        tmp_max = 0
        for j in range(-(-i // 2), i+1):
            tmp_V = V[:j]
            tmp_V.sort()
            # print(i, j, tmp_V[i - 2 * j:])
            if tmp_max < sum(tmp_V[i - 2 * j:]):
                tmp_max = sum(tmp_V[i - 2 * j:])
        # print(tmp_max)
        left.append(tmp_max)

    for i in range(2, 2*N+1):
        tmp_max = 0
        for j in range(-(-i // 2), i+1):
            tmp_V = V[-j:]
            tmp_V.sort()
            if tmp_max < sum(tmp_V[i - 2 * j:]):
                tmp_max = sum(tmp_V[i - 2 * j:])
        # print(tmp_max)
        right.append(tmp_max)
    ans = []
    # print(left)
    # print(right)
    sV = sum([i for i in V if i >= 0])
    # print(sV)
    for j in range(0, min(2*N, K) + 1):
        tmp_ans = -10**9
        for i in range(j+1):
            if tmp_ans < left[i] + right[j - i]:
                tmp_ans = left[i] + right[j - i]
        ans.append(tmp_ans)
    print(min(max(ans), sV))

Submission status: Accepted

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


def solve(N: int, K: int, V: "List[int]"):
    l = [0] * (K + 1)
    r = [0] * (K + 1)
    for i in range(1, K + 1):
        v = V[:i]
        v.sort(reverse=True)
        for j in range(0, i):
            if i + j <= K:
                l[i + j] = max(l[i + j], sum(v[:i - j]))

    V.reverse()
    for i in range(1, K + 1):
        v = V[:i]
        v.sort(reverse=True)
        for j in range(0, i):
            if i + j <= K:
                r[i + j] = max(r[i + j], sum(v[:i - j]))

    for i in range(1, K + 1):
        l[i] = max(l[i], l[i - 1])
        r[i] = max(r[i], r[i - 1])

    #print(l)
    #print(r)
    ret = 0
    for i in range(0, len(l)):
        ret = max(ret, l[i] + r[K - i])
        #print(l[i], r[K - i], ret)

    tmp = 0
    for v in V:
        if v > 0:
            tmp += v
    ret = min(ret, tmp)
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    V = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    solve(N, K, V)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq

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

max_v = -float('inf')
for a in range(min(k, n)+1):
    total = 0
    minus = []
    for i in range(a):
        total += vs[i]
        if vs[i] < 0:
            heapq.heappush(minus, vs[i])
    max_v = max(max_v, total)
    for b in range(min(k-a, n-a)+1):
        c = k - a - b
        if c < 0:
            break
        h = minus[:]
        t = total
        for i in range(b):
            t += vs[n-1-i]
            if vs[n-1-i] < 0:
                heapq.heappush(h, vs[n-1-i])
        for i in range(c):
            if h:
                v = heapq.heappop(h)
                t -= v
            else:
                break
        max_v = max(max_v, t)

print(max_v)

Submission status: Accepted

Solution code:
from heapq import*
n,k=map(int,input().split())
*v,=map(int,input().split())
motimono=[]
ans=[]
if k>=n:
    k-=n
    heapify(v)
    ans.append(sum(v))
    for i in range(k):
        if len(v)>0:
            heappop(v)
        ans.append(sum(v))
    print(max(ans))
else:
    v*=2
    for j in range(1,k+1):
        for i in range(n-j,n+1):
            motimono=v[i:i+j]
            ans.append(sum(motimono))
            heapify(motimono)
            for i in range(k-j):
                if len(motimono)>0:
                    heappop(motimono)
                ans.append(sum(motimono))
    print(max(ans))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from copy import copy
from heapq import *
from collections import deque


N, K = list(map(int, input().split()))
jewels = deque(list(map(int, input().split())))
score = []

def startLoop(jewels, k, i, j):
    hand = []
    if k >= N:
        for _ in range(N):
            heappush(hand, jewels.pop())
    else:
        for _ in range(i):
            heappush(hand, jewels.popleft())
        for _ in range(j):
            heappush(hand, jewels.pop())
    return hand

def maximize(l, hand):
    s_max = 0
    s = 0
    for _ in range(min(l, len(hand))):
        s -= heappop(hand)
        if s > s_max:
            s_max = s
    return s_max

for k in range(K+1):
    current_score = -10**10
    for i in range(0, k+1):
        hand = startLoop(copy(jewels), k, i, k-i)
        temp_score = sum(hand) + maximize(K-k, copy(hand))
        if current_score < temp_score:
            current_score = temp_score
    score.append(current_score)

print(max(score))

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
arr=list(map(int,input().split()))
ans=0
for k in range(m):
  for i in range(m+1-k):
    j=m-k-i
    if i+j<=n:
      if j==0:
        tarr=arr[:i]
      else:
        tarr=arr[:i]+arr[-j:]
    else:
      tarr=arr[:]
    tarr=sorted(tarr)
    for l in range(min(len(tarr),k)):
      if tarr[l]<0:
        tarr[l]=0
    tsum=sum(tarr)
    ans=max(ans,tsum)
print(ans)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
v = list(map(int,input().split()))
a = 0 #左からaことる
b = 0 #右からbことる

ans = -10**10
while a <= min(k,n):
    while b <= min(k-a,n-a):
        plus = []
        minus = []
        for i in range(a):
            if v[i] >= 0:
                plus.append(v[i])
            else:
                minus.append(v[i])
        for i in range(b):
            if v[-1-i] >= 0:
                plus.append(v[-1-i])
            else:
                minus.append(v[-1-i])
        plus.sort()
        minus.sort()
        temp = sum(plus) + sum(minus)
        m = k-a-b #取り出した後に残った操作回数
        for i in range(min(m,len(minus))):
            temp += -minus[i]
        m = m - min(m,len(minus)) #負の数を戻した後に残った操作回数
        if temp > ans:
            ans = temp
        b += 1
    a += 1
    b = 0
print(ans)

Submission status: Accepted

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



"""
import sys


from collections import deque
from functools import lru_cache

@lru_cache(maxsize=None)
def dig_left(n, q):
    res = [0]
    for di in range(1, min(n, len(q))+1):
        bu = n - di
        dig = list(q[:di])
        dig.sort()
        while bu and dig and dig[0] < 0:
            dig.pop(0)
            bu -= 1
        res.append(sum(dig))
    return max(res)


@lru_cache(maxsize=None)
def dig_right(n, q):
    res = [0]
    for di in range(1, min(n, len(q))+1):
        bu = n - di
        dig = list(q[-di:])
        dig.sort()
        while bu and dig and dig[0] < 0:
            dig.pop(0)
            bu -= 1
        res.append(sum(dig))
    return max(res)


def solve(N, K, V):
    ans = [0]
    limit = sum([v for v in V if v > 0])
    for left in range(K+1):
        q = deque(V)
        right = K - left
        l_dig = dig_left(left, tuple(V))
        r_dig = dig_right(right, tuple(V))
        ans.append(min(limit, l_dig+r_dig))
    return max(ans)


def main(args):
    N, K = map(int, input().split())
    V = [int(v) for v in input().split()]
    ans = solve(N, K, V)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
import numpy as np
words = lambda t : list(map(t, input().split()))

n,k = words(int)
vs = words(int)
#print(vs)
ans = 0
if True: # k < n:
    for i in range(k+1):
        #print("--------------")
        r = k-i
        #print(i,r)
        if i > n:
            continue
        for j in range(-1,i):
            temp = []
            for l in range(i):
                #print(j-l)
                temp.append(vs[j-l])
            temp.sort()
            #print(temp)
            for _ in range(r):
                if len(temp) == 0:
                    break
                if temp[0] < 0:
                    temp.pop(0)
                else:
                    break
            ss = sum(temp)
            ans = max(ans, ss)


print(ans)

Submission status: Accepted

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

for i in range(K+1):
    j = K - i
    for k in range(i+1):
        value = []
        for l in range(N):
            if (l < k or l >= N-(i-k)):
                value.append(V[l])
        value = sorted(value)
        deleteList = []
        for l in range(min(j, len(value))):
            if (value[l] < 0):
                deleteList.append(l)
        sm = 0;
        for l in range(len(value)):
            if l not in deleteList:
                sm += value[l]
        if (sm > mx):
            mx = sm
print(mx)

Submission status: Accepted

Solution code:
import sys,heapq
from collections import deque,defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True  and False
def ddprint(x):
  if DBG:
    print(x)

n,k = inm()
v = inl()

#vsuml = [0] * n
#for i in range(n):
#    vsuml[i] = vsuml[i-1]+v[i]

#vsumr = [0] * n
#vsumr[n-1] = v[n-1]
#for i in range(n-2,-1,-1):
#    vsumr[i] = vsumr[i+1]+v[i]

maxsum = 0
maxi = min(n,k)
for i in range(1,maxi+1):
    for il in range(i+1):
        ir = i-il  # il from left, ir from right
        x = []
        for j in range(il):
            x.append(v[j])
        for j in range(ir):
            x.append(v[n-1-j])
        x.sort()
        rmmax = min(k-i,i-1)
        for j in range(rmmax):
            if x[j]>0:
                rmmax = j  # first j are negative
                break
        #sum = (vsuml[il] if il>0 else 0) + (vsumr[n-ir+1] if ir>0 else 0)
        sum0 = sum(x[rmmax:])
        ddprint("il {} ir {} rm {} sum {}".format(il,ir,rmmax,sum0))
        if sum0 > maxsum:
            maxsum = sum0
        if i==n:
            break

print(maxsum)

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):#左から何個とるか
    if i > K:
        break
    for j in range(N + 1):#右から何個とるか
        if i + j > N or i + j > K:
            break
        for l in range(N + 1):#何個捨てるか
            if i + j + l > K:
                break
            a = V[:i] + V[N-j:]
            a.sort()
            s = sum(a[l:])
            ans = max(ans, s)
print(ans)

Submission status: Accepted

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

    
maxv=0
for i in range(1,min(K+1,len(v)+1)):
    for j in range(0,i+1):
        l=v[0:j]
        r=v[N-(i-j):]
        my=l
        my.extend(r)
        my=sorted(my)
        for k in range(0,min(K-i,len(my))):
            if my[k]<0:
                my[k]=0
            else:
                break
        if maxv<sum(my):
            maxv=sum(my)
print(maxv)

Submission status: Accepted

Solution code:
from itertools import accumulate

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

dpl, dpr = [-10 ** 9] * (k + 1), [-10 ** 9] * (k + 1)
dpl[0] = dpr[0] = 0

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

vvv.reverse()

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

# print(dpl)
# print(dpr)
acl = list(accumulate(dpl, func=max))
acr = list(accumulate(dpr, func=max))
# print(acl)
# print(acr)
ans = 0
for i in range(k + 1):
    ans = max(ans, acl[i] + acr[k - i])
max_ans = sum(v for v in vvv if v > 0)
ans = min(ans, max_ans)
print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
V = list(map(int, input().split()))
INF_MIN = -(10**10)
l = [[INF_MIN] * (K+1) for i in range(N+1)]
r = [[INF_MIN] * (K+1) for i in range(N+1)]

pop_sum = 0
for i in range(N+1):
    if i == 0:
        pop_sum = 0
        l[i][0] = 0
        r[i][0] = 0
        popV = []
    else:
        pop_sum += V[i-1]
        popV = list(sorted(V[0:i]))
        l[i][0] = pop_sum
    for k in range(1, K+1):
        if not (k-1 < len(popV)) or popV[k-1] > 0:
            l[i][k] = l[i][k-1]
        else:
            l[i][k] = l[i][k-1] - popV[k-1]

pop_sum = 0
for i in range(N+1):
    if i == 0:
        pop_sum = 0
        r[i][0] = 0
        popV = []
    else:
        pop_sum += V[N-i]
        popV = list(sorted(V[N-i:N]))
        r[i][0] = pop_sum
    for k in range(1, K+1):
        if not (k-1 < len(popV)) or popV[k-1] > 0:
            r[i][k] = r[i][k-1]
        else:
            r[i][k] = r[i][k-1] - popV[k-1]

#print(l)
#print(r)

max_val = INF_MIN
imax = min(N, K)
for i in range(imax+1):
    for k in range(K-i+1):
        jmax = min(N-i, K-i-k)
        for j in range(jmax+1):
            val = l[i][k] + r[j][K-i-k-j]
            if val > max_val:
                max_val = val
                #print(i, j, k, l[i][k], r[j][K-i-k-j])


print(max_val)

Submission status: Accepted

Solution code:
inf = - (10 ** 9)
n, k = map(int, input().split())
v = [int(i) for i in input().split()]
ans = inf
for left in range(k + 1):
    for right in range(k - left + 1):
        back = k - left - right
        if left + right <= n:
            vv = v[:left] + v[n - right:]
        else:
            vv = v
        vv.sort()
        if len(vv) > 0:
            back = k - left - right
            under_zero = len([v_i for v_i in vv if v_i < 0])
            if back <= under_zero:
                ans = max(sum(vv[back:]), ans)
            else:
                if (back - under_zero) % 2 == 1:
                    ans = max(sum(vv[under_zero:]), ans)
                else:
                    ans = max(sum(vv[under_zero - 1:]), ans)
print(ans)