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
input=sys.stdin.readline
from collections import deque
from heapq import heappush,heappop
import re

def int_raw():
    return int(input())
 
def ss_raw():
    return input().split()
 
def ints_raw():
    return tuple(map(int, ss_raw()))


def main():
    N ,K = ints_raw()
    Vs = ints_raw()
    N = len(Vs)
    leftSum = [0]
    leftNegas = [[]]
    for v in Vs:
        leftSum.append(leftSum[-1]+v)
        neoNega = leftNegas[-1]
        if v<0:
            neoNega = neoNega+[v]
            neoNega.sort()
        leftNegas.append(neoNega )


    rightSum = [0]
    rightNegas = [[]]
    for v in Vs[::-1]:
        rightSum.append(rightSum[-1]+v)
        neoNega = rightNegas[-1]
        if v<0:
            neoNega = rightNegas[-1]+[v]
            neoNega.sort()
        rightNegas.append(neoNega )

    ans = 0
    for left_k in range(K+1):
        left_total = 0
        left_n = 0
        for n in range(min(N+1,left_k+1)):
            tmp = leftSum[n] - (sum(leftNegas[n]) if len(leftNegas[n])<=left_k-n else sum(leftNegas[n][:left_k-n]))
            if left_total < tmp:
                left_total = tmp
                left_n = n
        right_total = 0
        right_n = 0
        right_k = K -left_k
        for n in range(min(K-left_k+1,N-left_n+1)):
            tmp = rightSum[n] - (sum(rightNegas[n]) if len(rightNegas[n])<=right_k-n else sum(rightNegas[n][:right_k-n]))
            if right_total < tmp:
                right_total = tmp
                right_n = n
        ans = max(ans,left_total+right_total)
    return ans

print(main())

Submission status: Accepted

Solution code:
def run(N, K, V):
    ret = 0
    for L_get in range(K+1):
        for R_get in range(K-L_get+1):
            if L_get + R_get > N:
                break
            for Leave in range(K-L_get-R_get+1):
                if Leave > L_get + R_get:
                    break
                if L_get == 0:
                    L_lists = []
                else:
                    L_lists = V[:L_get]
                if R_get == 0:
                    R_lists = []
                else:
                    R_lists = V[-R_get:]
                lists = L_lists + R_lists
                sorted_lists = sorted(lists)
                ret = max(ret, sum(lists) - sum(sorted_lists[:Leave]))
    return ret


def main():
    N, K = map(int, input().split())
    V = list(map(int, input().split()))
    print(run(N, K, V))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

from itertools import accumulate
Lcumsum = [0] + list(accumulate(V))
Rcumsum = [0] + list(accumulate(V[::-1]))
#print(Lcumsum)
#print(Rcumsum)

ans = 0
               
for l in range(min(N,K)+1):
  for r in range(min(N-l,K-l)+1):
    Lsum = Lcumsum[l]
    Rsum = Rcumsum[r]
    Nsum = sum(sorted([v for v in (V[:l] + V[N-r:]) if v<0])[:K-l-r])
    ans = max(ans, Lsum+Rsum-Nsum)
    #print(l,r,Lsum,Rsum,Nsum,Lsum+Rsum-Nsum)
    
print(ans)

Submission status: Accepted

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

max_score = 0
for i in range(N+1):
    # print(list(range(i, N+1)))
    for j in range(i, N+1):
        # print(i, j)
        p = V[:i] + V[j:] 
        # print(p)
        if len(p) > K:
            continue
        p.sort(reverse=True)
        for _ in range(K-len(p)):
            if p and p[-1]<0:
                p.pop()
            else:
                break
        score = sum(p)
        # print(p)
        max_score = max(max_score, score)

print(max_score)

Submission status: Accepted

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

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

    mani = []
    for ac in range(K+1):
        for bc in range(K+1):
            for cc in range(K+1):
                if (ac+bc+cc) == K:
                    mani.append([ac,bc,cc])

    max_v = 0
    for m in mani:
        VV = deque(V)
        MV = []
        lenVV = len(VV)
        for i in range(min(m[0],lenVV)):
            MV.append(VV.popleft())

        lenVV = len(VV)
        for i in range(min(m[1],lenVV)):
            MV.append(VV.pop())

        MV.sort()
        MV = deque(MV)
        for i in range(m[2]):
            if len(MV) > 0 and MV[0] < 0:
                MV.popleft()

        max_v = max(max_v,sum(MV))

    print(max_v)



            



# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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:
n, k = list(map(int, input().split()))
v = list(map(int, input().split()))

total_all = []
for a in range(min(n, k) + 1):
    for b in range(min(k - a, n - a) + 1):
        if b == 0:
            tmp = v[:a]
        else:
            tmp = v[:a] + v[-1 * b:]
        tmp.sort()

        n_tmp_negative = sum(1 for x in tmp if x < 0)
        cd = k - a - b
        if cd > 0:
            total = sum(tmp[min(cd, n_tmp_negative):])
        else:
            total = sum(tmp)

        total_all.append(total)
print(max(total_all))

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
V = [int(x) for x in input().split()]
L = [[] for i in range(K + 1)]
R = [[] for i in range(K + 1)]
for i in range(1, K + 1):
  L[i] = sorted(V[:i])
  R[i] = sorted(V[-i:], reverse=True)
ans = 0
for l in range(min(N, K) + 1):
  for r in range(min(N, K) + 1 - l):
    LR = L[l] + R[r]
    k = K - l - r
    while k > 0:
      if len(LR) and LR[0] <= LR[-1] and LR[0] < 0:
        LR.pop(0)
      elif len(LR) and LR[-1] <= LR[0] and LR[-1] < 0:
        LR.pop(len(LR) - 1)
      k -= 1
    ans = max(sum(LR), ans)
print(ans)

Submission status: Accepted

Solution code:
import bisect

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

ans = 0

if N < K :
    pp = K
    K = N
else :
    pp = K
for a in range(1,K+1) :
    for i in range(a+1) :
        G = []
        G.extend(V[:i])
        G.extend(V[len(V)-(a-i):])
        G.append(0)
        G = sorted(G)
        #bi = bisect.bisect(G,0)
        #G = G[min(bi-1,K-a):]

        cnt = 0
        calc = 0
        for i in range(len(G)) :
            if G[i] < 0 :
                if cnt < pp-a :
                    cnt += 1
                else :
                    calc += G[i]
            else :
                calc += G[i]


        ans = max(ans,calc)

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
import numpy as np
# n = int(input())
# a, b = map(int, input().split())
# int_list = list(map(int, input().split()))
# l = list(input().split())

def solve():
    n, k = map(int, input().split())
    v_list = list(map(int, input().split()))

    temoti_max = 0
    for i in range(k+1):
        for j in range(min(k+1-i, n-i+1)):
            #print(v_list)
            temoti_list = []
            temoti_list +=  v_list[:i]
            #print(i, j)
            #print(temoti_list)
            temoti_list += v_list[n-j:]
            #print(temoti_list)
            temoti_list.sort()
            #print(temoti_list)

            temoti = sum(temoti_list)
            for iret in range(min(len(temoti_list), k-i-j)):
                if temoti_list[iret] < 0:
                    temoti -= temoti_list[iret]

            if temoti_max <= temoti:
                temoti_max = temoti

    print(temoti_max)

solve()

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
v = list(map(int, input().split()))
ans = 0
for l in range(n + 1):
	for r in range(l, max(n, l + 1)):
		o = v[:l] + v[r + 1:]
		if len(o) > k:
			continue
		o.sort()
		i = 0
		while i < len(o) and i < k - len(o) and o[i] < 0:
			i += 1
		ans = max(ans, sum(o[i:]))
		# print("%d %d: %s, %d, %d" % (l, r, str(o), i, ans))
print(ans)

Submission status: Accepted

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


v = list(map(int,input().split()))
res = -(10**-12)
#left
for left in range(min(n+1,k+1)):
    for right in range(min(n-left+1,k-left+1)):
        if right == 0:
            s = v[:left]
        else:
            s=v[:left]+v[-right:]
        s.sort()
        r = 0
        cnt = 0
        bound = k-left-right
        for i in s:
            if i<0 and cnt<bound:
                cnt+=1
            else:
                r+=i
        res = max(res,r) 
print(res)

Submission status: Accepted

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

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

m = 0

for i in range(n + 1):

    for j in range(n, i - 1 , -1):

        temp = sorted(v[:i] + v[j:], reverse = True)

        count = len(temp)

        if count > k:
            break

        while temp and count < k and temp[-1] < 0:

            temp.pop()

            count += 1

        m = max(m, sum(temp))

print(m)

Submission status: Accepted

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

ans = -1e+7
for n_get in range(1, min(N, K) + 1):
    n_remove = min(n_get, K-n_get)
    for n_front in range(n_get + 1):
        got = V[:n_front] + V[N-n_get+n_front:]
        got.sort()
        if n_remove > 0:
            if got[n_remove-1] < 0:
                got = got[n_remove:]
            else:
                got = [g for g in got if g > 0]
        ans = max(ans, sum(got))
print(ans)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
V = list(map(int,input().split()))
import heapq
ans = -float('inf')
for i in range(min(N+1,K+1)):
    for j in range(min(N-i+1,K-i+1)):
        A = V[:i]
        B = V[N-j:]
        AB = A + B
        heapq.heapify(AB)
        k = 1
        c = 0
        s = 0
        while i+j+k<=K and len(AB)>0:
            c = heapq.heappop(AB)
            if  c >= 0:
                break
            k += 1
        s = sum(AB)
        if c >= 0:
            s += c
        ans = max(ans,s)
print(ans)

Submission status: Accepted

Solution code:
import heapq
n,k=map(int,input().split())
V=[int(i) for i in input().split()]
M=sum(v for v in V if v>=0)
A=[[0,0]]
for i in range(1,n):
  VS=V[:i]
  cost=i
  A.append([cost,sum(VS)])
  heapq.heapify(VS)
  for _ in range(i):
    cost+=1
    heapq.heappop(VS)
    A.append([cost,sum(VS)])
B=[[0,0]]
V=V[::-1]
for i in range(1,n):
  VS=V[:i]
  cost=i
  B.append([cost,sum(VS)])
  heapq.heapify(VS)
  for _ in range(i):
    cost+=1
    heapq.heappop(VS)
    B.append([cost,sum(VS)])
ans=-float("inf")
for a in A:
  for b in B:
    if a[0]+b[0]<=k:
      ans=max(ans,a[1]+b[1])
print(M if n==1 else min(ans,M))

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

N,K = inpl()
vv = inpl()

ans = 0
for lnum in range(K+1):
    for rnum  in range(K-lnum+1):
        if lnum + rnum > N:
            continue
        torukazu = vv[:lnum] + vv[N-rnum:]
        torukazu.sort()
        #print(' ' , torukazu,lnum,rnum)
        for sute in range(K-lnum-rnum+1):
            #print(torukazu[sute:])
            tmp = sum(torukazu[sute:])
            ans = max(tmp,ans)

print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
v=list(map(int,input().split()))
ma=0
for i in range(k//2+1):
     pick=min(k-i,n)
     for j in range(pick+1):
          if j==0:
               l=v[:pick]
               al=l
          elif j==pick:
               r=v[-pick:]
               al=r
          else:
               l=v[:pick-j]
               r=v[-j:]
               al=l+r
          for rem in range(i):
               if len(al)>0:
                    mi=min(al)
                    if mi<0:
                         al.remove(mi)
                    else:
                         break
               else:
                    break
          if len(al)>0:
               ma=max(ma,sum(al))
print(ma)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
v_list=list(map(int,input().split()))
ans=0
for i in range(min(k+1,n+1)):
    for j in range(min(k-i+1,n-i+1)):
        List=v_list[:i]+v_list[n-j:]
        Sum=sum(List)
        List.sort()
        count=k-i-j
        x=0
        if List==[]:
            Sum=0
        else:
            while not count==0 and List[x]<0:
                Sum=Sum-List[x]
                count=count-1
                x=x+1
                if x==len(List):
                    break
        ans=max(ans,Sum)
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(min(N, K) + 1):
    for j in range(i + 1):
        h = v[:j] + (v[-(i - j):] if i != j else [])
        k = K - i
        tmp = sum(h)
        for m in range(i):
            h.sort()
            if k > 0 and h[m] < 0:
                k -= 1
                tmp -= h[m]
        ans = max(ans, tmp)
print(ans)

Submission status: Accepted

Solution code:
import bisect

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

res = -10**10
for x in range( min(k+1,n+1) ):
    for l in range(x+1):
        r = x-l
        tras = k-x
        get = sorted(v[:l] + (v[-r:] if r!=0 else []))
        
        idx_0 = bisect.bisect_left(get,0)
        if res < sum(get[ min(idx_0,tras) :]):
            res = sum(get[ min(idx_0,tras) :])

print(res)

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(i,n+1):
        a = v[:i]+v[j:]
        if len(a)>k:
            continue
        else:
            a.sort()
            a.reverse()
            for l in range(k-len(a)):
                if len(a)>0 and a[-1]<0:
                    a.pop()
                else:
                    break
            ans = max(ans, sum(a))
print(ans)

Submission status: Accepted

Solution code:
n,k = [int(i) for i in input().split()]
d = [int(i) for i in input().split()]
ans = 0
for en in range((k//2)+1):
    if en > n:
        break
    if k-en > n:
        tmp = d[:]
        tmp.sort()
        ans = max(ans, sum(tmp[en:]))
        continue
    for dl in range(k-en+1):
        tmp = d[:dl]+d[n-(k-en-dl):]
        tmp.sort()
        for j in range(en+1):
            ans = max(ans, sum(tmp[j:]))
print(ans)

Submission status: Accepted

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

def readInts():
  return [int(s) for s in input().split(" ")]

def max_val(V, n):
  count = n
  ret = 0
  for v in sorted(V):
    if v < 0 and count > 0:
      count -= 1
    else:
      ret += v
  return ret

def main():
  N, K = readInts()
  V = readInts()

  ans = 0

  for KL in range(K+1):
    KR = K - KL
    for L in range(min(KL, N)+1):
      for R in range(min(KR, N-L)+1):
        left = V[:L]
        right = V[-1 * R:] if R > 0 else []
        s = max_val(left, KL - L) + max_val(right, KR - R)
        ans = max(ans, s)

  print(ans)

if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys
import math
import collections

N, K = map(int, sys.stdin.readline().rstrip().split(" "))
Vs = list(map(int, sys.stdin.readline().rstrip().split(" ")))
result = 0
for L in range(min(N + 1, K + 1)):
    for R in range(min(N + 1 - L, K + 1 - L)):
        gems = Vs[:L]
        if R > 0:
            gems += Vs[-R:]

        gems.sort()
        rest = K - L - R
        # print(L, R, gems)
        for _ in range(rest):
            if len(gems) > 0 and gems[0] < 0:
                gems.pop(0)
            else:
                break
        # print(gems, sum(gems))
        result = max(result, sum(gems))
print(result)
exit(0)

Submission status: Accepted

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

dp = [[[False for ___ in range(N+1)] for __ in range(N+1)] for _ in range(K+1)]

dp[0][0][N] = True

for k in range(K):
    for i in range(N+1):
        for j in range(i, N+1):
            if j+1<=N and i-1>=0:
                dp[k+1][i][j] = dp[k][i][j+1] or dp[k][i-1][j]
            elif j+1<N:
                dp[k+1][i][j] = dp[k][i][j+1]
            elif i-1>=0:
                dp[k+1][i][j] = dp[k][i-1][j]
                

ans = 0
for k in range(K+1):
    for n in range(K-k+1):
        for i in range(N+1):
            for j in range(i, N+1):
                if not dp[k][i][j]:
                    continue
                on_hand = D[:i]+D[j:]
                m = len(on_hand)
                if m < n:
                    continue
#                print(on_hand)
#                print(k, i, j, n, sorted(on_hand,reverse=True)[:m-n], sum(sorted(on_hand,reverse=True)[:m-n]))
                ans = max(ans, sum(sorted(on_hand,reverse=True)[:m-n]))
print(ans)

Submission status: Accepted

Solution code:
import sys


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

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

for i in range(1,min(K,N)+1):
    for j in range(i+1):
        x=[v[k] for k in range(j)]+[v[k] for k in range(N-i+j,N)]
        tmp=sum(x)
        x.sort()
        
        for k in range(min(i,K-i)):
            if x[k]<0: tmp-=x[k]

        if tmp>ans: ans=tmp

print(ans)

Submission status: Accepted

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

sV=sorted(V)
ans=0
for i in range(N):
  for j in range(N-i+1):
    if i+j<=K:
      if i+j>=N:
        L=sV
      else:
        L=V[:i]+V[N-j:]
        L.sort()
      k=bisect.bisect_left(L,0)
      kans=sum(L[min(max(0,K-i-j),k):])
      ans=max(ans,kans)
print(ans)

Submission status: Accepted

Solution code:

# N <= 50
# K <= 100



def solve(V, K):
    hiscore = 0
    for k in range(0, K+1):
        lscore = sum(V[:k])
        rV = list(reversed(V[k:]))
        neg = [v for v in V[:k] if v < 0]
        for rk in range(0, K+1-k):
            neg0 = list(neg)
            rscore = lscore + sum(rV[:rk])
            neg0.extend(v for v in rV[:rk] if v < 0)
            score = rscore - sum(sorted(neg0)[:K-k-rk])
            if score > hiscore:
                #print(k, rk)
                hiscore = score
    print(hiscore)


N, K = [int(x) for x in input().split()]
V = [int(x) for x in input().split()]
solve(V, K)

Submission status: Accepted

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

# 何もしないパターン
maxScore = 0
for p in range(K+1):
    # d回戻す
    for l in range(K+1-p):
        if l > N:
            continue
        for r in range(K+1-p-l):
            if l + r > N:
                continue
            d = K  - p - l - r
            if d < 0:
                continue
            if d > l + r:
                continue
            Vs = V[0:l]
            Vs += V[-r:] if r > 0 else []
            Vs.sort()
            score = sum(Vs[d:])
            maxScore = max(score, maxScore)
print(maxScore)

Submission status: Accepted

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

Ans = 0
M = min(N + 1, K + 1)
for i in range(M):
  S = V[:i]
  for j in range(M - i):
    if j == 0:
      P = S
    else:
      P = S + V[-j:]
    t = 0
    T = []
    for k in P:
      t += k
      if k < 0:
        T.append(k)
    T.sort()
    for k in range(min(len(T), K - (i + j))):
      t -= T[k]
    Ans = max(Ans, t)

print(Ans)

Submission status: Accepted

Solution code:
from itertools import product

N, K = map(int, input().split())
V = [int(x) for x in input().split()]

ans = 0
# l: 左から取り出す数
for l, r in product(range(K + 1), repeat=2):
    if l + r == 0 or l + r > N or l + r > K:
        continue

    A = V[:l] + V[N - r:]
    s = sum(A)

    # 入れることができる回数
    a = K - (l + r)
    if a > 0:
        A = sorted(A)
        for i in range(min(a, len(A))):
            if A[i] < 0:
                s -= A[i]
            else:
                break
    ans = max(ans, s)
print(ans)

Submission status: Accepted

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

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

# 左から試していく

left_dict = {0:0}

for i in range(K,0,-1):
    left_dict[i]=max([sum(sorted(V[:i-j])[j:]) for j in range(i//2+1)])

left_dict



V = list(reversed(V))

V

right_dict = {0:0}
for i in range(K,0,-1):
    right_dict[i]=max([sum(sorted(V[:i-j])[j:]) for j in range(i//2+1)])

right_dict

m = 0
for i in range(K+1):
    for j in range(K-i+1):
        if m < left_dict[i]+right_dict[j]:
            m = left_dict[i]+right_dict[j]

            
print(min(m,sum([v for v in V if v>0 ]) ))

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc128/abc128_d
import itertools as it

N, K = map(int, input().split())
vs = [int(s) for s in input().split()]

acc = [0] + list(it.accumulate(vs))
res = 1000000000
for left in range(min(N, K) + 1):
    for right in range(min(N, K) + 1 - left):
        tmp = acc[N - right] - acc[left]
        rem = K - left - right
        rest = sorted(vs[:left] + vs[N - right :])[:rem]

        for x in rest:
            if x < 0:
                tmp += x
        if tmp < res:
            res = tmp

print(acc[-1] - res)

Submission status: Accepted

Solution code:
n, k = map(int, raw_input().split(" "))
v = map(int, raw_input().split(" "))

ans = 0
for k1 in range(0, min(n, k) + 1):
    for k2 in range(0, max(min(k - k1 + 1, n - k1 + 1), 0)):
        k3 = max(0, k - k1 - k2)

        gets = v[0:k1] + v[len(v)-k2:len(v)]
        sort = sorted(gets)

        sum = 0
        for i in range(0, len(sort)):
            if sort[i] < 0 and i <= k3 - 1:
                pass
            else:
                sum += sort[i]

        # if ans < sum:
            # print("%d %d %d" % (k1, k2, sum))
            # print(gets)
        ans = max(sum, ans)

print(ans)

Submission status: Accepted

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

ans = 0
for push_num in range(K // 2 + 1):
    gem_num = K - push_num
    # print("#", push_num, gem_num)
    if gem_num >= N:
        gem_list = list(V)
        gem_list.sort()
        for i_start, gemi in enumerate(gem_list):
            if i_start >= push_num: break
            if gemi > 0: break
        ans_tmp = sum(gem_list[i_start:])
        # print("##", gem_list, ans_tmp)
        if ans < ans_tmp: ans = ans_tmp
        continue
    else:
        for l_num in range(gem_num + 1):
            r_num = gem_num - l_num
            gem_list = []
            for i in range(l_num): gem_list.append(V[i])
            for i in range(r_num): gem_list.append(V[-(r_num - i)])
            gem_list.sort()
            for i_start, gemi in enumerate(gem_list):
                if i_start >= push_num: break
                if gemi > 0: break
            ans_tmp = sum(gem_list[i_start:])
            # print("##", gem_list, ans_tmp)
            if ans < ans_tmp: ans = ans_tmp

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from math import ceil
from itertools import chain

def solve(N: int, K: int, V: "List[int]"):
    # i: num to pick, j: num to pick from left
    ans = -10**10
    for i in range(min(K+1, N+1)):
        max_n = min(K-i, i)
        for j in range(i+1):
            V2 = sorted(chain(V[:j], V[N-(i-j):]))
            k=0
            while True:
                if k>=max_n or V2[k]>=0:
                    break
                k+=1
            ans = max(sum(V2[k:]), ans)
    print(ans)

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:
N,K = map(int,input().split())
V = list(map(int,input().split()))
V_r = list(reversed(V))

ans = 0
for take in range(min(N+1,K+1)):
	for left in range(take+1):
		right = take - left
		jewel = V[:left] + V_r[:right]
		rest = K - take
		jewel.sort()
		tmp = sum(jewel)
		for i in range(min(take,rest)):
			if jewel[i] < 0:
				tmp -= jewel[i]
		ans = max(ans, tmp)
print(ans)

Submission status: Accepted

Solution code:
read = input 
rn = lambda :list(map(int, read().split()))
# O(N^2)
n, k = rn()
V = rn() # 0 ~ n-1
best = 0
for i in range(0, n + 1): # [0, n]
    for j in range(i, n+1): # [i + 1, n]
        # take [0,i), [j, n)
        yes = V[0:i] + V[j: n]
        if len(yes) > k:
            continue
        leftout = k - len(yes)
        yes.sort()
        skip = 0
        for skip in range(len(yes)):
            if yes[skip] <0 and leftout > 0:
                leftout -= 1
            else :
                break
        if best < sum(yes[skip:]):
            best = sum(yes[skip:])
#             print(yes[skip:], k, best)
print(best)

Submission status: Accepted

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

ans = 0

for left in range(k+1):
    for right in range(k - left + 1):
        if left + right > n:
            continue
        rock = v[:left] + v[::-1][:right]
        rock.sort()
        rem = k - left - right
        while rem > 0 and len(rock) > 0 and rock[0] < 0:
            rock = rock[1:]
            rem -= 1
        ans = max(ans, sum(rock))

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
from collections import defaultdict
from functools import reduce

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

class Interval():
    def __init__(self, li):
        self.li = li
        self.n = len(li)
        self.sum_li = [li[0]]
        for i in range(1, self.n):
            self.sum_li.append(self.sum_li[i-1] + li[i])

    def sum(self, a, b=None):
        if b is None:
            return self.sum(0, a)

        res = self.sum_li[min(self.n-1, b-1)]
        if a > 0:
            res -= self.sum_li[a-1]
        return res


res = 0
for k in range(K+1):
    for l in range(k+1):
        pos = 0
        neg = []
        for i in range(min(l, N)):
            if i >= N:
                break
            if V[i] >= 0:
                pos += V[i]
            else:
                neg.append(V[i])

        for i in range(min(k-l, N-l)):
            if i >= N:
                break
            v = V[N-i-1]
            if v >= 0:
                pos += v
            else:
                neg.append(v)

        # print(pos)

        for i, v in enumerate(sorted(neg)):
            if i < K-k:
                continue
            pos += v
        res = max(res, pos)

print(res)

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-i+1):
        if i+j>k:
            continue
        tmp=V[:i]+V[n-j:]
        tmp.sort(reverse=True)
        for l in range(k-i-j):
            if tmp and tmp[-1]<0:
                tmp.pop()
            else:
                break
        ans=max(ans,sum(tmp))
print(ans)

Submission status: Accepted

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

p = min(n, k)

res = 0

for i in range(p, -1, -1):
        # kことる
        for l in range(i + 1):
                r = i - l
                # 左からl, 右からrとる
                q = []
                for w in range(l):
                        q.append(v[w])
                for w in range(n - r, n):
                        q.append(v[w])
                q = sorted(q)
                ans = sum(q)
                tmp = ans
                for w in range(min(k - i, len(q))):
                        tmp -= q[w]
                        ans = max(ans, tmp)
                res = max(res, ans)



print(res)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
v = list(map(int, input().split()))
res = []
for i in range(K+1):
    for j in range(K-i+1):

        _v = v[::]
        stock = []
        stock.extend(_v[:i])
        _v = _v[i:]
        _v.reverse()
        stock.extend(_v[:j])
        stock.sort()
        for k in range(K-i-j+1):
            res.append(sum(stock[k:]))
print(max(res))

Submission status: Accepted

Solution code:
import heapq

n, K = map(int, input().split())
v = list(map(int, input().split()))
cum = [0] * (n+1)
for i in range(n):
    cum[i+1] += cum[i] + v[i]

ans = 0
for k in range(K+1):
    for i in range(k+1):
        if i > n:
            break
        j = k - i
        if j > i:
            continue
        for l in range(i+1):
            r = i - l
            score = 0
            hq = []
            for li in range(l):
                score += v[li]
                heapq.heappush(hq, v[li])
            for ri in range(r):
                ri = n - 1 - ri
                score += v[ri]
                heapq.heappush(hq, v[ri])
            for t in range(j):
                a = heapq.heappop(hq)
                score -= a
            ans = max(ans, score)

print(ans)