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:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
input = sys.stdin.readline
 
# bisect_left(lists, 3)
# bisect_right(lists, 3)

# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

def main():
	N, K = map(int, input().split(" "))
	#N = int(input())
	#S = input()
	V = input().split(" ")
	V = [int(s) for s in V]

	ptn = []
	for i in range(K):
		tmp = K - i
		ptn.append((i, tmp))

	ans = 0
	for i in ptn:
		L, R = i
		tmp = 0
		for i in range(L):
			tmp += V[i]
		for i in range(R):
			tmp += V[-i-1]
		
		if tmp > ans:
			ans = tmp

	print(ans)

if __name__ == "__main__":
	main()

Submission status: Runtime Error

Solution code:
import copy
import heapq
from collections import deque

N, K = [int(i) for i in input().split()]
V = deque([int(i) for i in input().split()])


def dfs(queue, havings, value, k):
    if k == 0:
        return value
    # 1
    v1 = copy.copy(queue)
    h1 = copy.copy(havings)
    a1 = v1.popleft()
    if a1 < 0:
        heapq.heappush(h1, a1)
    d1 = dfs(v1, h1, value+a1, k-1)

    # 2
    v2 = copy.copy(queue)
    h2 = copy.copy(havings)
    a2 = v2.pop()
    if a2 < 0:
        heapq.heappush(h2, a2)
    d2 = dfs(v2, h2, value+a2, k-1)

    # 2
    if k <= len(havings):
        v3 = copy.copy(queue)
        h3 = copy.copy(havings)
        hp3 = heapq.heappop(h3)
        v3.appendleft(hp3)
        d3 = dfs(v3, h3, value-hp3, k-1)

        v4 = copy.copy(queue)
        h4 = copy.copy(havings)
        hp4 = heapq.heappop(h4)
        v4.append(hp4)
        d4 = dfs(v4, h4, value-hp4, k-1)

        return max(d1, d2, d3, d4, value)
    return max(d1, d2, value)


res = dfs(V, [], 0, K)
print(res)

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
V = list(map(int, input().split()))
INF_MIN = -(10**10)
l = [[INF_MIN] * (K+1) for i in range(N+1)]
r = [[INF_MIN] * (K+1) for i in range(N+1)]

pop_sum = 0
for i in range(N+1):
    if i == 0:
        pop_sum = 0
        l[i][0] = 0
        r[i][0] = 0
        popV = []
    else:
        pop_sum += V[i-1]
        popV = list(sorted(V[0:i]))
        l[i][0] = pop_sum
    for k in range(1, K+1):
        if not (k-1 < len(popV)) or popV[k-1] > 0:
            l[i][k] = l[i][k-1]
        else:
            l[i][k] = l[i][k-1] - popV[k-1]

pop_sum = 0
for i in range(N+1):
    if i == 0:
        pop_sum = 0
        r[i][0] = 0
        popV = []
    else:
        pop_sum += V[N-i]
        popV = list(sorted(V[N-i:N]))
        r[i][0] = pop_sum
    for k in range(1, K+1):
        if not (k-1 < len(popV)) or popV[k-1] > 0:
            r[i][k] = r[i][k-1]
        else:
            r[i][k] = r[i][k-1] - popV[k-1]

#print(l)
#print(r)

max_val = INF_MIN
imax = min(N, K)
for i in range(imax+1):
    for k in range(K-i+1):
        for j in range(K-i-k+1):
            val = l[i][k] + r[j][K-i-k-j]
            if val > max_val:
                max_val = val
                #print(i, j, k, l[i][k], r[j][K-i-k-j])


print(max_val)

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:
    k-=n
    heapify(v)
    for i in range(k):
        if len(v)>0:
            heappop(v)
        ans.append(sum(v))
    print(max(ans))
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:
from copy import deepcopy
N, K = map(int, input().split())
V = list(map(int, input().split()))
Lsum = [0]
Rsum = [0]
Lnegs = [[]]
Rnegs = [[]]
for i in range(N):
    Lsum.append(Lsum[i]+V[i])
    Rsum.append(Rsum[i]+V[N-i-1])
    Lnegs_cp = deepcopy(Lnegs[i])
    if V[i] < 0:
        Lnegs_cp.append(V[i])
        Lnegs_cp = sorted(Lnegs_cp)
    Lnegs.append(Lnegs_cp)
    Rnegs_cp = deepcopy(Rnegs[i])
    if V[N-i-1] < 0:
        Rnegs_cp.append(V[N-i-1])
        Rnegs_cp = sorted(Rnegs_cp)
    Rnegs.append(Rnegs_cp)

ans = 0

for dig in range(K+1):
    n_del = K - dig
    for ldig in range(dig+1):
        rdig = dig - ldig
        LRsum = Lsum[ldig] + Rsum[rdig]
        negs = []
        for neg in Lnegs[ldig]:
            negs.append(neg)
        for neg in Rnegs[rdig]:
            negs.append(neg)
        negs = sorted(negs)
        for i in range(min(n_del, len(negs))):
            LRsum -= negs[i]
        ans = max(ans, LRsum)

print(ans)

# for llim in range(N+1):
#     rlim = N - llim
#     lmax = -1001001001
#     for k0 in range(min(K, llim)):
#         kh = min(K, llim) - k0
#         s0 = Lsum[k0]
#         s1 = 0
#         for l in range(min(len(Lnegs[k0]),kh)):
#             s1 -= Lnegs[k0][l]
#         lmax = max(lmax, s0+s1)
#         rmax = -1001001001
#         for k1 in range(min(K - k0, rlim)):
#             kh = min(K - k0, rlim) - k1
#             s0 = Rsum[k1]
#             s1 = 0
#             for l in range(min(len(Rnegs[k1]),kh)):
#                 s1 -= Rnegs[k1][l]
#             rmax = max(rmax, s0+s1)
#         ans = max(ans, lmax + rmax)

# print(ans)

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Your code here!

N, K = map(int, input().rstrip().split(' '))
X = [0] + list(map(int, input().rstrip().split(' ')))

sorted_left_X = []
sorted_right_X = []
sorted_remove_X = []
for i in range(N+1):
    sorted_left_X.append(sorted([x for x in X[:i] if x < 0]))
    sorted_right_X.append(sorted([x for x in X[::-1][:i] if x < 0]))
    
    sorted_remove_X.append(sorted([x for x in X[:i] if x < 0] + [x for x in X[::-1][:i] if x < 0]))

cum_X = []
cum = 0
for x in X:
    cum += x
    cum_X.append(cum)

max_count = 0
for k in range(1,K+1):
    for i in range(k+1):
        num_left_removed = i
        num_right_removed = k - i
        temp = sorted(sorted_left_X[i] + sorted_right_X[k-i])
        temp2 = sum(temp[:min(len(temp), K-k)])
        max_count = max(cum_X[i] - cum_X[0] + cum_X[-1] - cum_X[i+N-k] - temp2, max_count)

print(max_count)

Submission status: Runtime Error

Solution code:
N,K=map(int,input().split())
V=list(map(int,input().split()))
ans=0
KK=K
if K>N:
    KK=N
for i in range(KK+1):
    j=KK-i
    a=V[:i]
    b=V[N-j:]
    ans=max(ans,sum(a)+sum(b))
    k=sum(a)+sum(b)
    c=a+b
    c.sort(reverse=True)
    W=K+max(0,K-N)
    W-=2
    while(W>0):
        if c==[]:
            break
        t=c.pop()
        if t in a:
            a.remove(t)
        else:
            b.remove(t)
        if a!=[] and b!=[] :
            if a[-1]<=b[0]:
                h=a.pop(-1)
            else:
                h=b.pop(0)
        elif a!=[] and b==[]:
            h=a.pop(-1)
        elif b!=[] and a==[]:
            h=b.pop(0)
        else:
            break
        k=k-t-h
        ans=max(k,ans)
        W-=2
print(ans)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, K, V):
    ans = 0
    for i in range(0, K//2):
        for j in range(i, K+1):
            l = V[:j-i]
            r = V[N-(K-j):]
            if len(l) + len(r) > N:
                lr = V[:]
            else:
                lr = l + r
            lr.sort(reverse=True)

            for _ in range(K - len(lr)):
                if lr[-1] < 0:
                    lr.pop()
                else:
                    break
            ans = max(ans, sum(lr))

    return ans


def main():
    N, K = read_int_n()
    V = read_int_n()
    print(slv(N, K, V))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
V = list(map(int, input().split()))
INF_MIN = -(10**10)
l = [[INF_MIN] * (K+1) for i in range(N+1)]
r = [[INF_MIN] * (K+1) for i in range(N+1)]

pop_sum = 0
for i in range(N+1):
    if i == 0:
        pop_sum = 0
        l[i][0] = 0
        r[i][0] = 0
        popV = []
    else:
        pop_sum += V[i-1]
        popV = list(sorted(V[0:i]))
        l[i][0] = pop_sum
    for k in range(1, K+1):
        if not (k-1 < len(popV)) or popV[k-1] > 0:
            l[i][k] = l[i][k-1]
        else:
            l[i][k] = l[i][k-1] - popV[k-1]

pop_sum = 0
for i in range(N+1):
    if i == 0:
        pop_sum = 0
        r[i][0] = 0
        popV = []
    else:
        pop_sum += V[N-i]
        popV = list(sorted(V[N-i:N]))
        r[i][0] = pop_sum
    for k in range(1, K+1):
        if not (k-1 < len(popV)) or popV[k-1] > 0:
            r[i][k] = r[i][k-1]
        else:
            r[i][k] = r[i][k-1] - popV[k-1]

#print(l)
#print(r)

max_val = INF_MIN
for i in range(N):
    for k in range(K+1-i):
        for j in range(K-i-k+1):
            val = l[i][k] + r[j][K-i-k-j]
            if val > max_val:
                max_val = val
                #print(i, j, k, l[i][k], r[j][K-i-k-j])


print(max_val)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun May 26 20:56:05 2019

@author: Yamazaki Kenichi
"""
import heapq

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

ans = 0
for i in range(K):
    for j in range(K-i+1):
        tmp = 0
        minus = [0]
        for k in range(K-i):
            tmp += V[k-j]
            heapq.heappush(minus,V[k-j])
#            print(tmp,minus)
        tmp += (-sum(minus[:i]))
#        print(ans,tmp,i,j,k)
        ans = max(ans,tmp)
    
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque

n,k = list(map(int,input().split()))
v = list(map(int,input().split()))
d = deque(v)
# print(d)

ansscore = 0
for i in range(4**k):
    tot = format(i,'b').zfill(k*2)
    # print(tot)
    target =  deque(v)
    score = 0
    hand = []
    # inst = []
    while len(tot) > 0:
        cmd = tot[-2:]    
        if cmd == '00':
            s = target.pop()
            hand.append(s) 
            # inst.append('A')
        elif cmd == '01':
            s = target.popleft()
            hand.append(s)
            # inst.append('B')
        elif cmd == '10':
            if len(hand) > 0:
                s = min(hand)
                hand.remove(s)
                target.append(s)
            # inst.append('C')
        elif cmd == '11':
            if len(hand) > 0:
                s = min(hand)
                hand.remove(s)
                target.appendleft(s)
            # inst.append('D')
        tot = tot[:-2]
        score = max(sum(hand),score)
    ansscore = max(ansscore,score)
    if i > (4**k/2):
        break
print(ansscore)

Submission status: Runtime Error

Solution code:
N,K= map(int,input().split())
D = list(map(int,input().split()))
from itertools import accumulate
acc = [0]+list(accumulate(D, lambda x,y:x+y))
mx = 0
for k in range(K+1): # k 回とる
    rest = K-k # rest回まで捨てることができる
    for l in range(1, min(k+1, N)): # 左から何個とるか
        r = k-l
        left = acc[l]
        right = acc[N]-acc[N-r]
        tmp = left+right
        tmpl = D[:l]
        tmpr = D[N-r:N]
        minus = sorted([i for i in tmpl+tmpr if i < 0])
        tmp -= sum(minus[:rest])
        mx = max(mx, tmp)
print(mx)

Submission status: Runtime Error

Solution code:
from heapq import*
from copy import*
n,k=map(int,input().split())
*v,=map(int,input().split())
v2=deepcopy(v)
motimono=[]
ans=[]
if k>=n:
    v*=2
    for j in range(1,k+1):
        try:
            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))
        except:
            continue
    motimono=deepcopy(d2)
    k-=n
    for i in range(k):
        heappop(motimono)
        ans.append(sum(motimono))
    print(max(ans))
else:
    v*=2
    for j in range(1,k+1):
        try:
            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))
        except:
            continue
    print(max(ans))

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
v = list(map(int, input().split()))
maxvalue = 0
for l in range(k+1):
    r = k - l
    leftmax = 0 
    for take in range(l+1):
        ava = sorted(v[:take])
        value = sum(ava)
        for back in range(min(take, l - take, n)):
            if ava[back] >= 0:
                break
            else:
                value -= ava[back]
        leftmax = max(leftmax, value)
    rightmax = 0
    for take in range(r+1):
        ava = sorted(v[n-take:])
        value = sum(ava)
        for back in range(min(take, r - take, n)):
            if ava[back] >= 0:
                break
            else:
                value -= ava[back]
        rightmax = max(rightmax, value)
    maxvalue = max(maxvalue, leftmax + rightmax)
print(maxvalue)

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
V = list(map(int, input().split()))
hand = []
ps = []
def func(V, hand, K):
    if K < 1:
        ps.append(hand)
        return
    if len(hand) > 0 and min(hand) < 0:
        hand_ = hand[:]
        hand_, min_val = handPop(hand_)
        C = func([min_val] + V, hand_, K-1)
        D = func(V + [min_val], hand_, K-1)
        A = func(V[1:], hand+[V[0]], K-1)
        B = func(V[:-1], hand+[V[-1]], K-1)
    else:
        A = func(V[1:], hand+[V[0]], K-1)
        B = func(V[:-1], hand+[V[-1]], K-1)

    
func(V, hand, K)
v_max = max([sum(x) for x in ps])
print(v_max if v_max > 0 else 0)

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:
    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))
            if len(motimono)==0:
                break
            heapify(motimono)
            for i in range(k-j):
                if len(motimono)>0:
                    heappop(motimono)
#                print(motimono)
                ans.append(sum(motimono))
    motimono=v
    k-=n
    for i in range(k):
        heappop(motimono)
        ans.append(sum(motimono))
    print(max(ans))
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))
            if len(motimono)==0:
                break
            heapify(motimono)
            for i in range(k-j):
                if len(motimono)>0:
                    heappop(motimono)
#                print(motimono)
                ans.append(sum(motimono))
    print(max(ans))

Submission status: Runtime Error

Solution code:
from collections import deque

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

if K >= N:
    print(sum([v for v in dq if dq >= 1]))
else:
    dq = deque(dq, maxlen=len(dq))
    print(100)

Submission status: Runtime Error

Solution code:
N, K = [int(x) for x in input().split(" ")]
D = [int(x) for x in input().split(" ")]
i = 0
j = len(D) - 1
memo = dict()

hands = set()

steps = 0

def maxSum(d, hands, k):
    if k == 0:
        return 0

    key = f"{str(d)}::{str(hands)}::{k}"
    if key in memo:
        return memo[key]
    
    patterns = [sum(hands)]

    if len(d) > 0:
        el = d[0]
        patterns.append(d[0] + maxSum(d[1:], hands.union(set([el])), k - 1))
        if len(d) > 1:
            el = d[-1]
            patterns.append(d[-1] + maxSum(d[:-1], hands.union(set([el])), k - 1))

    if hands:
        m = min(hands)
        newHand = hands.difference(set([m]))
        patterns.append(maxSum([m] + d, newHand, k - 1) - m)
        patterns.append(maxSum(d + [m], newHand, k - 1) - m)

    res = max(patterns)
    return res
        

print(maxSum(D, set(), K))

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):
    j=K-i
    a=V[:i]
    b=V[N-j:]
    ans=max(ans,sum(a)+sum(b))
    k=sum(a)+sum(b)
    c=a+b
    c.sort(reverse=True)
    W=K
    W-=2
    while(W>0):
        if c==[]:
            break
        t=c.pop()
        if t in a:
            a.remove(t)
        else:
            b.remove(t)
        if a!=[] and b!=[] :
            if a[-1]<=b[0]:
                h=a.pop(-1)
            else:
                h=b.pop(0)
        elif a!=[] and b==[]:
            h=a.pop(-1)
        elif b!=[] and a==[]:
            h=b.pop(0)
        else:
            break
        k=k-t-h
        ans=max(k,ans)
        W-=2
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque

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

if K >= N:
    print(sum((v for v in dq if dq >= 1)))
else:
    dq = deque(dq, maxlen=len(dq))
    print(100)

Submission status: Runtime Error

Solution code:
from collections import deque

dp = {}

def dfs(N, K, k, have, q):
  if k == K:
    return sum(have)
  else:
    if not ((k, tuple(q)) in dp):
      a = [sum(have)]
      if len(q) > 0:
        tmp_q = q.copy()
        tmp_have = have.copy()
        v = tmp_q.popleft()
        tmp_have.append(v)
        a.append(dfs(N, K, k+1, tmp_have, tmp_q))
        tmp_q = q.copy()
        tmp_have = have.copy()
        v = tmp_q.pop()
        tmp_have.append(v)
        a.append(dfs(N, K, k+1, tmp_have, tmp_q))
      if len(have) > 0:
        tmp_q = q.copy()
        tmp_have = sorted(have.copy())
        v = tmp_have.pop(0)
        tmp_q.appendleft(v)
        a.append(dfs(N, K, k+1, tmp_have, tmp_q))
        tmp_q = q.copy()
        tmp_have = sorted(have.copy())
        v = tmp_have.pop(0)
        tmp_q.append(v)
        a.append(dfs(N, K, k+1, tmp_have, tmp_q))
      dp[(k, tuple(q))] = max(a)
    return dp[(k, tuple(q))]


N, K = map(int, input().split())
V = deque(list(map(int, input().split())))
print(dfs(N, K, 0, [], V))

Submission status: Runtime Error

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

if K >= N:
    print(sum((v for v in dq if dq >= 1)))
else:
    dq = deque(dq, maxlen=len(dq))
    print(100)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
v = list(map(int, input().split()))
maxvalue = 0
for l in range(k+1):
    r = k - l
    leftmax = 0 
    for take in range(l+1):
        ava = sorted(v[:take])
        value = sum(ava)
        for back in range(min(take, l - take)):
            if ava[back] >= 0:
                break
            else:
                value -= ava[back]
        leftmax = max(leftmax, value)
    rightmax = 0
    for take in range(r+1):
        ava = sorted(v[n-take:])
        value = sum(ava)
        for back in range(min(take, r - take)):
            if ava[back] >= 0:
                break
            else:
                value -= ava[back]
        rightmax = max(rightmax, value)
    maxvalue = max(maxvalue, leftmax + rightmax)
print(maxvalue)

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:
    motimono=v
    k-=n
    for i in range(k):
        heappop(motimono)
        ans.append(sum(motimono))
    print(max(ans))
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)
#                print(motimono)
                ans.append(sum(motimono))
    print(max(ans))

Submission status: Runtime Error

Solution code:
def do_action(q, temoto, value, k_remain):
    if k_remain == 0:
        return value
    a = b = c = d = e = -100000000

    # どっちを掘るか決める
    l_sum = r_sum = 0
    for i in range(k_remain):
        if i > len(q):
            break
        if q[i] > 0:
            l_sum += q[i]
        if q[- (i + 1)] > 0:
            r_sum += q[- (i + 1)]

    # a
    if l_sum >= r_sum:
        if len(q) != 0:
            val = q[0]
            a = do_action(q[1:], temoto + [val], value + val, k_remain - 1)
    # b
    if r_sum <= l_sum:
        if len(q) != 0:
            val = q[-1]
            b = do_action(q[:-1], temoto + [val], value + val, k_remain - 1)

    temoto.sort()
    # 戻す可能性があるのは負のがあるときのみ
    if len(temoto) > 0 and temoto[0] < 0:
        # c
        if len(temoto) != 0:
            temoto.sort()
            val = temoto[0]
            c = do_action([val] + q , temoto[1:], value - val, k_remain - 1)
        # d
        if len(temoto) != 0:
            temoto.sort()
            val = temoto[0]
            d = do_action(q + [val], temoto[1:], value - val, k_remain - 1)
    # e
    e = do_action(q , temoto, value, k_remain - 1)

    return max(a,b,c,d,e)
n, k = map(int, input().split())
dat_v = map(int, input().split())
dat_v = list(dat_v)
val = do_action(dat_v, [], 0, k)
print(val)

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
v=list(map(int,input().split()))
V=sorted(v,reverse=True)
cnt=0
for i in range(n):
  if V[i]>0:
    cnt+=1
  else:
    break
print(sum(V[:(min(cnt,k//2))])

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
V = list(map(int, input().split()))
l = [0]
for i in range(1, K + 1): #左に何回操作するか
    #print("i=",i)
    b = 0
    for j in range(i // 2 + 1): #いくつ捨てるか
        #print("j=",j)
        a = []
        for m in range(min(i - j, N)):
            a.append(V[m])
        a.sort()
        s = 0
        for m in range(i - j):
            if m >= j or a[m] >= 0:
                s += a[m]
        b = max(b, s)
    #print("b=",b)
    l.append(max(b, l[-1]))
#print(l)
r = [0]
for i in range(1, K + 1): #右に何回操作するか
    #print("i=",i)
    b = 0
    for j in range(i // 2 + 1): #いくつ捨てるか
        #print("j=",j)
        a = []
        for m in range(max(0, N - i + j), N):
            a.append(V[m])
        #print("s=",s)
        a.sort()
        s = 0
        for m in range(i - j):
            if m >= j or a[m] >= 0:
                s += a[m]
        b = max(b, s)
    #print("b=",b)
    r.append(max(b, r[-1]))
#print(r)
ans = 0
for i in range(K + 1):
    ans = max(ans, l[i] + r[K - i])
print(ans)

Submission status: Runtime Error

Solution code:
N,K= map(int,input().split())
D = list(map(int,input().split()))
from itertools import accumulate
acc = [0]+list(accumulate(D, lambda x,y:x+y))
mx = 0
for k in range(K+1): # k 回とる
    rest = K-k # rest回まで捨てることができる
    for l in range(1, k+1): # 左から何個とるか
        r = k-l
        left = acc[l]
        right = acc[N]-acc[N-r]
        tmp = left+right
        tmpl = D[:l]
        tmpr = D[N-r:N]
        minus = sorted([i for i in tmpl+tmpr if i < 0])
        tmp -= sum(minus[:rest])
        mx = max(mx, tmp)
print(mx)

Submission status: Runtime Error

Solution code:
import copy

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

mx = 0
for num_out in range(k+1):
	if num_out > n:
		num_out = n
		num_ret = min(k-n, n)
		out = copy.deepcopy(v).sort()
		ret_value = 0
		for ret_v in out[:num_ret]:
			if ret_v < 0:
				ret_value += ret_v
			else:
				break
		val = sum(out) - ret_value
		if val > mx:
			mx = val
		continue
	
	num_ret = k-num_out
	for num_out_l in range(num_out+1):
		num_out_r = num_out - num_out_l
		out = v[:num_out_l] + v[n-num_out_r:]
		out.sort()
		ret_value = 0
		for ret_v in out[:num_ret]:
			if ret_v < 0:
				ret_value += ret_v
			else:
				break
		val = sum(out) - ret_value
		if val > mx:
			mx = val
			# mx_out = out

print(mx)
# print(mx_out)

Submission status: Runtime Error

Solution code:
from collections import deque

def read_input():
    n, k = map(int, input().split())
    vlist = list(map(int, input().split()))
    vq = deque()

    for v in vlist:
        vq.append(v)

    return n, k, vq


def submit():
    n, k, vq = read_input()

    maxvalue = 0
    for kk in range(1, k):
        # 左からi回宝石を取得する
        # 右からkk-i回宝石を取得する
        for i in range(kk + 1):
            getv = []
            minusv = []
            vq_temp = vq.copy()
            for j in range(i):
                if len(vq_temp) > 0:
                    vl = vq_temp.popleft()
                    if vl < 0:
                        minusv.append(vl)
                    else:
                        getv.append(vl)
                else:
                    break

            for j in range(kk - i):
                if len(vq_temp) > 0:
                    vr = vq_temp.pop()
                    if vr < 0:
                        minusv.append(vr)
                    else:
                        getv.append(vr)
                else:
                    break


            # k - kk回はminusを削除できる
            minusv.sort()
            for m in range(k - kk):
                if minusv:
                    minusv.remove(minusv[0])
                else:
                    break

            currvalue = sum(getv) + sum(minusv)

            if currvalue > maxvalue:
                maxvalue = currvalue

    print(maxvalue)







if __name__ == '__main__':
    submit()

Submission status: Runtime Error

Solution code:
n, K = map(int, input().split())
l = list(map(int, input().split()))
res = curr = 0
neg = []
for i in range(K + 1):
    
    ans = curr
    neg0 = neg[::]
    for j in range(K - i):
        if i + j > n: break
        neg0.sort()
        s = 0
        for k in range(min(len(neg0), K - i - j)):
            s -= neg0[k]
            res = max(res, ans + s)
        
        ans += l[n - 1 - j]
        if l[n - 1 - j] < 0: neg0.append(l[n - 1 - j])

    curr += l[i]
    if l[i] < 0: neg.append(l[i])
print(res)

Submission status: Runtime Error

Solution code:
import copy

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

mx = 0
for num_out in range(k+1):
	if num_out > n:
		num_out = n
		num_ret = min(k-n, n)
		out = copy.deepcopy(v).sort()
		for ret_v in out[:num_ret]:
			if ret_v < 0:
				ret_value += ret_v
			else:
				break
		val = sum(out) - ret_value
		if val > mx:
			mx = val
		continue
	
	num_ret = k-num_out
	for num_out_l in range(num_out+1):
		num_out_r = num_out - num_out_l
		out = v[:num_out_l] + v[n-num_out_r:]
		out.sort()
		ret_value = 0
		for ret_v in out[:num_ret]:
			if ret_v < 0:
				ret_value += ret_v
			else:
				break
		val = sum(out) - ret_value
		if val > mx:
			mx = val
			# mx_out = out

print(mx)
# print(mx_out)

Submission status: Runtime Error

Solution code:
# abcde	s=input()	s='abcde'
# abcde	s=list(input())	s=['a', 'b', 'c', 'd', 'e']
# 5(1つだけ)	a=int(input())	a=5
# 1 2	| x,y = s_inpl()   |	x=1,y=2
# 1 2 3 4 5 ... n 　	li = input().split()	li=['1','2','3',...,'n']
# 1 2 3 4 5 ... n 　	li = inpl()	li=[1,2,3,4,5,...,n]
# FFFTFTTFF 　	li = input().split('T')	li=['FFF', 'F', '', 'FF']

# INPUT
# 3
# hoge
# foo
# bar
# ANSWER
# n=int(input())
# string_list=[input() for i in range(n)]

import math
import copy
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
from bisect import bisect_left, bisect_right
# import numpy as np

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]

def i_inpl(): return int(input())
def s_inpl(): return map(int,input().split())
def l_inpl(): return list(map(int, input().split()))
INF = float("inf")

############
############
############


N, K = s_inpl()
V = l_inpl()

def dfs(i, cnt, sum_val, lim, v):
    if cnt==lim:
        return sum_val
    elif cnt > lim:
        return -INF
    
    return max(dfs(i+1, cnt+1, sum_val+v[i], lim, v), dfs(i+1, cnt+2, sum_val, lim, v), sum_val)

ans = -INF
for i in range(K+1):
    lk, rk = i, K-i
    ans = max(ans, dfs(0, 0, 0, lk, V)+dfs(0, 0, 0, rk, V[::-1]))

print(ans)