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, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from heapq import heappop
import heapq

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

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

# R = A + B
max_R = min(N, K)
# A, B 全探索
ans = 0
for R in range(1, max_R+1):
    for i in range(0, R+1):
        minus_count = 0

        v = deepcopy(V)
        #print("v:", v)
        pocket = []
        heapq.heapify(pocket)
        A = i
        B = R - i
        #print("a,b:", A, B)
        for a in range(A):
            a_pop = v.popleft()
            if a_pop < 0:
                minus_count += 1
            pocket.append(a_pop)
        for b in range(B):
            b_pop = v.pop()
            if b_pop < 0:
                minus_count += 1
            pocket.append(b_pop)
        # abundant abandon
        dump = K - R
        # pocketの中に捨てなくていいものもあるとき
        dump_time = min(minus_count, dump)
        #print("minus_count:", minus_count)
        #print("time:", dump_time)
        #print("pocket_b:", pocket)

        pocket.sort(reverse=True)
        # OK
        if dump_time > 0:
            for d in range(dump_time):
                x = pocket.pop()
        #        print("pop", x)
        
        # NG
        #if dump_time > 0:
        #    for d in range(dump_time):
        #        x = heappop(pocket) 
        #        print("X", x)

        wa = sum(pocket)
        #print("pocket_c:", pocket)
        if ans <= wa:
            ans = wa
        #print(ans)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

n,k = map(int,input().split())
D =list(map(int,input().split()))
ans = 0

for toridasukaisu in range(min(k,n)+1):#0~min(k,n)回取り出す
    for i in range(toridasukaisu+1):
        value = []#取り出したもののそれぞれの価値
        l = i#左からi回取り出し
        r = toridasukaisu - i#右から取り出す回数-i回取り出す
        for j in range(l):
            value.append(D[j])
        for j in range(r):
            value.append(D[-1-j])

        value.sort()
        suterukazu = 0
        suterukaisu = k - toridasukaisu
        for e in value:
            if suterukazu >= suterukaisu:
                break
            if e < 0:
                suterukazu += 1
            
        ans = max(sum(value[suterukazu:]),ans)
        
print(ans)

Submission status: Accepted

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

cum = [0]
rcum = [0]

for i in range(N):
    cum.append(cum[-1]+V[i])
    rcum.append(rcum[-1]+V[-1-i])

ans = 0

for i in range(N+1):
    for j in range(N+1):

        if i+j > min(N,K):
            continue

        value = cum[i]+rcum[j]
        neg = []

        for ii in range(i):
            if V[ii] < 0:
                neg.append(V[ii])

        for jj in range(j):
            if V[-1-jj] < 0:
                neg.append(V[-1-jj])

        neg.sort()

        value -= sum(neg[:min(K-i-j,len(neg))])

        ans = max(ans,value)

print(ans)

Submission status: Accepted

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

cum = [0]
rcum = [0]

for i in range(N):
    cum.append(cum[-1]+V[i])
    rcum.append(rcum[-1]+V[-1-i])

ans = 0

for i in range(N+1):
    for j in range(N+1):

        if i+j > min(N,K):
            continue

        value = cum[i]+rcum[j]
        neg = []

        for ii in range(i):
            if V[ii] < 0:
                neg.append(V[ii])

        for jj in range(j):
            if V[-1-jj] < 0:
                neg.append(V[-1-jj])

        neg.sort()

        value -= sum(neg[:min(K-i-j,len(neg))])

        ans = max(ans,value)

print(ans)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
V=list(map(int,input().split()))
from collections import deque
#K=min(N,K)
ans=-10**10
for k in range(0,min(K+1, N+1)):
    for n in range(0,k+1):
        A=V[0:n]+V[N-(k-n):]
        if len(A)==0:
            A=[0]
        A.sort()
        tmp=sum(A)
        for i in range(0, min(K-k,len(A))):
            if A[i]<0:
                tmp-=A[i]
            else:
                break
        if ans<tmp:
            ans=tmp
print(ans)

Submission status: Accepted

Solution code:
import heapq
n,k=list(map(int,input().split()))
a=list(map(int,input().split()))
ans=0
for i in range(k+1):
    tmp=a[:i]
    for j in range(k+1-i):
        if i+j>n:
            cal=a.copy()
            zan=k-n
        else:
            cal=tmp+a[n-j:]
            zan=k-i-j
        
        heapq.heapify(cal)
        ans=max(ans,sum(cal))
        for _ in range(zan):
            if len(cal)>0:
                heapq.heappop(cal)
                ans=max(ans,sum(cal))
            else:
                break
print(ans)

Submission status: Accepted

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

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

ret = 0

for i in range(0, min(n, k) + 1):
    for j in range(0, min(n, k) - i + 1):
        num_refund = k - i - j
        got_list = v_list[:i] if i > 0 else []
        got_list.extend(v_list[-j:] if j > 0 else [])
        sorted_list = sorted(got_list)

        if num_refund == 0:
            val = sum(sorted_list)
            if val > ret:
                ret = val

        insert_index = bisect.bisect_left(sorted_list, 0)
        if insert_index > num_refund:
            val = sum(sorted_list[num_refund:])
            if val > ret:
                ret = val
        else:
            val = sum(sorted_list[insert_index:])
            if val > ret:
                ret = val

print(ret)

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

def main():
  n, k = map(int, input().strip().split())
  vs = list(map(int, input().strip().split()))
  
  max = 0
  for i in range(k+1):
    if i > n:
      break
    for j in range(i+1):
      xs = sorted(vs[:j] + vs[n-(i-j):])
      cand = sum(xs)
      for ik in range(k - (i)):
        if ik >= len(xs):
          break
        if xs[ik] < 0:
          cand -= xs[ik]
      if max < cand:
        max = cand
  print(max)
    

if __name__=='__main__':
  main()

Submission status: Accepted

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


def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def func(N, mod):
    F = [1]
    for i in range(1, N + 1):
        F.append(F[-1] * i % mod)
    return F


def inv(a, mod):
    return pow(a, mod - 2, mod)


def C(F, a, b, mod):
    return F[a] * inv(F[b], mod) * inv(F[a - b], mod) % mod


def f(V, L, R):
    import bisect
    N = len(V)
    
    res = 0
    for r in range(min(N - L, R) + 1):
        LL = sorted(V[:L] + V[-r:] if r != 0 else V[:L])
        k = min(R - r, bisect.bisect_left(LL, 0))
        res = max(res, sum(LL[k:]))
    return res


def main():
    N, K = read_values()
    V = read_list()
    
    res = 0
    for L in range(K + 1):
        res = max(res, f(V, L, K - L))
    print(res)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import heapq

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

ans = 0
for i in range(N+1):
    for j in range(N+1):
        if i + j > min(K, N):
            continue
        que = []
        for k in range(i):
            heapq.heappush(que, V[k])
        for k in range(j):
            heapq.heappush(que, V[-k-1])

        for l in range(K-i-j):
            if len(que) == 0 or que[0] > 0:
                break
            heapq.heappop(que)

        #print(i, j, K-i-j, que)

        ans = max(ans, sum(que))

print(ans)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
ret = 0
for a in range(N):
  for b in range(N-a+1):
    cmax = K-a-b
    if cmax >= 0:
      W=A[:a]+A[N-b:]
      W.sort()
      tmp=0
      for i in range(len(W)):
        if i<cmax and W[i]<0:
          continue
        else:
          tmp=sum(W[i:])
          break
      ret=max(ret,tmp)
print(ret)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
ret = 0
for a in range(N):
  for b in range(N-a+1):
    cmax = K-a-b
    if cmax >= 0:
      W=A[:a]+A[N-b:]
      W.sort()
      c=min(sum([1 for i in W if i<0]),cmax)
      ret=max(ret,sum(W[c:]))
print(ret)

Submission status: Accepted

Solution code:
import math
import copy
from copy import deepcopy
import sys
import fractions
import numpy as np
from functools import reduce
# import statistics
import heapq
sys.setrecursionlimit(3000)

# input = sys.stdin.readline
# sys.setrecursionlimit(10**6)

# ===FUNCTION===

def getInputInt():
    inputNum = int(input())
    return inputNum


def getInputListInt():
    outputData = []
    inputData = input().split()
    outputData = [int(n) for n in inputData]

    return outputData


def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList


def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList


# ===CODE===

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

ans = 0

for i in range(1, min(n, k)+1, 1):
    for j in range(i+1):
        l = j
        r = n-(i-j)

        d = data[:l]
        d += data[r:]
        d.sort()

        del_num = min(k-i, i)
        for l in range(del_num):
            if d[l] >= 0:
                del_num = l
                break
        ans = max(ans, sum(d[del_num:]))

print(ans)

Submission status: Accepted

Solution code:
import math
import copy
from copy import deepcopy
import sys
import fractions
import numpy as np
from functools import reduce
# import statistics
import heapq
sys.setrecursionlimit(3000)

# input = sys.stdin.readline
# sys.setrecursionlimit(10**6)

# ===FUNCTION===

def getInputInt():
    inputNum = int(input())
    return inputNum


def getInputListInt():
    outputData = []
    inputData = input().split()
    outputData = [int(n) for n in inputData]

    return outputData


def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList


def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList


# ===CODE===

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

ans = 0

for i in range(1, min(n, k)+1, 1):
    for j in range(i+1):
        l = j
        r = n-(i-j)

        d = data[:l]
        d += data[r:]
        d.sort()

        del_num = min(k-i, len(d))
        for l in range(del_num):
            if d[l] >= 0:
                del_num = l
                break
        ans = max(ans, sum(d[del_num:]))

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):
  l=min(k-i,n)
  for a in range(l+1):
    b=l-a
    if b==0:
      sub=v[:a]
    else:
      sub=v[:a]+v[-b:]
    h=min(len(sub),i)
    for j in range(h):
      m=min(sub)
      if m<0:
        sub.remove(m)
    ans=max(ans,sum(sub))

print(ans)

Submission status: Accepted

Solution code:
def main():
    N,K=map(int,input().split())
    V=list(map(int,input().split()))
    M=min(N,K)
    result=0
    for l in range(M+1):
        for r in range(M+1-l):
            L=l
            R=r
            count=0
            minus=[]
            m=l+r
            while L>0:
                a=V[L-1]
                if a>=0:
                    count+=a
                else:
                    count+=a
                    minus.append(a)
                L-=1
            while R>0:
                a=V[-R]
                if a>=0:
                    count+=a
                else:
                    count+=a
                    minus.append(a)
                R-=1

            minus.sort()
            i_minus=0
            while K-m>0 and i_minus<len(minus):
                count-=minus[i_minus]
                m+=1
                i_minus+=1
            result=max(result,count)
    print(result)

if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    N, K = map(int, input().split())
    V = list(map(int, input().split()))
    L = [(0, [])]
    R = [(0, [])]

    mp = 0
    mn = []
    for _, v in zip(range(K), V):
        if v >= 0:
            mp += v
        else:
            mn.append(v)
            mn.sort()
        L.append((mp, tuple(mn)))

    mp = 0
    mn = []
    for _, v in zip(range(K), reversed(V)):
        if v >= 0:
            mp += v
        else:
            mn.append(v)
            mn.sort()
        R.append((mp, tuple(mn)))

    mval = 0
    for l, (lp, ln) in enumerate(L):
        for r, (rp, rn) in zip(range(K - l + 1), R):
            if l + r > len(V):
                break
            val = rp + lp
            n = K - l - r
            if len(ln) + len(rn) > n:
                t = list(ln) + list(rn)
                t.sort()
                val += sum(t[n:])
            mval = max(mval, val)
    print(mval)


main()

Submission status: Accepted

Solution code:
import copy
if __name__ == '__main__':
    N,K=list(map(int,input().split()))
    Jewelries_org=list(map(int,input().split()))
    ans=0
    upper=min(N,K)
    for a in range(upper+1):
        for b in range(upper-a+1):
            hand=[]
            Jewelries=copy.deepcopy(Jewelries_org)
            for i in range(a):
                hand.append(Jewelries.pop(0))
            for i in range(b):
                hand.append(Jewelries.pop(-1))
            hand.sort()
            for i in range(K-(a+b)):
                if hand.__len__()>0 and hand[0]<0:
                    hand.pop(0)
            s=sum(hand)
            if s>ans:
                ans=s
    print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
V=list(map(int,input().split()))
ans=0
for i in range(n+1):
    for j in range(n-i+1):
        #print(i, j)
        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()))
ans = 0
for i in range(K+1):
    li = V[:i]
    for j in range(K+1):
        if i+j > N or i+j > K:
            break
        if j:
            lj = li + V[-j:]
        else:
            lj = li[:]
        for k in range(K+1):
            if i+j+k>K:
                break
            if i+j >= k:
                lj.sort()
                ans = max(ans, sum(lj[k:]))
print(ans)

Submission status: Accepted

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


res = 0
minNK = min(n, k)

for i in range(minNK + 1):
    for j in range(minNK - i + 1):
        tempList = []
        tempList.extend(v[:i])
        if j!=0:
            tempList.extend(v[-j:])
        tempList.sort()
        tempSum = sum(tempList)
        for idx, val in enumerate(tempList):
            if val < 0 and idx < min(k - i - j, len(tempList)):
                tempSum -= val
        res = max(res, tempSum)

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):
	for j in range(i,n+1):
		if len(v[:i])+len(v[j:])>k:
			continue	
		p=sum(v[:i])+sum(v[j:])
		minus=[]
		for x in v[:i]:
			if x<0:
				minus.append(x)
		for x in v[j:]:
			if x<0:
				minus.append(x)
		minus.sort()
		for l in range(min(len(minus),k-(len(v[:i])+len(v[j:])))):
			p-=minus[l]
		ans=max(ans,p)
print(ans)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
V=list(map(int,input().split()))
a=0
for i in range(0,K+1):
    li=V[:i]
    for j in range(0,K+1):
        if i+j>N or i+j>K:
            break
        if j:
            lj=li+V[-j:]
        else:
            lj=li
        for k in range(0,K+1):
            if i+j+k>K:
                break
            if i+j>=k:
                lj.sort()
                a=max(a,sum(lj[k:]))
print(a)

Submission status: Accepted

Solution code:
from itertools import accumulate
N, K = map(int, input().split())
*V, = map(int, input().split())

ans = 0
for a in range(N+1):
    for b in range(N+1):
        if a+b>N:continue
        t = []
        if a:
            t += V[:a]
        if b:
            t += V[-b:]
        t.sort()
        t = [0]+t
        
        v = sum(t)
        for c in range(a+b+1):
            v -= t[c]
            if a+b+c<=K:
                ans = max(ans, v)

print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate
N, K = map(int, input().split())
*V, = map(int, input().split())

ans = 0
for a in range(N+1):
    for b in range(N+1):
        if a+b>N:continue
        
        if a and b:
            qa, qb = list(accumulate([0]+sorted(V[:a]))), list(accumulate([0]+sorted(V[-b:])))
            sa, sb = sum(V[:a]), sum(V[-b:])
            for c in range(a+1):
                for d in range(b+1):
                    if a+b+c+d<=K:
                        ans = max(ans, sa+sb-qa[c]-qb[d])
        elif a:
            qa = list(accumulate([0]+sorted(V[:a])))
            sa = sum(V[:a])
            for c in range(a+1):
                if a+c<=K:
                    ans = max(ans, sa-qa[c])
        elif b:
            qb = list(accumulate([0]+sorted(V[-b:])))
            sb = sum(V[-b:])
            for d in range(b+1):
                if b+d<=K:
                    ans = max(ans, sb-qb[d])

print(ans)

Submission status: Accepted

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

## 宝石を取得する個数、でループ
ans = 0
for k in range(K+1):
  for _ in range(K+1):
    if (k+_)>N or (k+_)>K:
      break
    
    cnt_push_stone = K-(k+_)
    
    ## 取得する宝石をリストにしてソートする
    got_stones = V[:k]+V[N-_:]
    got_stones.sort()
    
    ## 負の価値の宝石を戻す
    for i in range(min(cnt_push_stone,k+_)):
      if got_stones[i] < 0:
        got_stones[i] = 0
    
    ## 既存の最大値との比較
    ans = max(ans, sum(got_stones))

print(ans)

Submission status: Accepted

Solution code:
import sys

n, k, *v = map(int, sys.stdin.read().split())

def main():
    m = min(n, k)
    ls = [None] * (m + 1)
    rs = [None] * (m + 1)
    l_neg = [None] * (m + 1)
    r_neg = [None] * (m + 1)
    
    ls[0] = 0
    rs[0] = 0
    l_neg[0] = []
    r_neg[0] = []

    for i in range(m):
        l = v[i]; r = v[-(i+1)]
        ls[i+1] = ls[i] + l
        rs[i+1] = rs[i] + r
        
        l_neg[i+1] = l_neg[i].copy()
        if l < 0:
            l_neg[i+1].append(l)
        r_neg[i+1] = r_neg[i].copy()
        if r < 0:
            r_neg[i+1].append(r)
    
    res = 0
    for i in range(m+1):
        for j in range((m-i)+1):
            s = ls[i] + rs[j]
            neg = sorted(l_neg[i] + r_neg[j])
            s -= sum(neg[:k-(i+j)])
            res = max(res, s)
    return res
        
if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Accepted

Solution code:
import sys

n, k, *v = map(int, sys.stdin.read().split())

def main():
    m = min(n, k)
    res = 0
    for i in range(m+1):
        for j in range((m-i)+1):
            l = v[:i]
            r = v[-j:] if j > 0 else []
            take = l + r
            s = sum(take)
            neg = [t for t in take if t < 0]
            neg.sort()
            s -= sum(neg[:(k-(i+j))])
            res = max(res, s)
    return res
    
if __name__ == '__main__':
    ans = main()
    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(K + 1, N + 1)):
    for j in range(min(K + 1 - i, N + 1 - i)):
        d = K - i -j
        nowlst = v[:i] + v[N - j:]
        nowlst.sort(reverse=True)
        for k in range(d):
            if nowlst != [] and nowlst[-1] < 0:
                nowlst.pop()
            else:
                break
        ans = max(ans, sum(nowlst))

print(ans)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc128/tasks/abc128_d


# 単純なアイデアとしては、ほぼ愚直に操作を行う。
# K個のViを取って一番合計の大きいもの
# K-1のViを取って価値の引くものを1つ詰めるとしたときに一番合計の大きくなるもの
# K-iのViを取って価値の低いものをiつ詰めるとしたときに一番合計が大きくなるもの

# 最大N個とるのを最大N回ずらして、最大N個の手持ちのソートするので、オーダーはO(N^3 logN)
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


N, K = read_ints()
V = read_ints()
V = V + V

ans = 0
for i in range(K):
    n_pick = K - i
    n_back = i
    if n_pick > N:
        n_back = n_pick - N
        n_pick = N

    for j in range(n_pick + 1):  # スライドよう
        v = V[N - j:N + n_pick - j]
        v.sort()
        # print(v)
        if n_back < len(v) and v[n_back] < 0:
            ans = max(ans, sum(v[n_back:]))  # ここでは最大n_back個まで捨てることができる
        else:
            ans = max(ans, sum([max(0, x) for x in v]))
print(ans)

Submission status: Accepted

Solution code:
def main():
    N, K = (int(i) for i in input().split())
    V = [int(i) for i in input().split()]
    if 2*N <= K:
        ans = sum(v for v in V if v > 0)
        return print(ans)
    ans = 0
    for a in range(N+1):
        for b in range(N+1):
            if N < a+b:
                continue
            if K < a+b:
                continue
            rest = K - a - b
            cur_e = V[:a]
            if b > 0:
                cur_e += V[-b:]
            cur_e.sort(reverse=True)
            while cur_e and cur_e[-1] < 0 and 0 < rest:
                cur_e.pop()
                rest -= 1
            ans = max(ans, sum(cur_e))

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    N, K = (int(i) for i in input().split())
    V = [int(i) for i in input().split()]
    if 2*N <= K:
        ans = sum(v for v in V if v > 0)
        return print(ans)
    ans = 0
    R = min(N, K)
    for a in range(R+1):
        for b in range(R+1):
            if R < a+b:
                continue
            can_de = K - a - b
            cur_e = V[:a] + V[:-(b+1):-1]
            cur_e.sort(reverse=True)
            while cur_e and cur_e[-1] < 0 and 0 < can_de:
                cur_e.pop()
                can_de -= 1
            ans = max(ans, sum(cur_e))

    print(ans)


if __name__ == '__main__':
    main()

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-i):
        if i+j<=n:
            remain=max(0,k-(i+j))
            kouho=V[:i]+V[n-j:]
            kouho.sort()
            if remain>0:
                for t in range(remain):
                    if t<i+j:
                        if kouho[t]<0:
                            kouho[t]=0
            ans=max(ans,sum(kouho))
print(ans)

Submission status: Accepted

Solution code:
def main():
    N, K = map(int, input().split())
    V = list(map(int, input().split()))
    M = min(N, K)
    ans = 0
    for a in range(M+1):
        for b in range(M - a+1):
            tmp = []
            tmp.extend(V[:a])
            tmp.extend(V[::-1][:b])
            tmp.sort()
            for i in range(K - (a + b)):
                if len(tmp) > 0 and tmp[0] < 0:
                    tmp.pop(0)
            ans = max(ans, sum(tmp))
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
v=list(map(int,input().split()))
ans=0
for l in range(min(k+1,n+1)):
  for r in range(min(k+1-l,n+1-l)):
    if l==0 and r==0:
      continue
    rem=r+l
    if l==0:
      arr=v[n-r:]
    elif r==0:
      arr=v[:l]
    else:
      arr=v[:l]+v[n-r:]
    arr.sort()
    m=sum(arr)
    idx=0
    while 0<=idx<len(arr) and arr[idx]<0 and rem<k:
      rem+=1
      m-=arr[idx]
      idx+=1
    ans=max(ans,m)
print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
v = list(map(int, input().split()))
mini = min(n, k)
value = 0
for a in range(mini + 1):
  for b in range(mini - a + 1):
    c = k - a - b
    j = v[:a] + v[n-b:]
    j.sort(reverse=True)
    for _ in range(c):
      if j and j[-1] < 0:
        j.pop()
      else:
        break
    value = max(value, sum(j))
print(value)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
n,k = map(int,readline().split())
lst1 = list(map(int,readline().split()))

ans = 0
for a in range(n+1):
    for b in range(n+1):
        if a+b > min(n,k):
            continue
        left = lst1[:a]
        right = lst1[n-b:]
        res = left + right
        rest = k - (a + b)
        if rest > 0:
            res.sort()
            while rest:
                if len(res) == 0:
                    break
                if res[0] < 0:
                    del res[0]
                    rest -=1
                else:
                    break
        ans = max(ans,sum(res))

print(ans)

Submission status: Accepted

Solution code:
import bisect
def main():
    N, K = map(int, input().split())
    V = list(map(int, input().split()))
    m = 0
    for i in range(min(N, K)+1):
        for j in range(min(K - i, N-i) + 1):
            t = V[:i] + V[N-j:]
            t.sort()
            ind = bisect.bisect_right(t, 0)
            d = min((i+j), K - i - j, ind)
            m = max(m, sum(t[d:]))
    print(m)
main()

Submission status: Accepted

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

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

    #ans = -(10**10)
    ans = 0
    for pick in range(min(N+1,K+1)):
        throw = min(pick,K-pick)
        for left in range(pick+1):
            right = pick-left
            p = []
            minus = 0
            for i in range(left):
                if V[i] < 0:
                    minus += 1
                p.append(V[i])
            for i in range(right):
                if V[-i-1] < 0:
                    minus += 1
                p.append(V[-i-1])
            p.sort()
            if minus >= throw:
                rest = p[throw:]
            else:
                rest = p[minus:]
            ans = max(ans,sum(rest))

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

ans = 0
have = []  # 手元にある宝石の価値のリスト
val = 0  # 手元にある宝石の価値の和

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

        # 負の数をできるだけ戻す
        for d in range(0, min(l + r, k - l - r)):
            if have[d] > 0: break
            val -= have[d]

        ans = max(ans, val)

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(101)

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


def doit(l, r, kk):
    if kk == 0 or l > r:
        return 0
    if (l, r, kk) not in memo:
        memo[(l, r, kk)] = max(vs[l] + doit(l + 1, r    , kk - 1),
                           vs[r] + doit(l    , r - 1, kk - 1),
                                   doit(l + 1, r    , kk - 2) if kk > 1 else 0,
                                   doit(l    , r - 1, kk - 2) if kk > 1 else 0)
    return memo[(l, r, kk)]


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

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
v = list(map(int, input().split()))
ret = 0
for s in range(n):
    for e in range(s, n + 1):
        t = k - (s + n - e)
        if t < 0:
            continue
        l = sorted(v[:s] + v[e:])
        u = 0
        while u < len(l) and u < t and l[u] < 0:
            u += 1
        ret = max(ret, sum(l[u:]))
print(ret)

Submission status: Accepted

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

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