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

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

slice_L = [list(sorted(v[:i])) for i in range(N + 1)]
sum_L = [sum(slice_L[i]) for i in range(N + 1)]

slice_R = [list(sorted(v[N - 1 - i:])) for i in range(-1, N)]
sum_R = [sum(slice_R[i]) for i in range(N + 1)]
# print(slice_L)
# print(slice_R)

ans = 0
for put, pick in enumerate(tuple(range(K, 0, -1)), 0):
    for left in range(pick + 1):
        m_put = put
        right = pick - left
        t = sum(slice_L[left]) + sum(slice_R[right])
        sl_i = 0
        sr_i = 0
        # print(m_put)
        while m_put > 0:
            # print(right, sr_i, slice_R[right])
            if sl_i == left:
                if sr_i == right: break
                t -= slice_R[right][sr_i]
                sr_i += 1
            elif sr_i == right:
                t -= slice_L[left][sl_i]
                sl_i += 1
            elif slice_L[left][sl_i] < slice_R[right][sr_i]:
                t -= slice_L[left][sl_i]
                sl_i += 1
            elif slice_L[left][sl_i] > slice_R[right][sr_i]:
                # print('test')
                t -= slice_R[right][sr_i]
                sr_i += 1
            else:
                if sl_i + 1 == left:
                    if sr_i == right: break
                    t -= slice_R[right][sr_i]
                    sr_i += 1
                elif sr_i + 1 == right:
                    t -= slice_L[left][sl_i]
                    sl_i += 1
                else:
                    flg = False
                    k = 0
                    while slice_L[left][sl_i + k] == slice_R[right][sr_i + k]:
                        k += 1
                        if sl_i + k == left:
                            t -= slice_R[right][sr_i]
                            sr_i += 1
                            flg = True
                            break
                        elif sr_i + k == right:
                            t -= slice_L[left][sl_i]
                            sl_i += 1
                            flg = True
                            break
                    if not flg:
                        if sl_i + k == left and sr_i + k == right: break
                        if slice_L[left][sl_i + k] < slice_R[right][sr_i + k]:
                            t -= slice_L[left][sl_i]
                            sl_i += 1
                        elif slice_L[left][sl_i + k] > slice_R[right][sr_i + k]:
                            t -= slice_R[right][sr_i]
                            sr_i += 1
            m_put -= 1
        # print(pick, left, right, t, slice_R[right], slice_L[left])
        ans = max(ans, t)
print(ans)

Submission status: Runtime Error

Solution code:
import bisect

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

ans=0
for i in range(1,K+1):
    if i<=N:
        for j in range(i+1):
            right=V[:i-j]
            left=V[N-j:]
            right.extend(left)
            right.sort()
            index = bisect.bisect_left(right, 0)
            if index + i <= K:
                ans = max(ans, sum(right[index:]))
            else:
                les = K - i
                ans = max(ans, sum(right[les:]))
    else:
        rignt=V
        rignt.sort()
        index = bisect.bisect_left(right, 0)
        if index + i <= K:
            ans = max(ans, sum(right[index:]))
        else:
            les = K - i
            ans = max(ans, sum(tmp[les:]))



print(ans)

Submission status: Runtime Error

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

ans = 0
for i in range(k // 2):
    for j in range(k - i):
        a = v_sum[j] + v_sum[-1] - v_sum[-(k-i-j)]
        a -= sum(sorted(v[:j+1] + v[-(k-i-j):])[:i])
        ans = max(ans, a)

print(ans)

Submission status: Runtime Error

Solution code:
# coding:utf-8
# DDDDDDDDDDDDD

import math
import re

def main(params):
    n,q = params[0]
    ss = params[1:n+1]
    d = [int(i) for i in params[n+1:]]
    ng = []
    for i in d:
        infinite = True
        for j in ss:
            s,t,x = [int(k) for k in j.split()]
            if s - x <= i and t - x > i:
                print x
                infinite = False
                break
        if infinite == True:
            print -1

if __name__ == "__main__":
    n,q = [int(i) for i in raw_input().split()]
    cnt = n + q # TODO: edit here
    params = [[n,q]]
    for i in range(cnt):
        param = raw_input()
        params.append(param)
    main(params)

Submission status: Runtime Error

Solution code:
from copy import copy
from bisect import bisect_left

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

def p(k,v):
    ret = 0
    for i in range(k+1):
        vt = copy(v)
        vt = vt[:i]
        vt.sort(reverse=True)
        t = 0 
        #print(i,len(vt))
        for j in range(i):
            t += vt[j]
            if j+1 >= i*2-k and t > ret:
                ret = t
    return ret

def length(v):
    ret = 0
    for num in v:
        if num < 0:
            ret += 2
        else:
            ret += 1
    return ret
            
vr = copy(v)
vr.reverse()
ans = 0

k = min(k,length(v))
for i in range(k+1):
    t = p(i,v) + p(k-i,vr)
    print(i,p(i,v),p(k-i,vr),t)
    if t > ans:
        ans = t
print(ans)

Submission status: Runtime Error

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
Max = sys.maxsize
def l():
	return list(map(int,input().split()))
def m():
	return map(int,input().split())
def s(x):
	a = []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa == x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x):
	return " ".join(map(str,x))

n,m = m()

a = l()

su = 0
for i in range(n):
	ll = max(i,n-(m - i))
	for j in range(ll,n+1):
		q = []
		co = 0
		p = a[:i]
		pp = a[j:]
		for k in range(len(p)):
			if p[k] < 0:
				q.append(p[k])
		for k in range(len(pp)):
			if pp[k] < 0:
				q.append(pp[k])
		co += sum(p)
		co += sum(pp)
		q.sort()
		for k in range(max(len(q),j-ll)):
			co += abs(q[k])
		su = max(su,co)
print(su)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
# coding: utf-8

# In[1]:


import sys
#import numpy as np
#import itertools
input = sys.stdin.readline
N, K = map(int, input().split())
V = list(map(int, input().split()))


# In[2]:


#print(N, K)
#print(V)


# In[ ]:


"""
6 4
-10 8 2 1 2 6
"""


# In[29]:


if N < K:
    scs = []
    for i in range(K-N):
        scs.append(sorted(V[i:]))
    s = max(scs)
else:
    scs = []
    for i in range(K//2):
        #print("{}個返す".format(i))
        scss = []
        for j in range(K+1-i):
            #print("左から{}個　右から{}個/{}".format(j,K-j-i, K-i))
            if j == K-i:
                choices = V[:j]
            else:
                choices = V[:j] + V[-K+j+i:]
            #print(choices)
            #print(sorted(choices)[i:])
            scss.append(sum(sorted(choices)[i:]))
        scs.append(max(scss))
    s = max(scs)
    s = 0 if s<0 else s
print(s)


# In[ ]:

Submission status: Runtime Error

Solution code:
import numpy


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


memo = {}


def best_op(v_list, hand, k):
    if (tuple(v_list.tolist()), tuple(hand.tolist()), k) in memo:
        return memo[(tuple(v_list.tolist()), tuple(hand.tolist()), k)]
    # print('call ', v_list, hand, k)
    if k == 0:
        # print('return')
        return sum(hand)
    if k > 0:
        # print('a')
        # print(v_list, hand)
        v_list_a, hand_a, succ = op_a(v_list, hand)
        if succ:
            sum_a = best_op(v_list_a, hand_a, k - 1)
            if not (tuple(v_list_a.tolist()), tuple(hand_a.tolist()), k - 1) in memo:
                memo[(tuple(v_list_a.tolist()), tuple(hand_a.tolist()), k)] = sum_a
        else:
            sum_a = -10 ** 7 * k

        # print('b')
        # print(v_list, hand)
        v_list_b, hand_b, succ = op_b(v_list, hand)
        if succ:
            sum_b = best_op(v_list_b, hand_b, k - 1)
            if not (tuple(v_list_b.tolist()), tuple(hand_b.tolist()), k - 1) in memo:
                memo[(tuple(v_list_b.tolist()), tuple(hand_b.tolist()), k)] = sum_a
        else:
            sum_b = -10 ** 7 * k

        # print('c')
        v_list_c, hand_c, succ = op_c(v_list, hand)
        if succ:
            sum_c = best_op(v_list_c, hand_c, k - 1)
            if not (tuple(v_list_c.tolist()), tuple(hand_c.tolist()), k - 1) in memo:
                memo[(tuple(v_list_c.tolist()), tuple(hand_c.tolist()), k)] = sum_a
        else:
            sum_c = -10 ** 7 * k

        # print('d')
        v_list_d, hand_d, succ = op_d(v_list, hand)
        if succ:
            sum_d = best_op(v_list_d, hand_d, k - 1)
            if not (tuple(v_list_d.tolist()), tuple(hand_d.tolist()), k - 1) in memo:
                memo[(tuple(v_list_d.tolist()), tuple(hand_d.tolist()), k)] = sum_a
        else:
            sum_d = -10 ** 7 * k

        v_list_e, hand_e, succ = v_list, hand, True
        sum_e = best_op(v_list_e, hand_e, k - 1)

        # print(sum_a, sum_b, sum_c, sum_d)
        return max(sum_a, sum_b, sum_c, sum_d, sum_e)


def op_a(v_list, hand):
    if len(v_list) == 0:
        return v_list, hand, False
    value = v_list[0]
    v_list = numpy.delete(v_list, 0)
    hand = numpy.append(hand, value)
    return v_list, sorted(hand), True


def op_b(v_list, hand):
    if len(v_list) == 0:
        return v_list, hand, False
    value = v_list[len(v_list) - 1]
    v_list = numpy.delete(v_list, len(v_list) - 1)
    hand = numpy.append(hand, value)
    return v_list, sorted(hand), True


def op_c(v_list, hand):
    if len(hand) == 0:
        return v_list, hand, False
    min_val = hand[0]
    hand = numpy.delete(hand, 0)
    v_list = numpy.insert(v_list, 0, min_val)
    return v_list, sorted(hand), True


def op_d(v_list, hand):
    if len(hand) == 0:
        return v_list, hand, False
    min_val = hand[0]
    hand = numpy.delete(hand, 0)
    v_list = numpy.append(v_list, min_val)
    return v_list, sorted(hand), True


if __name__ == '__main__':
    [n, k] = li()
    v_list = li()
    v_list = numpy.array(v_list, dtype=numpy.int64)
    hand = numpy.array([], dtype=numpy.int64)

    # print(n, k)
    # print(v_list)
    print(max(best_op(v_list, hand, k), 0))

Submission status: Runtime Error

Solution code:
from heapq import heappush, heappop
from collections import deque

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

ans = 0

for i in range(K+1):
    sup = min(i,K)
    for l in range(sup+1):
        for r in range(sup+1-l):
            j = min(i-r-l,r+l)
            hq = []
            dq = deque(V)
            for _ in range(l):
                item = dq.popleft()
                heappush(hq, item)
            for _ in range(r):
                item = dq.pop()
                heappush(hq, item)
            for _ in range(j):
                heappop(hq)
            res = sum(hq)
            ans = max(ans,res)

print(ans)

Submission status: Runtime Error

Solution code:
a,b = map(int,input().split())
A = list(map(int,input().split()))
c = 0
d = 0
tmp1 = 0
tmp2 = 0
count1 = 0
count2 = 0
M = 0
m = 0
while True:
    tmp1 = c
    c = A[0+count1]
    count1= count1 + 1
    if c >= tmp1:
        M = c
    if (count1 + count2) > b:
        break
    tmp2 = d
    d = A[-1-count2]
    count2 = count2 + 1
    if d >= tmp2:
        m = d
    if (count1 + count2) > b:
        break
print(M+m)

Submission status: Runtime Error

Solution code:
from collections import deque

N, K = map(int, input().split())
d = list(map(int, input().split()))
left = [0]
left_m = []
right = [0]
right_m = []
for i, l, r in zip(range(K), d, d[::-1]):
    left.append(left[i] + l)
    left_m.append(l if l < 0 else 0)
    right.append(right[i] + r)
    right_m.append(r if r < 0 else 0)
point = 0
for i in range(K + 1):
    for j in range(K + 1 - i):
        p = K - i - j
        minus = list(sorted(left_m[:i] + right_m[:j]))
        point = max(point, left[i] + right[j] - sum(minus[:p]))
print(point)

Submission status: Runtime Error

Solution code:
from heapq import heappush, heappop
from collections import deque

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

ans = 0

for i in range(K+1):
    for l in range(min(i+1,N+1)):
        for r in range(i+1-l):
            j = min(i-r-l,r+l)
            hq = []
            dq = deque(V)
            for _ in range(l):
                item = dq.popleft()
                heappush(hq, item)
            for _ in range(r):
                item = dq.pop()
                heappush(hq, item)
            for _ in range(j):
                heappop(hq)
            res = sum(hq)
            ans = max(ans,res)

print(ans)

Submission status: Runtime Error

Solution code:
from copy import deepcopy

def IntToMani(N, K):
    ret = []
    start = N
    while start / 4 > 0:
        ret.append(start % 4)
        start /= 4
    ret.append(start % 4)
    while len(ret) < K:
        ret.insert(0, 0)
    return ret

def addToKeep(_keep, _ele):
    low_ind = 0
    up_ind = len(_keep) - 1
    found = None
    while (up_ind - low_ind) > 1:
        mid = (up_ind + low_ind) / 2
        if _keep[mid] < _ele:
            low_ind = mid
        elif _keep[mid] > _ele:
            up_ind = mid
        elif _keep[mid] == _ele:
            found = mid
            break
    if found is not None:
        cnt = found
    else:
        cnt = up_ind
    _keep.insert(cnt, _ele)

def solve():
    N, K = [int(_) for _ in raw_input().split()]
    V = [int(_) for _ in raw_input().split()]
    MAX_CASE = 1<<(2*K)
    ans = 0
    for i in range(MAX_CASE):
        tmpV = deepcopy(V)
        mani = IntToMani(i,K)
        keep = []
        sum_keep = 0
        # tmp_ret = []
        for _man in mani:
            if _man == 0:
                if len(tmpV) == 0:
                    break
                else:
                    ele = tmpV.pop(0)
                    addToKeep(keep, ele)
                    sum_keep += ele
            elif _man == 1:
                if len(tmpV) == 0:
                    break
                else:
                    ele = tmpV.pop()
                    addToKeep(keep, ele)
                    sum_keep += ele
            else:
                if len(keep) == 0:
                    break
                else:
                    ele = keep.pop(0)
                    sum_keep -= ele
                    if _man == 2:
                        tmpV.insert(0, ele)
                    elif _man == 3:
                        tmpV.append(ele)
            # addToKeep(tmp_ret, sum_keep)
            ans = max(ans, sum_keep)
        # ans = max(ans, tmp_ret[-1])
    print ans

if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
from heapq import heappush, heappop, heapify

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

# N jewels in dequeue D
# at most K operations
# 1 <= N <= 50
# 1 <= K <= 100
# -10000000 <= Vi <= 10000000

# Operation A, B: Remove left or right
# Operation C, D: Add to left or right

S = 0
for take in range(K):
    for takeL in range(take + 1):
        for takeR in range(take - takeL + 1):
            hand = []
            for i in range(takeL):
                if i >= len(V):
                    break
                heappush(hand, V[i])
            for i in range(takeR):
                if N - i - 1 >= len(V):
                    break
                heappush(hand, V[N- i - 1])
            for i in range(K - take):
                if not hand:
                    break
                heappop(hand)
                s = sum(hand)
                S = max(s, S)
print(S)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
# coding: utf-8

# In[1]:


import sys
#import numpy as np
#import itertools
input = sys.stdin.readline
N, K = map(int, input().split())
V = list(map(int, input().split()))


# In[2]:


#print(N, K)
#print(V)


# In[ ]:


"""
6 4
-10 8 2 1 2 6
"""


# In[29]:


scs = []
for i in range(K//2):
    #print("{}個返す".format(i))
    scss = []
    for j in range(K+1-i):
        #print("左から{}個　右から{}個/{}".format(j,K-j-i, K-i))
        if j == K-i:
            choices = V[:j]
        else:
            choices = V[:j] + V[-K+j+i:]
        #print(choices)
        #print(sorted(choices)[i:])
        scss.append(sum(sorted(choices)[i:]))
    scs.append(max(scss))
s = max(scs)
s = 0 if s<0 else s
print(s)


# In[ ]:

Submission status: Runtime Error

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

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

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


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

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
vs = list(map(int, input().split()))
ps = list(filter(lambda x: x > 0, vs))
ns = list(filter(lambda x: x < 0, vs))
zs = list(filter(lambda x: x == 0, vs))
P = len(ps)

should_take_nagative_gem = 1 if max(ns) + min(ps) > 0 else -1

num_get_positive = P if (K-P)%2==0 else P + should_take_nagative_gem

def feasible(c, P, K):
    return True

# P C num_get_positiveが探索対象となる。

import itertools
cs = itertools.combinations(vs, num_get_positive)
answer = 0
for c in cs:
    if all([p in c for p in ps]):
        # 探索する価値がある
        if feasible(c, P, K):
            s = sum(c)
            answer = s if s > answer else answer

print(answer)

Submission status: Runtime Error

Solution code:
from heapq import heappush, heappop, heapify

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

# N jewels in dequeue D
# at most K operations
# 1 <= N <= 50
# 1 <= K <= 100
# -10000000 <= Vi <= 10000000

# Operation A, B: Remove left or right
# Operation C, D: Add to left or right

S = 0
for take in range(K):
    for takeL in range(take + 1):
        for takeR in range(take - takeL + 1):
            hand = []
            for i in range(takeL):
                heappush(hand, V[i])
            for i in range(takeR):
                heappush(hand, V[N- i - 1])
            for i in range(K - take):
                if not hand:
                    break
                heappop(hand)
                s = sum(hand)
                S = max(s, S)
print(S)

Submission status: Runtime Error

Solution code:
from heapq import heappush, heappop
from collections import deque

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

ans = 0

for i in range(K+1):
    for l in range(i+1):
        for r in range(i+1-l):
            j = min(i-r-l,r+l)
            hq = []
            dq = deque(V)
            for _ in range(l):
                if dq:
                    item = dq.popleft()
                    heappush(hq, item)
            for _ in range(r):
                if dq:
                    item = dq.pop()
                    heappush(hq, item)
            for _ in range(j):
                heappop(hq)
            res = sum(hq)
            ans = max(ans,res)
        
print(ans)

Submission status: Runtime Error

Solution code:
import math
import sys
sys.setrecursionlimit(10 ** 6 + 10)
from collections import defaultdict

def get_data(data_left, nokori):
    # print(data_left, nokori)
    while 1:
        if len(data_left) == 0:
            break
        if data_left[-1] <= 0:
            data_left.pop(-1)
            nokori += 1
        else:
            break

    # print(data_left, nokori)

    while nokori > 0:
        if len(data_left) == 0:
            break
        min_data = min(data_left)
        if min_data < 0:
            data_left.pop(data_left.index(min_data))
            nokori -= 1
        else:
            break
        # print('uuu', data_left)

    # print(data_left)

    while 1:
        if len(data_left) == 0:
            break
        saigo = data_left[-1]
        min_data = min(data_left)

        if saigo + min_data < 0:
            data_left.pop(-1)
            if len(data_left) == 0:
                nokori += 1
                break
            # print(data_left.index(min_data))
            data_left.pop(data_left.index(min_data))
        else:
            break

    return nokori, data_left

def main():
    num_houseki, num_sousa = map(int, input().split())
    data = list(map(int, input().split()))


    ans = 0


    # dp = defaultdict(int)

    for i in range(num_sousa + 1):

        nokori = 0
        left_ind = min(i, num_houseki)
        nokori += i - left_ind
        righ_ind = max(left_ind, num_houseki - num_sousa + i)
        nokori += num_sousa - i - num_houseki + righ_ind
        data_left = data[:left_ind]
        data_right = data[righ_ind:]

        # print('<><<><<><')
        # print(data_left)
        # print(data_right)


        nokori, data_left = get_data(data_left, nokori)
        nokori, data_right = get_data(data_right[::-1], nokori)
        data_right = data_right[::-1]

        # print('----')
        # print(data_left)
        # print(data_right)

        kari = sum(data_right) + sum(data_left)
        if kari > ans:
            ans = kari

    print(ans)







if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
# coding: utf-8

# In[1]:


import sys
#import numpy as np
#import itertools
input = sys.stdin.readline
N, K = map(int, input().split())
V = list(map(int, input().split()))


# In[2]:


#print(N, K)
#print(V)


# In[ ]:


"""
6 4
-10 8 2 1 2 6
"""


# In[29]:


scs = []
for i in range(K//2):
    #print("{}個返す".format(i))
    scss = []
    for j in range(K+1-i):
        #print("左から{}個　右から{}個/{}".format(j,K-j-i, K-i))
        if j == K-i:
            choices = V[:j]
        else:
            choices = V[:j] + V[-K+j+i:]
        #print(choices)
        #print(sorted(choices)[i:])
        scss.append(sum(sorted(choices)[i:]))
    scs.append(max(scss))
print(max(scs))


# In[ ]:

Submission status: Runtime Error

Solution code:
N,K=map(int,input().split())
V=list(map(int,input().split()))
ans=[0]
for i in range(K+1):
    #print(i)
    for j in range(i+1):
        if N<=j:
            temp=sorted(V)
        elif j-i!=0:
            temp=sorted(V[:j]+V[j-i:])
        else:
            temp=sorted(V[:j])
        t=0
        for k in range(i):
            if temp[k]>=0:
                t=k+1
                break
        #print(temp,t)
        #if t==0:
        #    print(":",0)
        if t>K-i:
            #print(":",temp[K-i:])
            ans.append(sum(temp[K-i:]))
        elif (K-1-t)%2==1:
            if t>=2:
                #print(":",max(sum(temp[t-2:]),sum(temp[t:])))
                ans.append(max(sum(temp[t-2:]),sum(temp[t:])))
            else:
                #print(":",sum(temp[t:]))
                ans.append(sum(temp[t:]))
        else:
            #print(":",sum(temp[t-1:]))
            ans.append(sum(temp[t-1:]))
print(max(ans))

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
listV = list(map(int, input().split()))
haveL=[]
memo={}
def maxTaker(haveL, listV, k):
    strH = "".join(list(map(str, haveL)))
    strV = "".join(list(map(str, haveL)))
    key = strH+strV+str(k)
    if key in memo:
        return memo[key]
    else:
        if k == 1:
            if haveL != [] and listV != []:
                minHave = min(haveL)
                memo[key] = max(0, -1*minHave, listV[0], listV[-1])
                return max(0, -1*minHave, listV[0], listV[-1])
            elif haveL == []:
                memo[key] = max(0, listV[0], listV[-1])
                return max(0, listV[0], listV[-1])
            else:
                minHave = min(haveL)
                memo[key] = max(0, -1*minHave)
                return max(0, -1*minHave)

        else:
            if haveL!=[] and listV!=[]:
                haveL.sort()
                minHave = haveL[0]
                listV1 = []
                listV1.extend(listV)
                listV2 = [minHave]
                listV1.extend([minHave])
                listV2.extend(listV)
                haveL1 = [listV[0]]
                haveL2 = [listV[-1]]
                haveL1.extend(haveL)
                haveL2.extend(haveL)
                memo[key] = max(0, maxTaker(haveL[1:], listV1, k-1)-minHave, maxTaker(haveL[1:], listV2, k-1)-minHave,
                                maxTaker(haveL1, listV[1:], k-1)+listV[0], maxTaker(haveL2, listV[:len(listV)-1], k-1)+listV[-1])
                return max(0, maxTaker(haveL[1:], listV1, k-1)-minHave, maxTaker(haveL[1:], listV2, k-1)-minHave, maxTaker(haveL1, listV[1:], k-1)+listV[0], maxTaker(haveL2, listV[:len(listV)-1], k-1)+listV[-1])
            elif haveL == []:
                haveL1 = [listV[0]]
                haveL2 = [listV[-1]]
                haveL1.extend(haveL)
                haveL2.extend(haveL)
                memo[key] = max(0, maxTaker(haveL1, listV[1:], k-1)+listV[0],
                                maxTaker(haveL2, listV[:len(listV)-1], k-1)+listV[-1])
                return max(0,maxTaker(haveL1, listV[1:], k-1)+listV[0], maxTaker(haveL2, listV[:len(listV)-1], k-1)+listV[-1])
            else:
                minHave = min(haveL)
                index=0
                while index < len(haveL):
                    if haveL[index] == minHave:
                        del haveL[index]
                        break
                    else:
                        index+=1
                listV1 = []
                listV1.extend(listV)
                listV2 = [minHave]
                listV1.extend([minHave])
                listV2.extend(listV)
                memo[key] = max(0, maxTaker(haveL, listV1, k-1)-minHave, maxTaker(haveL, listV2, k-1)-minHave)
                return max(0, maxTaker(haveL, listV1, k-1)-minHave, maxTaker(haveL, listV2, k-1)-minHave)

print(maxTaker(haveL, listV, k))

Submission status: Runtime Error

Solution code:
a,b = map(int,input().split())
A = list(map(int,input().split()))
c = 0
d = 0
tmp1 = 0
tmp2 = 0
count1 = 0
count2 = 0
M = 0
m = 0
while True:
    tmp1 = c
    c = A[1+count1]
    count1= count1 + 1
    if c >= tmp1:
        M = c
    if (count1 + count2) > b:
        break
    tmp2 = d
    d = A[-1-count2]
    count2 = count2 + 1
    if d >= tmp2:
        m = d
    if (count1 + count2) > b:
        break
print(M+m)

Submission status: Runtime Error

Solution code:
from collections import deque

N, K = map(int, input().split())
d = list(map(int, input().split()))
left = [0]
left_m = [0]
right = [0]
right_m = [0]
for i, l, r in zip(range(K), d, d[::-1]):
    left.append(left[i] + l)
    left_m.append(l if l < 0 else 0)
    right.append(right[i] + r)
    right_m.append(r if r < 0 else 0)
point = 0
for i in range(K + 1):
    for j in range(K + 1 - i):
        minus = list(sorted(left_m[:i + 1] + right_m[:j + 1]))
        point = max(point, left[i] + right[j] - sum(minus[:K - i - j]))
print(point)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import numpy as np
import copy
N,K = map(int,input().split())
V = list(map(int,input().split()))
# N = 17
# K = 100
# V = [i for i in range(N)]


V = [0 for i in range(N)] + V + [0 for i in range(N)] 


dp = {}

# discardフラグを立てて，一度捨てると取れないように．
def search(start, end, k, own, discard=False):
    if k==K:
        return sum(own)
    key = tuple(own)
    if key in dp:
        return dp[key]
    val_Default = sum(own)
    val_A,val_B = 0,0
    if end-start >= 0 and not discard:
        val_A = search(start+1, end, k+1, own + [V[start]])
        val_B = search(start, end-1, k+1, own + [V[end]])
    if len(own) == 0 and discard:
        return val_Default
    val_Cs = []
    val_Ds = []
    for i,o in enumerate(own):
        own_new = copy.copy(own)
        own_new.pop(i)
        val_Cs.append(search(-1, -1, k+1, own_new, discard=True) )
        # val_Cs.append(search(start-1, end, k+1, own_new, discard=True) )
        # val_Ds.append(search(start, end+1, k+1, own_new, discard=True) )
    # print([val_Default, val_A, val_B], val_Cs , val_Ds)
    # dp[key] = max([val_Default, val_A, val_B] + val_Cs + val_Ds)
    dp[key] = max([val_Default, val_A, val_B] + val_Cs)
    # print(own, [val_Default, val_A, val_B], val_Cs, val_Ds)
    return dp[key]

r = search(N, 2*N-1, 0, [])
print(r)