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:

def main():
    buf = input()
    buflist = buf.split()
    N = int(buflist[0])
    K = int(buflist[1])
    buf = input()
    buflist = buf.split()
    V = list(map(int, buflist))
    max_value = 0
    for i in range(min(N+1, K+1)):
        push_limit = K - i
        for j in range(i+1):
            jewel = []
            for k in range(-i+j, j):
                jewel.append(V[k])
            jewel = list(sorted(jewel))
            value = sum(jewel)
            for k in range(push_limit):
                if k >= len(jewel):
                    break
                if jewel[k] < 0:
                    value += -jewel[k]
                else:
                    break
            if value > max_value:
                max_value = value
    print(max_value)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
*V, = map(int,input().split())
ans = 0
for l in range(min(N,K+1)):
    for r in range(min(N-l+1,K-l+1)):
        h = V[:l]+V[N-r:]
        h.sort(reverse=True)
        for _ in [0]*(K-(l+r)):
            if h and h[-1]<0:h.pop()
        ans = max(ans,sum(h))
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
n, k = [int(_) for _ in input().split()]
v = [int(_) for _ in input().split()]

ans = 0

for l in range(n):
    for r in range(n - l + 1):
        if l + r > k:
            break
        nv = v[:l] + v[n - r:]
        nv.sort()
        for i in range(k - l - r):
            if not nv or nv[0] >= 0:
                break
            del nv[0]
        ans = max(ans, sum(nv))

print(ans)

Submission status: Accepted

Solution code:
import functools
import heapq


def main():
    from sys import stdin, stdout

    def read():
        return stdin.readline().rstrip('\n')

    def read_array(sep=None, maxsplit=-1):
        return read().split(sep, maxsplit)

    def read_int():
        return int(read())

    def read_int_array(sep=None, maxsplit=-1):
        return [int(a) for a in read_array(sep, maxsplit)]

    def write(*args, **kwargs):
        sep = kwargs.get('sep', ' ')
        end = kwargs.get('end', '\n')
        stdout.write(sep.join(str(a) for a in args) + end)

    def write_array(array, **kwargs):
        sep = kwargs.get('sep', ' ')
        end = kwargs.get('end', '\n')
        stdout.write(sep.join(str(a) for a in array) + end)

    N, K = read_int_array()
    nums = read_int_array()
    ans = 0

    @functools.lru_cache(None)
    def dp(i, j, handsum):
        nonlocal ans
        left = j + 1 - i
        taken = N - left
        if taken == K:
            ans = max(ans, handsum)
            return
        moves = K - taken

        if i <= j:
            dp(i+1, j, handsum + nums[i])
            dp(i, j-1, handsum + nums[j])

        can_return = sum(sorted([x for x in (nums[:i] + nums[j+1:]) if x < 0])[:moves])
        ans = max(ans, handsum - can_return)

    dp(0, N-1, 0)
    write(ans)

main()

Submission status: Accepted

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

for l in range(min(K,N)+1):
    ANS_l=V[:l]

    for r in range(min(K,N)+1-l):
        ANS=ANS_l+V[N-r:]

        #print(l,r,ANS)

        ANS.sort()

        SUM=sum(ANS)
        SCORE=max(SCORE,SUM)

        #print(SCORE,ANS)

        for u in range(min(len(ANS),K-l-r)):
            SUM-=ANS[u]
            SCORE=max(SCORE,SUM)

            #print(SCORE)
print(SCORE)

Submission status: Accepted

Solution code:
def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    # ここで分割を行う
    left = arr[:mid]
    right = arr[mid:]

    # 再帰的に分割を行う
    left = merge_sort(left)
    right = merge_sort(right)

    # returnが返ってきたら、結合を行い、結合したものを次に渡す
    return merge(left, right)


def merge(left, right):
    merged = []
    l_i, r_i = 0, 0

    # ソート済み配列をマージするため、それぞれ左から見ていくだけで良い
    while l_i < len(left) and r_i < len(right):
        # ここで=をつけることで安定性を保っている
        if left[l_i] <= right[r_i]:
            merged.append(left[l_i])
            l_i += 1
        else:
            merged.append(right[r_i])
            r_i += 1

    # 上のwhile文のどちらかがFalseになった場合終了するため、あまりをextendする
    if l_i < len(left):
        merged.extend(left[l_i:])
    if r_i < len(right):
        merged.extend(right[r_i:])
    return merged

# 以上マージソート

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

qa = [0]
takea = [[]]
now = 0

for i in range(N):
    now += que[i]
    qa.append(now)
    takea.append(que[0:i+1])

qb = [0]
takeb = [[]]
now = 0

for i in reversed(range(N)):
    now += que[i]
    qb.append(now)

    takeb.append(que[i:])

max = 0

# 取る個数：i
for i in range(1, N+1):
    #左から取る個数：j
    for j in range(i+1):
#        print("Left : ", j, "   Right : ", i-j)
        qtotal = qa[j]+qb[i-j]
        taketotal = takea[j]+takeb[i-j]
        taketotal = merge_sort(taketotal)
        discardable = K-i
        for k in taketotal:
            if (discardable==0):
                break;

            if (0<=k):
                break;
            else:
                qtotal-=k
                discardable-=1
        if(max<qtotal):
            max = qtotal
    if(i==K):
        break;

print(max)

# temp
'''
A = int(input())
'''
# 2つ
'''
A, B = map(int, input().split())
'''
# N個+横1列
'''
N = input()
A = list(map(int, input().split()));
'''
#-1が来るまでinput
'''
a = []
while True:
    n = input()
    if n == -1:
        break
    a.append(n)
'''
#EOFまでinput
'''
import sys

a = []
for line in sys.stdin:
    a.append(int(line))
'''

# 横N 縦M
'''
N, M = map(int, raw_input().split())
a = []
for i in range(M):
    a.append(map(int, raw_input().split()))
'''

# union-find木
'''
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)
'''

# merge sort
'''
def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    # ここで分割を行う
    left = arr[:mid]
    right = arr[mid:]

    # 再帰的に分割を行う
    left = merge_sort(left)
    right = merge_sort(right)

    # returnが返ってきたら、結合を行い、結合したものを次に渡す
    return merge(left, right)


def merge(left, right):
    merged = []
    l_i, r_i = 0, 0

    # ソート済み配列をマージするため、それぞれ左から見ていくだけで良い
    while l_i < len(left) and r_i < len(right):
        # ここで=をつけることで安定性を保っている
        if left[l_i] <= right[r_i]:
            merged.append(left[l_i])
            l_i += 1
        else:
            merged.append(right[r_i])
            r_i += 1

    # 上のwhile文のどちらかがFalseになった場合終了するため、あまりをextendする
    if l_i < len(left):
        merged.extend(left[l_i:])
    if r_i < len(right):
        merged.extend(right[r_i:])
    return merged

'''

Submission status: Accepted

Solution code:
from collections import deque

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

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

ans = 0
for left in range(min(N + 1, K + 1)):
    for right in range(min(N + 1 - left, K + 1 - left)):
        dq = deque(V)
        l = []
        for i in range(left):
            l.append(dq.popleft())
        for i in range(right):
            l.append(dq.pop())
        l.sort(key=lambda x: -x)
        for _ in range(K - left - right):
            if not l:
                break
            if l[-1] < 0:
                l.pop()
        ans = max(ans, sum(l))
        # print(left,right,sum(l),l)
print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
V = list(map(int, input().split()))
ans = 0
for n in range(1, min(K,N)+1):
    m = min(K-n, n)
    for l in range(n+1):
        r = n-l
        A = V[:l] + (V[-r:] if r!=0 else [])
        A.sort()
        an = 0
        for i, a in enumerate(A):
            if i<m and a<0:
                continue
            else:
                an += a
        ans = max(ans, an)
print(ans)

Submission status: Accepted

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

ans = 0
for l in range(K+1):
  for r in range(K+1):
    if l+r<=K and l+r<=N:
      T = V[:l]+(V[-r:] if r>0 else [])
      T = sorted(T)[::-1]
      for _ in range(K-l-r):
        if len(T)>0 and T[-1]<0:
          T.pop()
      ans = max(ans, sum(T))
print ans

Submission status: Accepted

Solution code:
from bisect import bisect_left
n,k = map(int, input().split())
v = list(map(int, input().split()))
# 取る回数i
# 取る回数が0なら0だからやらない
ans = 0
for i in range(1, k+1):
    if i > n:
        continue
    toreru = min(k-i, i)
    for left in range(i+1):
        right = i-left
        # left,rightの中から、マイナスのものがk-i個以下なら全部捨てる それ以上なら無視
        #print(left, right, toreru)
        #print(v[:left], v[-1:-right-1:-1])
        now = v[:left] + v[-1:-right-1:-1]
        now.sort()
        ko = bisect_left(now, 0)
        if ko <= toreru:
            ans = max(ans, sum(now[ko:]))
            #print(sum(now[ko:]))
        else:
            ans = max(ans, sum(now[toreru:]))
            #print(sum(now[toreru:]))
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque
from collections import defaultdict
import math
sys.setrecursionlimit(20000000)
#input = sys.stdin.readline

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-i+1):
                x = v[:i]
                if n< i+j:
                        continue
                if i+j > k:
                        continue
                if j > 0:
                        x = x + v[-j:]
                x.sort(key=lambda x : -x)
                kai = i+ j
                while kai < k and x and x[-1] < 0:
                        x.pop()
                        kai+=1
                ans = max(ans,sum(x))
print(ans)

Submission status: Accepted

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

ans = 0
for L in range(min(N, K) + 1):
    for R in range(min(N - L, K - L) + 1):
        js = V[:L] + V[-R:] if R >= 1 else V[:L]
        t = K - L - R
        s = 0
        for j in sorted(js):
            if j < 0 and t > 0:
                s += -j
                t -= 1
        ans = max(ans, sum(js) + s)

print(ans)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    a,p = LI()
    print((a*3+p)//2)
    return

#B
def B():
    n = I()
    s = [None for i in range(n)]
    for i in range(n):
        l = input().split()
        s[i] = l+[i]
    s.sort(key = lambda x:(x[0],-int(x[1])))
    for i,a,b in s:
        print(b+1)
    return

#C
def C():
    def dfs(d,k):
        if d == n:
            l.append(k)
        else:
            dfs(d+1,k+[0])
            dfs(d+1,k+[1])
    n,m = LI()
    l = []
    dfs(0,[])
    qu = LIR(m)
    p = LI()
    ans = 0
    for k in l:
        s = 0
        for q in range(m):
            num = qu[q][0]
            lis = list(map(lambda x:x-1, qu[q][1:]))
            su = 0
            for i in lis:
                su ^= k[i]
            if su == p[q]:
                s += 1
        if s == m:
            ans += 1
    print(ans)
    return

#D
def D():
    n,k = LI()
    v = LI()
    ans = -float("inf")
    for l in range(min(k,n)+1):
        for r in range(min(k,n)-l+1):
            m = 0
            q = v[:l]+v[n-r:]
            q.sort()
            res = max(0,k-r-l)
            for i in range(len(q)):
                if q[i] < 0 and res > 0:
                    res -= 1
                else:
                    m += q[i]
            if m > ans:
                ans = m
    print(ans)
    return

#E
def E():
    n = I()

    return

#F
def F():
    n = I()

    return

#Solve
if __name__ == "__main__":
    D()

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)


def main():
    n,k = LI()
    a = LI()
    r = 0
    for i in range(1,min(n,k)+1):
        for j in range(i+1):
            ii = i - j
            t = a[:j]
            if ii > 0:
                t += a[-ii:]
            t.sort()
            l = min(k - i,i-1)
            for ll in range(l):
                if t[ll] >= 0:
                    l = ll
                    break
            s = sum(t[l:])
            if r < s:
                r = s

    return r


print(main())

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
V=[int(i) for i in input().split()]
ans=0
for i in range(N):
  for j in range(i,N+1):
    c=0
    if i+N-j<=K:
      k=K-(i+N-j)
      s=V[:i]+V[j:]
      s.sort()
      c=0
      #print(s,k)
      for t in s:
        if k>=1 and t<0:
          k-=1
        else:
          c+=t
    ans=max(c,ans)
print(ans)

Submission status: Runtime Error

Solution code:

import sys

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

k=k0
if n<=k:
    v.sort()
    vsum=sum(v)
    kk=k-n
    vsum=0
    for i in range(n):
        if i>kk:
            vsum+=v[i]
        elif i<=kk and v[i]>0:
            vsum+=v[i]
    print(max(0,vsum))
    sys.exit()

vmax=-10**10

kk=k0
for k in range(kk):
    k2=kk-k-1
    
    vv=[[0]*(k+1) for i in range(k+1+1)]
    for i in range(k+1):
        vv[0][i]=v[n-k+i-1]
    vsum=sum(vv[0])
    vmax=max(vsum,vmax)
#    print("k:",k,"vsum:",vsum,"vmax:",vmax)
#    print(vv[0])
    vvv=vv[0].copy()
    vvv.sort()
    for i in range(min(k2,k+1)):
        if vvv[i]<0:
            vsum-=vvv[i]
    vmax=max(vsum,vmax)
#    print("k:",k,"vsum:",vsum,"vmax:",vmax)

    for i in range(k+1):
        vv[i+1]=vv[i].copy()
        vv[i+1].pop(0)
        vv[i+1].append(v[i])
        vsum=sum(vv[i+1])
        vmax=max(vsum,vmax)
#        print("k:",k,"vsum:",vsum,"vmax:",vmax)
#        print(vv[i+1])
        vvv=vv[i+1].copy()
        vvv.sort()
        for i in range(min(k2,k+1)):
            if vvv[i]<0:
                vsum-=vvv[i]
        vmax=max(vsum,vmax)
#        print("k:",k,"vsum:",vsum,"vmax:",vmax)
    
print(max(0,vmax))

Submission status: Runtime Error

Solution code:
# equeue

from collections import deque
import heapq


def main():
    N, K = map(int, input().split())
    V = list(map(int, input().split()))
    res = 0
    for pull in range(K+1):
        push = K - pull
        if push < 0:
            continue
        for left_push in range(push+1):
            tmp_que = deque(V)
            tmp_heap = []
            heapq.heapify(tmp_heap)
            right_push = push - left_push
            for _ in range(left_push):
                heapq.heappush(tmp_heap, tmp_que.popleft())
            for _ in range(right_push):
                heapq.heappush(tmp_heap, tmp_que.pop())

            tmp_res = sum(tmp_que)
            for i in range(min(push, pull)):
                x = heapq.heappop(tmp_heap)
                if x >= 0:
                    heapq.heappush(tmp_heap, x)
                    break

            res = max(res, sum(tmp_heap))
    print(res)
    return


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
ans=0
v=list(map(int,input().split()))
for i in range(min(n,k+1)):
    for j in range(min(n-i,k-i+1)):
        if j!=0
            tmp=v[:i]+v[-j:]
        else:
            tmp=v[:i]
        tmp.sort()
        t=sum(tmp)
        for d in range(min(k-i-j,len(tmp))):
            if tmp[d]<0:
                t-=tmp[d]
        if t>ans:
            ans=t
print(ans)

Submission status: Runtime Error

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

a=list(map(int,input().split()))
a_reverse=list(reversed(a))
b=sorted(a)
s=sum(a)

ans=[]

for i in range(k+1):
  if i>n:
    I=i-n
    for j in range(I): 
      ans1=s-b[j]
    ans.append(ans1)
  elif i==n:
    ans.append(s)
  elif i==0:
    ans.append(0)
  else:
    for h in range(i+1):
      H=i-h
      c=[]
      for x in range(h):
        c.append(a[x])
      for y in range(H):
        c.append(a_reverse[y])
        
      c.sort()
      S=sum(c)
      for g in range(1,k-i+1):
        if g<=i:
          if c[g-1]<0:
            S-=c[g-1]

      ans.append(S)
      
print(max(ans))

Submission status: Runtime Error

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

a=list(map(int,input().split()))
a_reverse=list(reversed(a))
b=sorted(a)
s=sum(a)

ans=[]

for i in range(k+1):
  if i>n:
    I=i-n
    for j in range(I): 
      ans1=s-[j]
    ans.append(ans1)
  elif i==n:
    ans.append(s)
  elif i==0:
    ans.append(0)
  else:
    for h in range(i+1):
      H=i-h
      c=[]
      for x in range(h):
        c.append(a[x])
      for y in range(H):
        c.append(a_reverse[y])
        
      c.sort()
      S=sum(c)
      for g in range(1,k-i+1):
        if g<=i:
          if c[g-1]<0:
            S-=c[g-1]

      ans.append(S)
      
print(max(ans))

Submission status: Runtime Error

Solution code:
from heapq import heappop, heapify


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

# i: 操作回数
# j: iのうち戻す回数
# k: i - j のうち左から取り出す範囲 [0, k)
ans = 0
for i in range(K + 1):
    res = 0
    pq = []
    for j in range(i // 2 + 1):
        for k in range(i - j + 1):
            put_out_cnt = j
            tmp = V[:k]
            l = i - j - k
            if l > 0:
                tmp += V[-l:]
            heapify(tmp)
            while put_out_cnt > 0:
                heappop(tmp)
                put_out_cnt -= 1
            ans = max(ans, sum(tmp))
print(ans)

Submission status: Runtime Error

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

base=sum(V)
ans=base
for i in range(K+1):
    for j in range(K-i+1):
        tmp=[V[k] for k in range(i)]
        for k in range(j):
            tmp.append(V[-1-k])
        tmp.sort()
        rest=K-i-j
        minus=0
        base=sum(tmp)
        for k in range(min(rest,len(tmp))):
            if tmp[k]<0:
                minus+=tmp[k]
            else:
                break
        test=base-minus
        ans=max(ans,test)

print(ans)

Submission status: Runtime Error

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N,K=MI()
    V=LI()
    
    ans=0
    import heapq
    
    #左からa個，右からb個とって，あまり分で負数を捨てる
    for a in range(K+1):
        for b in range(K+1):
            if a+b>K:
                break
            hq=[]
            heapq.heapify(hq)
            for i in range(a):
                heapq.heappush(hq,V[i])
            for j in range(b):
                heapq.heappush(hq,V[N-1-j])
                
            temp=0
            rem=K-(a+b)
            for i in range(a+b):
                v=heapq.heappop(hq)
                if v>=0:
                    temp+=v
                else:
                    if rem>0:
                        rem-=1
                    else:
                        temp+=v
                        
            ans=max(ans,temp)
            
    print(ans)
                
            

main()

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
v = list(map(int, input().split()))
reverse_v = v[::-1]
lst = [0] * (k + 1)
left = [[]]
right = [[]]
for i in range(1, n+1):
  left.append(v[:i])
  right.append(reverse_v[:i])

for cnt in range(1, k+1):
  rest = k - cnt
  total = 0
  for j in range(cnt+1):
    lst_j = left[j] + right[cnt-j]
    lst_j.sort()
    l = cnt
    for idx in range(cnt):
      if lst_j[idx] >= 0:
        l = idx
        break
    if l == cnt:
      value = 0
    else:
      flg = min(l, rest)
      value = sum(lst_j[flg:])
    if value > total:
      total = value
  lst[cnt] = total

ans = max(lst)
print(ans)

Submission status: Runtime Error

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

N,K = (int(x) for x in input().rstrip('\n').split())
vs = [int(x) for x in input().rstrip('\n').split()]
g = []
rest = K
for k in [K-1,K]:
  for b in range(K//2):
    t = k-b
    if t>N:
      t=N
    for i in range(t+1):
      v = []
      if i <t:
        v.extend(vs[:i])
        v.extend(vs[-(t-i):])
        for _ in range(b):
          if min(v)<0:
            v.remove(min(v))
          else:
            break
      else:
        v.extend(vs[:t])
        for _ in range(b):
          if min(v)<0:
          	v.remove(min(v))
      g.append(sum(v))
if max(g)<0:
  print(0)
else:
  print(max(g))

Submission status: Runtime Error

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

N,K = (int(x) for x in input().rstrip('\n').split())
vs = [int(x) for x in input().rstrip('\n').split()]
g = []
rest = K
for k in [K-1,K]:
  for b in range(K//2):
    t = k-b
    if t>N:
      t=N
    for i in range(t+1):
      v = []
      if i <t:
        v.extend(vs[:i])
        v.extend(vs[-(t-i):])
        for _ in range(b):
          if min(v)<0:
            v.remove(min(v))
          else:
            break
      else:
        v.extend(vs[:t])
        for _ in range(b):
          if min(v)<0:
          	v.remove(min(v))
      g.append(sum(v))
print(max(g))

Submission status: Runtime Error

Solution code:
from collections import deque

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

def bfs(s):
    seen = [0 for i in range(N+1)]
    d = [0 for i in range(N+1)]
    todo = deque([])
    now = s
    seen[now]=1
    todo.append(now)
    while 1:
      if len(todo)==0:break
      a = todo.popleft()
      for b in G[a]:
        if seen[b] == 0:
          seen[b] = 1
          todo.append(b)
          d[b] += d[a] + 1
  return d

d = bfs(v)

Submission status: Runtime Error

Solution code:
import heapq
from itertools import accumulate
n, k = map(int, input().split())
vs = list(map(int, input().split()))
vs_hq = vs.copy()
rsw_l = list(accumulate(vs))
rsw_r = vs.copy()
for i in reversed(range(n-1)):
    rsw_r[i] = rsw_r[i+1] + rsw_r[i]
rsw_l = [0] + rsw_l
rsw_r = rsw_r + [0]
n_minus_l = [0]*n
if vs[0] < 0:
    n_minus_l[0] = 1
for i in range(1,n):
    if vs[i] < 0:
        n_minus_l[i] = n_minus_l[i-1] + 1
    else:
        n_minus_l[i] = n_minus_l[i - 1]
n_minus_l = [0] + n_minus_l
n_minus_r = [0]*n
if vs[n-1] < 0:
    n_minus_r[n-1] = 1
for i in reversed(range(n-1)):
    if vs[i] < 0:
        n_minus_r[i] = n_minus_r[i+1] + 1
    else:
        n_minus_r[i] = n_minus_r[i+1]
n_minus_r = n_minus_r + [0]
res = 0
for i in range(min(n,k)+1):
    for j in range(k-i+1):
        tmp = rsw_l[i] + rsw_r[n-j]
        n_dis = min(k-i-j,n_minus_l[i]+n_minus_r[n-j])
        arr = []
        if i > 0:
            arr += vs[:i]
        if j > 0:
            arr += list(reversed(vs))[:j]
        if arr != []:
            tmp -= sum(sorted(arr)[:n_dis])
        res = max(res,tmp)
print(res)

Submission status: Runtime Error

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

def main(n,k,v):
    ruisekiL=[0]*(n+1)
    ruisekiR=[0]*(n+1)
    for i in range(1,n+1):
        ruisekiL[i]=ruisekiL[i-1]+v[i-1]
        ruisekiR[i]=ruisekiR[i-1]+v[n-i]
    vv=[]
    for i in range(n):
        vv.append((i+1,v[i]))
    vv.sort(key=lambda x:x[1])
    #print(vv)

    maxown=-10**7
    for kk in range(k+1):
        if n<kk:
            own=ruisekiL[n]
            for i in range(kk-n):
                own-=vv[i][1]
            #print(own)
            maxown=max(maxown,own)
        else:
            for l in range(kk//2+1):
                for i in range(kk-l+1):
                    j=kk-i-l
                    jj=n-j+1
                    own=ruisekiL[i]+ruisekiR[j]
                    #print(i,j,own)
                    m=0
                    mcnt=0
                    while(mcnt<l):
                        if i<vv[m][0] and vv[m][0]<jj:
                            m+=1
                            continue
                        #print(i,jj,vv[m])
                        own-=vv[m][1]
                        mcnt+=1
                        m+=1
                    #print(own)
                    maxown=max(own,maxown)
    return maxown

if __name__=='__main__':
    n,k,v=readinput()
    ans=main(n,k,v)
    print(ans)

Submission status: Runtime Error

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<=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: Runtime Error

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 = []
        cur1 = 0
        for i, x in enumerate(V):
            if i < m:
                ls.append(x)
                cur += 1
        cur2 = 0
        for i, x in enumerate(V[::-1]):
            if i < min(M-m, N-cur1):
                ls.append(x)
                cur2 += 1
        ls.sort()
        s = sum(ls)
        for i, x in enumerate(ls):
            if i < K-(cur1+cur2):
                s -= x
        ans = max(ans, s)
print(ans)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import heapq

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

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

ans = 0
for i in range(1, K+1):
    if i > 50:
        continue
    for j in range(i+1):
        tmp = 0
        q = V[:j] + V[N-i+j:]
        heapq.heapify(q)
        for _ in range(min(i, K-i)):
            tmp_min = heapq.heappop(q)
            ans = max(ans, sum(q))
            if tmp_min > 0:
                ans = max(ans, sum(q)+tmp_min)
                break

print(ans)

Submission status: Runtime Error

Solution code:
import heapq

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

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

ans = 0
for i in range(K+1):
    if i > 50:
        continue
    for j in range(i+1):
        tmp = 0
        q = V[:j] + V[N-i+j:]
        heapq.heapify(q)
        for _ in range(min(i, K-i)):
            tmp_min = heapq.heappop(q)
            ans = max(ans, sum(q))
            if tmp_min > 0:
                ans = max(ans, sum(q)+tmp_min)
                break

print(ans)