Problem:


Score : 400 points

Problem Statement

Your friend gave you a dequeue D as a birthday present.

D is a horizontal cylinder that contains a row of N jewels.

The values of the jewels are V_1, V_2, ..., V_N from left to right. There may be jewels with negative values.

In the beginning, you have no jewel in your hands.

You can perform at most K operations on D, chosen from the following, at most K times (possibly zero):

Operation A: Take out the leftmost jewel contained in D and have it in your hand. You cannot do this operation when D is empty.

Operation B: Take out the rightmost jewel contained in D and have it in your hand. You cannot do this operation when D is empty.

Operation C: Choose a jewel in your hands and insert it to the left end of D. You cannot do this operation when you have no jewel in your hand.

Operation D: Choose a jewel in your hands and insert it to the right end of D. You cannot do this operation when you have no jewel in your hand.

Find the maximum possible sum of the values of jewels in your hands after the operations.

Constraints

All values in input are integers.

1 \leq N \leq 50

1 \leq K \leq 100

-10^7 \leq V_i \leq 10^7

Input

Input is given from Standard Input in the following format:

N K
V_1 V_2 ... V_N

Output

Print the maximum possible sum of the values of jewels in your hands after the operations.

Sample Input 1

6 4
-10 8 2 1 2 6

Sample Output 1

14

After the following sequence of operations, you have two jewels of values 8 and 6 in your hands for a total of 14, which is the maximum result.

Do operation A. You take out the jewel of value -10 from the left end of D.

Do operation B. You take out the jewel of value 6 from the right end of D.

Do operation A. You take out the jewel of value 8 from the left end of D.

Do operation D. You insert the jewel of value -10 to the right end of D.

Sample Input 2

6 4
-6 -100 50 -2 -5 -3

Sample Output 2

44

Sample Input 3

6 3
-6 -100 50 -2 -5 -3

Sample Output 3

0

It is optimal to do no operation.



Sample input:
6 4
-10 8 2 1 2 6


Sample output:
14

Submission status: Accepted

Solution code:
import copy

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

INF = 10 ** 8


# mode 0: can pop left, pop right, drop
#      1: can pop right, drop
#      2: can drop
#      3: can not do anything
def rec(rest_ope, now_d, now_hand, mode):

    if rest_ope == 0:
        return sum(now_hand)

    max_price = -INF

    if len(now_d) > 0:
        if mode == 0:
            left_d = copy.copy(now_d)
            left_hand = copy.copy(now_hand)
            left_hand.append(left_d.pop(0))

            max_price = max(max_price, rec(rest_ope - 1, left_d, left_hand, 0))

        if mode <= 1:
            right_d = copy.copy(now_d)
            right_hand = copy.copy(now_hand)
            right_hand.append(right_d.pop(-1))

            max_price = max(max_price, rec(rest_ope - 1, right_d, right_hand, 1))

    if len(now_hand) > 0:
        if mode <= 2:
            drop_hand = copy.copy(now_hand)
            drop_hand.pop(drop_hand.index(min(drop_hand)))  # 最小値を削除

            max_price = max(max_price, rec(rest_ope - 1, now_d, drop_hand, 2))

    # do nothing
    max_price = max(max_price, rec(rest_ope - 1, now_d, now_hand, 3))

    return max_price


print(rec(K, V, [], 0))

Submission status: Accepted

Solution code:
from collections import deque
from copy import deepcopy
import heapq

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

ans = 0
for i in range(k+1):
    if True:
        for nl in range(i+1):
            nr = min(k - nl, n-nl)
            ansl, ansr = 0, 0
            for n_trash in range(nl):
                ansll, ansrr = 0, 0
                hands = sorted(v[:nl-n_trash])
                for vv in hands:
                    if vv < 0 and n_trash > 0:
                        n_trash -= 1
                    else:
                        ansll += vv
                ansl = max(ansl, ansll)

            for n_trash in range(nr):
                ansrr = 0
                hands = sorted(v[-(nr-n_trash):])
                # print(hands, nr, n_trash)
                for vv in hands:
                    if vv < 0 and n_trash > 0:
                        n_trash -= 1
                    else:
                        ansrr += vv
                ansr = max(ansr, ansrr)
            # print(ansl, ansr)
            ans = max(ans, ansl + ansr)
    else:
        n_trash = n-i
        ans_cur = 0
        for vv in v_sorted:
            if vv < 0 and n_trash > 0:
                n_trash -= 1
            else:
                ans_cur += vv
        ans = max(ans, ans_cur)

print(ans)

Submission status: Accepted

Solution code:
import heapq
import copy

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

ans = 0
for kr in range(min(N, K) + 1):
    for kl in range(min(N - kr, K - kr) + 1):
        kp = min(K - kr - kl, kr + kl)
        # print(kr, kl, kp)
        if kr != 0:
            vs = Vs[-kr:] + Vs[:kl]
        else:
            vs = Vs[:kl]
        
        length = len(vs)
        if length == 0:
            continue
        vs = copy.deepcopy(vs)
        heapq.heapify(vs)
        # less than the number of outputs
        for i in range(min(kp, length)):
            if vs[0] < 0:
                heapq.heappop(vs)
            else:
                break
        value = sum(vs)
        ans = max(value, ans)

print(ans)

Submission status: Accepted

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

ans = 0
for a in range(K + 1):  # a回まで行う
    for i in range(a + 1):
        get = a - i
        rel = i
        if rel >= get:
            continue
        for j in range(get + 1):  # 右からj個とる
            point = 0
            right = j
            left = get - right
            if right + left > N:
                continue
            l = V[:left]
            r = V[N - right:]
            al = r + l
            al.sort()
            point = sum(al[rel:])
            ans = max(ans, point)
print(ans)

Submission status: Accepted

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(min(K+1, N+1)): # k 回とる
    rest = K-k # rest回まで捨てることができる
    for l in range(min(k+1, N+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)
if K > N:
    tmp = acc[-1]
    rest = K - N
    minus = sorted([i for i in D if i < 0])
    tmp -= sum(minus[:rest])
    mx = max(mx, tmp)
print(mx)

Submission status: Accepted

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


def calc_score(hands, push):
  hands.sort()

  for i, v in enumerate(hands):
    if v > 0 or i >= push:
      return sum(hands[i:])

  return 0


def main():
  _, k = map(int, input().split())
  values = list(map(int, input().split()))
  score = 0

  for n in range(1, k + 1):
    if n < len(values):
      for i in range(n):
        score = max(calc_score(values[:i] + values[-n + i:], k - n), score)

      score = max(calc_score(values[:n], k - n), score)

    else:
      score = max(calc_score(values[:], k - n), score)

  print(score)


if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
def sol(_inp=input):
    n,k=map(int,_inp().split())
    ds=list(map(int,_inp().split()))
    res=0
    for l in range(k+1):
        for r in range(k-l+1):
            if l+r<n:
                cur=sum(ds[:l])+sum(ds[n-r:])
                negs=[i for i in ds[:l]+ds[n-r:] if i<0]
            else:
                cur=sum(ds)
                negs=[i for i in ds if i<0]
            rem=min(max(k-l-r,0),len(negs))
            cur-=sum(sorted(negs)[:rem])
            res=max(res,cur)
    return str(res)
print(sol())

Submission status: Accepted

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

from heapq import heappush, heappop
for i in range(1, k+1):
  for j in range(1, i+1):
    for k in range(0, j+1):
      menus = []
      l = min(n, k)
      r = min(n-l, j-l)
      for ll in range(l):
        if v[ll]<0:
          heappush(menus, v[ll])
      for rr in range(r):
        if v[n-rr-1]<0:
          heappush(menus, v[n-rr-1])
      cur = ls[l] + rs[r]
      rm = i-l-r
      while rm>0 and len(menus)>=rm:
        rm -= 1
        t = heappop(menus)
        cur -= t
      ans = max(ans, cur)
print(ans)

Submission status: Accepted

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

ans=0
mai=len([t for t in v if t<0])           
v2=sorted(v)
if k>=n:
    if k-n>=mai:
        ans=max(ans, sum(v2[mai:]))
    else:
        ans=max(ans, sum(v2[k-n:]))
    
for i in range(min(n+1,k+1)):
    for j in range(min(k-i+1,n-i+1)):
        if j==0:
            g=v[:i]
        else:
            g=v[:i]+v[-j:]
        g.sort()
        mai=len([t for t in g if t<0])
        if k-i-j>=mai:
            ans=max(ans, sum(g[mai:]))
            #print(g,sum(g[mai:]))
        else:
            ans=max(ans, sum(g[k-i-j:]))
            #print(g,sum(g[k-i-j:]))
print(ans)

Submission status: Accepted

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

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

dp = [[[-10000000000] * (K+1) for _ in range(N+1)] for _ in range(N+1)]
dp[0][N][0] = 0
for i in range(N) :
    for j in range(N, i-1, -1) :
        for k in range(1, K+1) :
            dp[i][j][k] = max(dp[i][j][k], dp[i][j][k-1])
            if 0 <= i-1 < N:
                dp[i][j][k] = max(dp[i][j][k], dp[i-1][j][k-1] + V[i-1])
            if 0 <= j+1 <= N :
                dp[i][j][k] = max(dp[i][j][k], dp[i][j+1][k-1] + V[j])
            if k >= 2 :
                if 0 <= i-1 < N :
                    dp[i][j][k] = max(dp[i][j][k], dp[i-1][j][k-2])
                if 0 <= j+1 <= N :
                    dp[i][j][k] = max(dp[i][j][k], dp[i][j+1][k-2])

ans = 0
for i in range(N+1) :
    for j in range(N+1) :
        for k in range(K+1) :
            ans = max(ans, dp[i][j][k])
            #print(i, j, k, dp[i][j][k])

print(ans)

Submission status: Accepted

Solution code:
#coding:utf-8
N,K = map(int,input().split())
oldK = K
K = min(N,K)
V = list(map(int,input().split()))
mx = 0
for k in range(1,K+1):
    for i in range(k+1):
        late = V[-(k-i):]
        if len(late)==N:
            late = []
        #print (k,V[:i],late)
        a = V[:i]+late
        a += [0]
        #print (a)
        a.sort()
        idx = min(a.index(0),oldK-k)
        sm = sum(a[idx:])
        #print (a,sm)
        mx = max(sm,mx)
        #print (mx)
print (mx)

Submission status: Accepted

Solution code:

N,K =map(int,input().split())
V =[int(i)for i in input().split()]
V.append("dami-")
ans = 0
for i in range(min(N,K)):
    i += 1
    for j in range(i+1):
        get = V[0:j] +V[j-i-1:-1]
        get.sort()
        for n in range(min(K-i,len(get))):
            if get[n]<0:
                get[n]=0
            else:
                break
        su =sum(get)
        if ans < su:
            ans = su
print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
V = list(map(int, input().split()))
ans = 0
KN = min(K,N)
for i in range(1,KN+1):
    for j in range(i+1):
        rec = V[:i-j]+V[N-j:]
        rec.sort(reverse=True)
        away = max(min(i, K-i),0)
        for l in range(away+1):
            recsum = sum(rec[:i-l])
            if recsum > ans:
                ans=recsum
print(ans)

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    import sys
    input = sys.stdin.readline

    import copy


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

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

    while k >= 1:
        for l in range((k+1)//2, k+1):
            for i in range(l+1):
                if i <= n-l+i:
                    get_list = vv[:i]+ vv[n-(l-i):]
                    get_list.sort(reverse=True)
                    ans = max([ans, sum(get_list[:2*l-k])])
        k -= 1

    print(ans)

Submission status: Accepted

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

ans = 0
for i in range(1,k+1):
    if i > n:
        break
    for j in range(i):
        tmpv = v[-j:]+v
        newv = tmpv[:i]
        newv.sort()
        rmsum = 0
        for t in range(min(k-i,len(newv))):
            if newv[t] < 0:
                rmsum += newv[t]
        ans = max(sum(newv) - rmsum,ans)
print(ans)

Submission status: Accepted

Solution code:
from copy import deepcopy

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

V = [0] + V + [0]

bag = []
value = []
for i in range(min(N,K)+1): ## 左からi個取り出す
  bag.append(V[i])
  bag_copy = deepcopy(bag)
  for j in range(min(N,K)-i+1): ## 右からj個取り出す
    bag_copy.append(V[N-j+1])
    bag_value = sum(bag_copy)
    bag_sorted = sorted(bag_copy)
    for k in range(K-i-j):
      if bag_sorted[k] < 0:
        bag_value -= bag_sorted[k]
      else:
        break
    value.append(bag_value)
    #print(i, j, bag_copy, bag_value)
    
ans = max(value)
print(ans)

Submission status: Accepted

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

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

av = tuple(chain((0,),accumulate(V)))


def left():
    for i in range(N+1):
        tmp = sorted(min(0, v) for v in V[:i])
        yield tuple(chain((0,), accumulate(tmp)))

left_cost = tuple(left())


def right():
    for i in reversed(range(N+1)):
        tmp = sorted(min(0, v) for v in V[i:])
        yield tuple(chain((0,), accumulate(tmp)))

right_cost = tuple(right())

def helper():
    for i in range(N+1):
        for j in range(N-i+1):
            d = K - i - j
            if d < 0:
                continue
            rev = av[i]+(av[N]-av[N-j])
            l,r = left_cost[i], right_cost[j]
            for k in range(d+1):
                yield rev - l[min(i,k)] - r[min(j,d-k)]
print(max(helper()))

Submission status: Accepted

Solution code:
def solve(N, K, V):
    # 右からi個、左からj個取り出す時の価値の最大値
    max_points = 0
    for i in range(N + 1):
        for j in range(min(N + 1, K - i + 1)):
            j = min(N - i, j)
            hand = list()
            hand.extend(V[N - i:])
            hand.extend(V[:j])
            points = sum(hand)
            minus = list(filter(lambda x: x < 0, hand))
            minus = sorted(minus)
            action = K - i - j
            points += abs(sum(minus) - sum(minus[action:]))
            max_points = max(max_points, points)
    return max_points


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

Submission status: Accepted

Solution code:
import numpy as np

INF = 10000000 * 50 + 1

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

ans = -INF
for l in range(K + 1):
	for dr in range(K + 1 - l):
		r = N - dr
		if r < l:
			break
		ms = np.sort(np.concatenate((V[:l], V[r:])))
		score = np.sum(ms)
		score -= np.sum(ms[ms < 0][:K-(l+dr)])
		ans = max(ans, score)

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3


def point(vs, skip_n):
    vs = sorted(vs)
    total = 0
    for v in vs:
        if v < 0 and skip_n > 0:
            skip_n -= 1
        else:
            total += v
    return total


def solv(n, k, vs):
    rvs = list(reversed(vs))
    max_take = min(k, n)
    max_val = 0
    for take in range(1, max_take+1):
        for l in range(take+1):
            r = take - l
            vs1 = vs[:l] + rvs[:r]
            max_val = max(point(vs1, k-take), max_val)
    return max_val


if __name__ == '__main__':

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

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

    ans = solv(n, k, vs)
    print(ans)

Submission status: Accepted

Solution code:
l = raw_input().split()
N = int(l[0])
K = int(l[1])

l = raw_input().split()
V = [int(x) for x in l]
# print(N, K, V)

def take_left(v, n):
    if n == 0:
        return []
    return v[:n]

def take_right(v, n):
    if n == 0:
        return []
    return v[-n:]

max_v = 0

for num_ret in range(K):
    for num_take_left in range(K - num_ret + 1):
        V_tmp = [x for x in V]
        # print('V_tmp first', V_tmp)
        num_take_right = K - num_ret - num_take_left
        # print(num_ret, num_take_left, num_take_right)
        l = take_left(V_tmp, num_take_left)
        del V_tmp[:num_take_left]
        r = take_right(V_tmp, num_take_right)
        del V_tmp[num_take_right:]
        taken = l + r
        taken.sort()
        # print('l,r,taken,tmp', l, r, taken, V_tmp)
        for i in range(num_ret):
            if len(taken) == 0:
                break
            if taken[0] < 0:
                del taken[0]
            else:
                break
        v = sum(taken)
        # print('v={}'.format(v))
        if max_v < v:
            max_v = v

print(max_v)

Submission status: Accepted

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



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

def get_sum(a,b):
  # a個取って、b個捨てる
  ret = 0
  for i in range(a+1):
    v = sorted(Vn[:i]+Vn[N-a+i:])
    for j in range(min(a,b)):
      v[j] = max(v[j],0)
    ret = max(ret,sum(v))
  return ret


def main():
  ans = 0
  for n in range(min(N,K)+1):
    ans = max(ans, get_sum(n, max(K-n,0)))
  return ans


if __name__ == "__main__":
  print(main())

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from heapq import heappop

n, k = li()
v = list(li())

ans = 0

for x in range(-(-k//2)):
    if 2*x > k:
        continue

    get = k - x
    if get >= n:
        cnt = 0
        heap = sorted(v)

        while heap[0] < 0 and cnt < x:
            _ = heappop(heap)
            cnt += 1

        ans = max(ans, sum(heap))

    else:
        for i in range(get+1):
            cnt = 0
            heap = sorted(v[:i] + v[n-(get-i):])
            while heap[0] < 0 and cnt < x:
                _ = heappop(heap)
                cnt += 1

            ans = max(ans, sum(heap))

print(ans)

Submission status: Accepted

Solution code:
import bisect

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

ans = 0
for i in range(0, k + 1):
    for j in range(0, min(k, n) - i + 1):
        if j:
            toridashita = v[:i] + v[-j:]
        else:
            toridashita = v[:i]
        toridashita.sort()
        tsumeru = min(k - i - j, bisect.bisect_left(toridashita, 0))
        ans = max(ans, sum(toridashita[tsumeru:]))

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

    return n, k, vlist


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

    maxvalue = 0
    for kk in range(1, k + 1):
        # 左からi回宝石を取得する
        # 右からkk-i回宝石を取得する
        for i in range(kk + 1):
            getv = []
            minusv = []
            vq_temp = deque()

            for v in vlist:
                vq_temp.append(v)

            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: Accepted

Solution code:
from itertools import*
import math
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = float("inf")
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)

n,k = map(int,input().split())
D = deque()
V = list(map(int,input().split()))
for i in range(n):
    D.append(V[i])
ans = 0
if 2*n <= k:
    for j in range(n):
        if V[j]>0:
            ans += V[j]
    print(ans)
    exit()
else:
    for i in range(k+1):
        for j in range(k+1):
                if i + j> k:
                    continue
                else:
                    cur = 0
                    V1 =[]
                    if i+j >=n:
                        cur = sum(V)
                        for v in V:
                            if v < 0:
                                V1.append(v)
                    else:
                        cur += sum(V[:i])
                        cur += sum(V[n-j:])
                        for s in range(i):
                            if V[s]<0:
                                V1.append(V[s])
                        for t in range(j):
                            if V[n-1-t]<0:
                                V1.append(V[n-1-t])
                    V1.sort(reverse=True)
                    for u in range(k-i-j):
                        if len(V1)>0:
                            cur -= V1.pop()
                        else:
                            break
                    ans = max(cur,ans)
print(ans)

Submission status: Accepted

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.copy(v)
		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
		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: Accepted

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

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

max_score = 0
searched_list = []
for k in range(K+1):
    #print(k)
    for l in range(k+1):
        for r in range(k+1-l):
            if l + r > N:
                break
            taken = V[:l]
            taken.extend(V[N-r:])
            sorted_taken = sorted(taken)
            #print(sorted_taken)
            neg_count = len([n for n in sorted_taken if n < 0])
            remove_count = min(k-l-r, neg_count)
            score = sum(sorted_taken[remove_count:])
            if max_score < score:
                max_score = score
                #print(sorted_taken)
                #print(remove_count)
print(max_score)

Submission status: Accepted

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

for i in range(N+1):
    for j in range(N+1):
        if i+j <= N and i+j <= K:
            nokori = K - i - j
            now = []
            now.extend(V[:i])
            if j != 0:
                now.extend(V[-j:])
            now.sort()
            nowmax = sum(now)
            #print(nokori)
            #print(now)
            for k in range(min(nokori, len(now))):
                nnn = now.pop(0)
                if nnn < 0:
                    nowmax -= nnn
                else:
                    break
            dp[i][j] = nowmax
#print(dp)
ans = -10 ** 10
for i in range(N+1):
    ans = max(ans, max(dp[i]))
print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
V = [int(v) for v in input().split()]

nk = min(N, K)  # NとKのmin（Vから取れる宝石の上限数）
ans = 0

for i in range(1, nk + 1):   # i:取る宝石の数
    for j in range(i + 1):   # j:左端から取る宝石の数
        tmp = V[:j] + V[N-i+j:] # 左からj個、右からi-j個取る
        tmp.sort()
        ngcnt = 0   # マイナスの数
        vsum = 0
        for t in tmp:
            if t < 0 and ngcnt < K-i:
                ngcnt += 1
                continue
            else:
                vsum += t
        ans = max(vsum, ans)

print(ans)

Submission status: Accepted

Solution code:
import heapq

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

pq = []
max_score = 0
# 左からi個
for i in range(min(N,K)+1):
    # 右からj個
    for j in range(min(N-i, K-i)+1):
        tmp_score = 0
        pq = []
        for lef in range(i):
            if inl[lef] < 0:
                heapq.heappush(pq, inl[lef])
            tmp_score += inl[lef]
        for rg in range(j):
            if inl[N-1-rg] < 0:
                heapq.heappush(pq, inl[N-1-rg])
            tmp_score += inl[N-1-rg]
        for _ in range(K-i-j):
            if len(pq):
                minus = heapq.heappop(pq)
                tmp_score -= minus
        # print(pq)
        # print("i:{} j:{} nokori:{} tmp_score:{}".format(i,j,K-i-j, tmp_score))
        max_score = max(tmp_score, max_score)

print(max_score)

Submission status: Accepted

Solution code:
list=input().split(" ")
n=int(list[0])
k=int(list[1])

list=input().split(" ")
for l in range(len(list)):
    list[l]=int(list[l])

#print(list)
maxpoint=0

for i in range(k+1):
    for j in range(i+1):
        if i>len(list):
            juery=list
        elif j==0:
            if j-i==0:
                juery=[]
            else:
                juery=list[j-i:]
        else:
            if j-i==0:
                juery=list[:j]
            else:
                juery=list[:j]+list[j-i:]
        juery=sorted(juery)
        #print(juery, sum(juery), k-len(juery))
        point=0
        magic=min(k-len(juery), len(juery))
        for x in range(magic):
            if juery[x]<0:
                point-=juery[x]
        point+=sum(juery)
        #print(juery, point)
        if point>maxpoint:
            maxpoint=point

print(maxpoint)

Submission status: Accepted

Solution code:
import bisect


def f(a: list, n: int) -> list:
    i = bisect.bisect(a, 0)
    return a[min(i, n):]


assert f([1, 2, 3], 1) == [1, 2, 3]
assert f([-1, 2, 3], 1) == [2, 3]
assert f([-2, -1, 3], 1) == [-1, 3]
assert f([-2, 0, 3], 1) == [0, 3]
assert f([-2, -1, 3], 3) == [3]
assert f([-2, -1, 3], 0) == [-2, -1, 3]
assert f([], 0) == []


def main():
    # pass
    N, K = map(int, input().split())
    V = [int(x) for x in input().split()]
    Vr = list(reversed(V))

    ans = -float("inf")
    for l in range(0, max(N, K)+1):
        for r in range(0, max(N, K)+1):
            n = max(0, K - r - l)  # 戻すことができる最大の回数

            if N < l + r or K < l + r:
                continue

            # l, r個ずつ取り出す
            a1 = V[:l]
            a2 = Vr[:r]
            a = a1 + a2
            a = sorted(a)

            score = sum(f(a, n))
            ans = max(ans, score)

            # print(f"{l} {r} {n} {a1}+{a2}={a}")
            # # print(i, a[:i], b)
            # print(f"score={score}")

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
ls,lm,rs,rm=[0],[[0 for i in range(k+1)]for i in range(n+1)],[0],[[0 for i in range(k+1)]for i in range(n+1)]
v=list(map(int,input().split()))
ld=[]
rd=[]
for i in range(n):
    ls.append(ls[-1]+v[i])
    if v[i]<0:
        ld.append(v[i])
        ld=sorted(ld)
    for j in range(1,k+1):
        if j-1<len(ld):
            lm[i+1][j]=lm[i+1][j-1]+ld[j-1]
        else:
            lm[i+1][j]=lm[i+1][j-1]
    ii=n-i-1
    rs.append(rs[-1]+v[ii])
    if v[ii]<0:
        rd.append(v[ii])
        rd=sorted(rd)
    for j in range(1,k+1):
        if j-1<len(rd):
            rm[i+1][j]=rm[i+1][j-1]+rd[j-1]
        else:
            rm[i+1][j]=rm[i+1][j-1]


mx=-999999999
for w in range(k+1):
    for x in range(w+1):
        for y in range(x,w+1):
            for z in range(y,w+1):
                    a,b,c,d=x,y-x,z-y,w-z
                    if a+c<=n and len(ls)>a>=b and len(rs)>c>=d and ls[a]-lm[a][b]+rs[c]-rm[c][d]>mx:
                        # print(a,b,c,d,ls[a],lm[a][b],rs[c],rm[c][d],ls[a]-lm[a][b]+rs[c]-rm[c][d])
                        mx=ls[a]-lm[a][b]+rs[c]-rm[c][d]
print(mx)

Submission status: Accepted

Solution code:
from functools import lru_cache
import numpy as np

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

retval=0
for left in range(max(N+1,K+1)):
    for right in range(min(N-left+1,K-left+1)):
        modoseru=K-(left+right)
        temoto=np.asarray(sorted(V[:left:]+V[N-right::]))
        modosu=min(np.sum(temoto<0),modoseru)
        retval=max(sum(temoto[modosu::]),retval)

print(retval)

Submission status: Accepted

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

max_val = 0
for disc in range(max(k - len(vals), 0), k):
    pick = k - disc
    for lp in range(pick+1):
        if pick > lp:
            jewel = vals[:lp] + vals[-(pick-lp):]
        else:
            jewel = vals[:lp]
        neg = sum([j < 0 for j in jewel])
        if neg <= disc:
            reward = sum([j for j in jewel if j > 0])
        else:
            reward = sum(sorted(jewel)[disc:])
        if reward > max_val:
            max_val = reward
print(max_val)

Submission status: Accepted

Solution code:
import sys

fin = sys.stdin.readline

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

# k >= 2*n -> sum(max(0, v))
if all([v_ <= 0 for v_ in v]):
    print(0)
else:
    scores = [0]
    for i in range(1, min(k, n) + 1):  # kことり出す
        for j in range(i + 1):
            poped = v[:j] + v[n - i + j:]
            poped = sorted(poped)
            if k ==i:
                scores.append(sum(poped))
            elif k >= i*2:
                scores.append(sum([max(0, p) for p in poped]))
            elif poped[k - i - 1] < 0:
                scores.append(sum(poped[k - i:]))
            else:
                scores.append(sum([max(0, p) for p in poped]))


    print(max(scores))