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 sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque, defaultdict
#deque(l), pop(), append(x), popleft(), appendleft(x)
#q.rotate(n)で → にn回ローテート
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import reduce,lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("## ",*x,file=sys.stderr)
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reverse=True)  #二個目の要素で降順並び替え

    #N = int(input())
    N, K = map(int, input().split())
    #
    vs = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    ans=0
    ls=0
    dlis1=[]
    for l in range(min(N,K)+1):
        rs=0
        dlis2=[]
        if l>=1:
            tag=vs[l-1]
            ls+=tag
            if tag<0:
                dlis1.append(tag)
        for r in range(min(K-l,N)+1):
            if r>=1:
                tag=vs[-1-r+1]
                rs+=tag
                if tag<0:
                    dlis2.append(tag)
            dlis=dlis1+dlis2
            dlis.sort()
            td=0
            
            dec =min(K-l-r,len(dlis))
            if dec>=1:
                td=sum(dlis[:dec])
            tot=ls+rs-td
            #printe(l,ls,r,rs,dec,td)
            ans=max(ans,tot)

            if l+r>=N:
                break

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import heapq
import itertools
def main():
    n,k=map(int, input().split())
    v=[int(i) for i in input().split()]
    #k回Vの両端から取り出したり詰めたりして持ってるものの価値の最大化をする
    v_1 = v[::-1]
    #左から取る回数をA、右から取る回数をBとしたとき、価値が負の宝石を捨てる操作は（k-(A+B)）回できる
    #これを利用して全探索
    res = 0
    for i in range(k+1):
        j = 0
        while(i+j<=min(n,k)):

            q = []
            tmp = 0
            if(i>0):
                for l in range(i):
                    if(v[l]<0):
                        heapq.heappush(q,v[l])
                    tmp += v[l]
            if(j>0):
                for l in range(j):
                    if(v_1[l]<0):
                        heapq.heappush(q,v_1[l])
                    tmp += v_1[l]
            for l in range(k-(i+j)):
                if(len(q)>0):
                    z = heapq.heappop(q)
                    tmp -= z
            j+=1
            res = max(res,tmp)

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

Submission status: Accepted

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

ans = - 10 ** 19
# i: Dから取り出す宝石の個数
for i in range(min(k + 1, n + 1)):
  # j: 左からとる個数(i-jが右からとる個数)
  for j in range(i + 1):
    inhands = V[:j] + V[n - i + j:]
    inhands.sort()
    remnum = k - i
    val = 0
    for h in inhands:
      if h < 0 and remnum > 0:
        remnum -= 1
      else:
        val += h
    ans = max(ans, val)
print(ans)

Submission status: Accepted

Solution code:
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from math import factorial, sqrt, ceil, gcd
from functools import lru_cache, reduce
from decimal import Decimal
from operator import mul

INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)


# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# 組合せnCr
def combinations_count(n, r):
    if n < r:
        return 0
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# 素数判定
def is_prime(n):
    if n <= 1:
        return False
    p = 2
    while True:
        if p ** 2 > n:
            break
        if n % p == 0:
            return False
        p += 1
    return True


# limit以下の素数を列挙
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

# 同じものを含む順列
def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

# ここから書き始める
n, k = map(int, input().split())
v = list(map(int, input().split()))

ans = -INF
for i in range(k + 1):
    for j in range(k + 1):
        if i + j > k or i + j > n:
            continue
        x = v[:i] + v[n - j:]
        x.sort()
        cnt = sum(x)
        for l in range(min(k - i - j, i + j)):
            if x[l] >= 0:
                break
            cnt -= x[l]
        ans = max(ans, cnt)
print(ans)

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7


#############
# Main Code #
#############

N, K = getNM()
V = getList()

V = 2 * V

ans = 0
for i in range(1, min(K + 1, N + 1)):
    slow = K - i
    for j in range(N - i, N + 1):
        opt = sorted(V[j: j + i])
        for l in range(min(len(opt), slow)):
            if opt[l] < 0:
                opt[l] -= opt[l]
        ans = max(ans, sum(opt))
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()))
ans = 0
for i in range(n+1):
    for j in range(n+1):
        if i+j > n or i+j > k:
            continue
        p = v[:]
        d = deque(p)
        a = []
        heapq.heapify(a)
        for t in range(i):
            heapq.heappush(a,d.popleft())
        for l in range(j):
            heapq.heappush(a,d.pop())
        nokori = k-i-j
        for s in range(nokori):
            if a:
                now = heapq.heappop(a)
                if now > 0:
                    heapq.heappush(a,now)
                    break
            else:
                break
        ans = max(ans,sum(a))
print(ans)

Submission status: Accepted

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

ans = -1

for l in range(N+1):
    for r in range(N+1):
        tmp = V[:l] + V[N-r:]
        if l+r > N:
            break
        res = K - (l+r)
        if res < 0:
            break
        tmp.sort()
        for i in range(min(res,len(tmp))):
            if tmp[0] < 0:
                tmp.pop(0)
            else:
                break
        ans = max(ans,sum(tmp))
            
print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
V = [int(i) for i in input().split()]
ans = 0
for M in range(K+1):
    for m in range(M+1):
        ls = []
        for i, x in enumerate(V):
            if i < m:
                ls.append(x)
        for i, x in enumerate(V[::-1]):
            if i < min(M-m, N-m):
                ls.append(x)
        ls.sort()
        s = sum(ls)
        for i, x in enumerate(ls):
            if i < K-M and x < 0:
                s -= x
        ans = max(ans, s)
print(ans)

Submission status: Accepted

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
from collections import defaultdict
from collections import deque
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)


#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####GCD#####
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i])*n**i for i in range(len(str(X))))

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N,K = IL()
V = IL()

def dig(L,d):
  N = len(L)
  dic = [[0,[]]]
  for l in L:
    if l>=0:
      dic.append([dic[-1][0]+l,dic[-1][1]])
    else:
      dic.append([dic[-1][0],dic[-1][1]+[l]])
  MAX = 0
  for i in range(N+1):
    dic[i][1].sort(reverse=True)
  for i in range(d+1):
    i = min(i,N)
    MAX = max(MAX,dic[i][0]+sum(dic[i][-1][:max(0,len(dic[i][-1])-(d-i))]))
  return MAX
  
MAX = 0
for i in range(N+1):
  for k in range(K+1):
    MAX = max(MAX,dig(V[:i],k)+dig(V[i:][::-1],K-k))
  
print(MAX)

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right

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

ans = 0
for get_num in range(0,k+1):
    rem = k-get_num
    for l in range(0,get_num+1):
        r = get_num-l
        if l+r > n: continue
        ls = vl[:l]
        rs = vl[n-r:]
        curr_l = ls + rs
        curr_l.sort()
        minus_cnt = bisect_left(curr_l, 0)
        if minus_cnt <= rem:
            curr_ans = sum(curr_l[minus_cnt:])
            ans = max(curr_ans,ans)
        else:
            curr_ans = sum(curr_l[rem:])
            ans = max(curr_ans,ans)

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(n+1):
    for j in range(n-i+1):
        if k < i+j:
            continue
        memo = v[:i] + v[n-j:]
        memo.sort()

        for _ in range(k-i-j):
            if memo and memo[0] < 0:
                memo.pop(0)
            else:
                break
        res = max(res,sum(memo))
print(res)

Submission status: Accepted

Solution code:
import copy

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

ans = 0

for l in range(0,n+1):
    for r in range(0,n+1):
        if l+r > n or l+r > k or l+r==0:
            continue
        vc = copy.deepcopy(v)
        have = []
        ll = copy.deepcopy(l)
        rr = copy.deepcopy(r)
        while ll:
            tmp = vc.pop(0)
            have.append(tmp)
            ll -= 1
        while rr:
            tmp = vc.pop(-1)
            have.append(tmp)
            rr -= 1
        have.sort()
        kk = copy.deepcopy(k)
        while have[0] < 0 and kk-(l+r) > 0:
            tmp = have.pop(0)
            kk -= 1
            if not have:
                break
        ans = max(ans, sum(have))
print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
v = [int(i) for i in input().split()]
ans = 0
for a in range(min(n, k) + 1):
    pa, va = v[:a], v[a:]
    for b in range(min(n, k) - a + 1):
        pb = pa + va[-b:] if b > 0 else pa
        pb.sort()
        s = sum(pb)
        ans = max(s, ans)
        for c in range(min(k - a - b, a + b)):
            s -= pb[c]
            ans = max(s, ans)
print(ans)

Submission status: Accepted

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

ans=0
for i in range(1,k+1): # iは抜き取り回数
    if i<n:
        for left in range(0,i+1): # 左からleft個目まで抜き取る
            tmp=0
            tmpq=[]
            right=i-left
            if right==0:
                right=-n
            tmpq+=q[:left]+q[-right:]
            tmp+=sum(tmpq)
            tmpq=[x for x in tmpq if x<0]
            tmpq=sorted(tmpq)
            tmp-=sum(tmpq[:min(k-i, len(tmpq))])
            ans=max(ans,tmp)
    else:
        for left in range(0,n+1):
            tmp=0
            tmpq=[]
            right=n-left
            if right==0:
                right=-n
            tmpq+=q[:left]+q[-right:]
            tmp+=sum(tmpq)
            tmpq=[x for x in tmpq if x<0]
            tmpq=sorted(tmpq)
            tmp-=sum(tmpq[:min(i-n, len(tmpq))])
            ans=max(ans,tmp)
print(ans)

Submission status: Accepted

Solution code:
import math
from collections import deque
n,k=map(int,input().split())
v=list(map(int,input().split()))
#k回までだったー誤読
ans=0
for i in range(1,min(k,n)+1):
    #取るところ(大きい方とは限らないのか)
    for m in range(i+1):
        s=v[:m]+v[n-(i-m):]
        s.sort()
        #取った個数より多く詰めようとしないように！
        #残りk-i回ある
        for j in range(i,min(k,2*i)):#それ以上詰められない場合
            #0より小さい場合は書き換える
            if s[j-i]<0:s[j-i]=0
        #取り出したやつの最大(戻す場合は0)
        ans=max(ans,sum(s))
        #残りk-j回ある(breakの時のjはやってないので)
        #ここからはいい感じに出すのと入れるのを繰り返す(偶数の場合はこのままか)
        #必要すらない、k回を使い切らなくていいので
        #print(sum(s))
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
from collections import deque
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
from heapq import heapify, heappop, heappush
# import numpy as np
# from numpy import cumsum  # accumulate

def solve():
    N, K = MI()
    V = LI()
    max_iter = min(N, K)
    ans = 0
    for a in range(max_iter+1):
        left = V[:a]
        for b in range(0, max_iter-a+1):
            right = V[-b:] if b != 0 else []
            k = K - a - b
            # print(a, b, k)
            # print(left, right)
            lst = sorted(left + right)
            # print(lst)
            sm = sum(lst)
            l = len(lst)
            for kk in range(1, k+1):
                if kk < l:
                    tmp = lst[kk-1]
                    if tmp >= 0: break
                    sm -= tmp
                    # print(tmp)
                else:
                    break
            ans = max(ans, sm)
    print(ans)


if __name__ == '__main__':
    solve()

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):
        if i + j <= k and i + j <= n:
            g = v[:i] + v[n-j:]
            g.sort()
            for l in range(min(k-i-j, i+j)+1):
                ans = max(ans, sum(g[l:]))

print(ans)

Submission status: Accepted

Solution code:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
# list(map(int, list(input()))) # スペースがない数字リストを読み込み
import math
import fractions
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
import collections
from collections import Counter
from collections import deque
import pprint

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""


def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr


# a^n
def power(a, n, mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod


# n*(n-1)*...*(l+1)*l
def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n - 1
    while (tmp >= l):
        a = a * tmp % mod
        tmp -= 1
    return a


inf = 10 ** 18
mod = 10 ** 9 + 7

n,k = lr()
v = lr()
v2 = [0]
for i in range(n):
    v2.append(v2[-1]+v[i])
def sumArea(l,r):
    return v2[r]-v2[l]
ans = -inf
for tmp in range(min(k,n)+1):
    for r in range(tmp+1):
        minus = []
        for num in v[:tmp-r]:
            if num < 0:
                minus.append(num)
        for num in v[n-r:]:
            if num < 0:
                minus.append(num)
        pre = sumArea(0,tmp-r) + sumArea(n-r,n)
        l = min(tmp,k-tmp,len(minus))
        if minus:
            minus.sort()
            pre -= sum(minus[:l])
        ans = max(ans,pre)
print(ans)

Submission status: Accepted

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

ans = []
# きっちりK回しなくていいみたい
for left in range(N + 1):
    for right in range(N + 1):
        if left + right > N:
            break

        li = V[:left] + V[N - right :]
        li = sorted(li)

        d = K - left - right
        if d < 0:
            break

        c = sum(li)
        for i in range(min(d, len(li))):
            if li[i] < 0:
                c -= li[i]
            else:
                break

        ans.append(c)

print(max(ans))

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

vals = []
for L in range(N+1):
    for R in range(N+1):
        if L+R > N:
            break
        get = V[:L] + V[N-R:]
        rest = K - (L+R)
        if rest < 0:
            break
        get.sort(reverse=True)
        for _ in range(min(len(get),rest)):
            if get[-1] < 0:
                get.pop()
            else:
                break
        vals.append(sum(get))

answer = max(vals)
print(answer)

Submission status: Accepted

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

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

ans = -float("inf")

#i: 左から取る回数
for i in range(targ+1):
    #j: 右を取る回数
    for j in range(targ+1-i):
        get = sorted(V[:i] + V[N-j:])
        tmp = sum(get)
        for k in range(min(K-i-j, i+j)):
            tmp = max(tmp, tmp-get[k])
        
        ans = max(tmp, ans)

print(ans)

Submission status: Accepted

Solution code:
n,k=[int(x) for x in input().rstrip().split()]
v=[int(x) for x in input().rstrip().split()]
vr=v[::-1]
ans=0
mi=min(n,k)

for i in range(mi+1):
  for j in range(mi-i+1):
    minus=0
    now=v[:i]+vr[:j]
    d=k-(len(now))
    now.sort()
    md=min(d,len(now))
    for s in range(md):
      if 0<=now[s]:
        break
      minus+=now[s]

    ans=max(ans,sum(now)-minus)
print(ans)

Submission status: Accepted

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

selected = []
left = []

max_sum = 0
left_sum = 0
for l in range(N):
    selected = copy.deepcopy(left)
    lr_sum = left_sum
    for r in range(N-l+1):
        # skip
        stock = K-l-r
        if stock < 0:
            break
        ri = N-r-1
        select_cnt = len(selected)
        tmp_sum = lr_sum
        max_sum = max(max_sum, tmp_sum)
        popper = copy.deepcopy(selected)

        for i in range(stock):
            if i >= select_cnt:
                break
            
            pop_v = heapq.heappop(popper)
            if pop_v > 0:
                break
            tmp_sum -= pop_v
            max_sum = max(max_sum, tmp_sum)

        r_val = V_list[ri]
        lr_sum += r_val
        heapq.heappush(selected, r_val)

    l_val = V_list[l]
    left_sum += l_val
    heapq.heappush(left, l_val)

print(max_sum)

Submission status: Accepted

Solution code:
# 初期入力
import bisect
import heapq
import sys
input = sys.stdin.readline
N,K = (int(i) for i in input().split())
V = list(map(int, input().split()))
V_sorted =sorted(V)

#取る個数take_num、返す個数reverse(t +r <=K)個全て決める

ans =[]
take_V =[] #最後に持っている宝石の価値
#Vが全てマイナスなら取らない
if V_sorted[-1] <=0:
    ans =0
else:
    take_num =min(K,N)
    for tak in range(1,take_num +1):
        for lef in range(tak+1):
            #for rev in range(reverse +1):
            
                take =[]  #取った宝石
                rig =N-(tak -lef )          #lef:左側の取る数 rig:右側の取る数
                take.extend(V[    :lef])
                take.extend(V[rig:   ])
                take.sort()
                reverse =min(K -tak,tak) #返す数はtake_numではなく、Kから引く
                ind_0 =bisect.bisect_left(take,0)
                rev =min(ind_0,reverse,K -tak)
                take_V.append(sum(take[rev:])) #返す分を除く
        
    ans =max(take_V)
print(ans)

Submission status: Accepted

Solution code:
# 初期入力
import bisect
import sys
input = sys.stdin.readline
N,K = (int(i) for i in input().split())
V = list(map(int, input().split()))
V_sorted =sorted(V)

#取る個数take_num、返す個数reverse(t +r <=K)個全て決める

ans =[]
take_V =[] #最後に持っている宝石の価値
#Vが全てマイナスなら取らない
if V_sorted[-1] <=0:
    ans =0
else:
    take_num =min(K,N)
    for tak in range(1,take_num +1):
        reverse =min(K -tak,tak) #返す数はtake_numではなく、Kから引く
        for lef in range(tak+1):
            for rev in range(reverse +1):
            
                take =[]                    #取った宝石
                rig =N-(tak -lef )          #lef:左側の取る数 rig:右側の取る数
                take.extend(V[    :lef])
                take.extend(V[rig:   ])
                take.sort()
                take_V.append(sum(take[rev:]))
        
    ans =max(take_V)
print(ans)

Submission status: Accepted

Solution code:
n, k = map(int,input().split())
targ = min(n, k)
v = list(map(int,input().split()))
"""
i…左を取る回数
j…右を取る回数
残り回数 k-(i+j)
"""
ans = -10**18
for i in range(targ+1):
	for j in range(targ-i+1):
		#print(i, j)
		nl = v[:i] + v[n-j:]
		nl.sort()
		#print(nl)
		tmp = sum(nl)
		for t in range(min(k-(i+j), i+j)):
			tmp = max(tmp, tmp-nl[t])
			#print("行いましたよ!")
		#print(tmp)
		ans = max(tmp, ans)
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(k+1):
  for j in range(k+1):
    if i+j > k or i+j > n:
      continue
    t = k-(i+j)
    s = v[:i] + v[(n-j):]
    s.sort()
    u = 0
    # print (s,t)
    while u < t:
      u += 1
      if len(s) < 1:
        break
      if s[0] < 0:
        s.pop(0)
      else:
        break
    ans = max(ans, sum(s))
print (ans)