Problem:
 Score : 400 points    Problem Statement There are N squares aligned in a row.
The i -th square from the left contains an integer a_i .  Initially, all the squares are white.
Snuke will perform the following operation some number of times:   Select K consecutive squares. Then, paint all of them white, or paint all of them black. Here, the colors of the squares are overwritten.   After Snuke finishes performing the operation, the score will be calculated as the sum of the integers contained in the black squares.
Find the maximum possible score.      Constraints  1≤N≤10^5  1≤K≤N  a_i is an integer.  |a_i|≤10^9         Input The input is given from Standard Input in the following format:  N  K  a_1  a_2  ...  a_N       Output Print the maximum possible score.        Sample Input 1 5 3
-10 10 -10 10 -10      Sample Output 1 10  Paint the following squares black: the second, third and fourth squares from the left.       Sample Input 2 4 2
10 -10 -10 10      Sample Output 2 20  One possible way to obtain the maximum score is as follows:   Paint the following squares black: the first and second squares from the left.  Paint the following squares black: the third and fourth squares from the left.  Paint the following squares white: the second and third squares from the left.        Sample Input 3 1 1
-10      Sample Output 3 0       Sample Input 4 10 5
5 -4 -5 -8 -4 7 2 -4 0 7      Sample Output 4 17

Solution (Python):
N, K = list(map(int, input().split()))
a = list(map(int, input().split()))

p = [0] * N
q = [0] * N

p[0] = a[0] if a[0] > 0 else 0
q[0] = a[0]

for i in range(1, N):
  p[i] = p[i - 1] + (a[i] if a[i] > 0 else 0)
  q[i] = q[i - 1] + a[i]

ans = 0
for i in range(N - K + 1):
  t = i + K - 1
  x = p[-1] - p[t] + (p[i - 1] if i != 0 else 0)
  ans = max(ans, x)
  x += q[t] - (q[i - 1] if i != 0 else 0)
  ans = max(ans, x)

print(ans)

Solution (Python):
import numpy as np
n,k=map(int,input().split())
*a,=map(int, input().split())
a+=[0]
a=np.array(a)

ac=np.ndarray.cumsum(np.maximum(a,0))
acr=np.ndarray.cumsum(np.maximum(a[::-1],0))
amid=np.sum(a[:k])
ans=max(amid,0)+acr[n-k]
for i in range(n-k):
    
    amid+=a[i+k]
    amid-=a[i]
    ans=max(ans,ac[i]+max(amid,0)+acr[n-k-i-1])
    
print(ans)

Solution (Python):
n,k=map(int,input().split())
a=list(map(int,input().split()))
base=sum([x for x in a if x>0])
black=sum([-x for x in a[:k] if x<0])
white=sum([x for x in a[:k] if x>0])
ans=max(0,base-min(black,white))
for i in range(k,n):
  if a[i]>0:
    white+=a[i]
  else:
    black-=a[i]
  if a[i-k]>0:
    white-=a[i-k]
  else:
    black+=a[i-k]
  ans=max(ans,base-min(black,white))
  
print(ans)

Solution (Python):
n,k=map(int,input().split())
a=list(map(int,input().split()))
ans=sum([x for x in a if x>0])
np=sum([x for x in a[:k] if x>0])
nm=sum([-x for x in a[:k] if x<0])
ansb=nm
answ=np


for i in range(k,n):
  x=a[i]
  if x>0:
    np+=x
  else:
    nm-=x
  y=a[i-k]
  if y>0:
    np-=y
  else:
    nm+=y
  ansb=min(ansb,np)
  answ=min(answ,nm)
print(ans-min(ansb,answ))

Solution (Python):
n, k = map(int, input().split())
a = list(map(int, input().split()))
cum = [0]
for i in range(n):
    cum.append(min(a[i], 0) + cum[-1])
cum2 = [0]
for i in range(n):
    cum2.append(max(a[i], 0) + cum2[-1])
SUM = sum(max(a[i], 0) for i in range(n))
l = []
for i in range(n - k + 1):
    l.append(SUM + cum[i + k] - cum[i])
    l.append(SUM - cum2[i + k] + cum2[i])
print(max(l))

Solution (Python):
n,k = map(int,input().split())
a = list(map(int,input().split()))
ans = 0
d = 0
if n == k:
    print(max(0,sum(a)))
    exit()
for i in range(k,n):
    if a[i] > 0:
        d += a[i]
now = 0

for i in range(n):
    now += a[i]
    if i >= k:
        now -= a[i-k]
        if a[i] >= 0:
            d -= a[i]
        if a[i-k] >= 0:
            d += a[i-k]
        ans = max(ans,d+max(0,now))
    
print(ans)

Solution (Python):
from itertools import accumulate
N, K = map(int, input().split())
A = []
B = []
for a in map(int, input().split()):
    A.append(a)
    B.append( a if a > 0 else 0)
S = [0]+list(accumulate(A))
T = [0]+list(accumulate(B))
res = 0
for i in range(N-K+1):
    res = max(T[i] + max(S[i+K] - S[i], 0) + T[N]-T[i+K], res)
print(res)

Solution (Python):
from itertools import accumulate

def solve(A,K):

    opt = [0]+list(accumulate(a if a > 0 else 0 for a in A))
    plain = [0]+list(accumulate(A))

    def it():
        for i in range(len(A)-K+1):
            x = opt[i] + opt[-1] - opt[i+K]
            yield x
            yield x + plain[i+K] - plain[i]

    return max(it())


if __name__ == '__main__':
    N,K = map(int,input().split())
    A = list(map(int,input().split()))

    print(solve(A,K))

Solution (Python):
from itertools import accumulate
n, k = map(int, input().split())
a = list(map(int, input().split()))


left_sum = [0 for i in range(n+1)]
sum_value = 0
for i in range(n):
    if a[i] > 0:
        sum_value += a[i]
    left_sum[i+1] = sum_value


c = list(accumulate(a))
range_sum = [0 for i in range(n-k+1)]
range_sum[0] = max(c[k-1], 0)
for i in range(1, n-k+1):
    range_sum[i] = max(c[i+k-1] - c[i-1], 0)


a.reverse()


right_sum = [0 for i in range(n+1)]
sum_value = 0
for i in range(n):
    if a[i] > 0:
        sum_value += a[i]
    right_sum[i+1] = sum_value


ans = 0
for i in range(n-k+1):
    ans = max(ans, left_sum[i] + range_sum[i] + right_sum[n-k-i])
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
N,K = map(int,input().split())
A = list(map(int,input().split()))
class BIT:
    def __init__(self,data,op,default):
        self.op = op
        self.default = default
        N = len(data)
        self.l = 2**((N-1).bit_length())
        self.data = [default]*(self.l+1)
        for i in range(1,N+1):
            v = data[i-1]
            while i <= self.l:
                self.data[i] = self.op(self.data[i], v)
                i += i & -i
    def add(self,i,v):
        i += 1
        while i <= self.l:
            self.data[i] = self.op(self.data[i], v)
            i += i & -i

    def get(self,i):
        if i == -1:
            return 0
        res = 0
        i += 1
        while i > 0:
            res = self.op(res, self.data[i])
            i -= i & -i
        return res

B = [a if a >= 0 else 0 for a in A]

bit = BIT(B, lambda x,y : x+y, 0)

cs = [0]
t = 0
for a in A:
    t += a
    cs.append(t)

ans = -10**15
for i in range(N-K+1):
    r = bit.get(N-1) - bit.get(K+i-1) + bit.get(i-1)
    b = cs[i+K] - cs[i]
    ans = max(ans,r,r+b)
print(ans)

Solution (Python):
n, k = map(int, input().split())
alst = list(map(int, input().split()))

total_1 = 0
total_2 = 0
for i in range(k):
    total_1 += min(0, alst[i])
    total_2 += max(0, alst[i])
t_max = total_1
t_min = total_2
max_pos = 0
min_pos = 0
for i in range(n - k):
    total_1 += min(alst[i + k], 0) - min(alst[i], 0)
    total_2 += max(alst[i + k], 0) - max(alst[i], 0)
    if total_1 > t_max:
        t_max = total_1
        max_pos = i + 1
    if total_2 < t_min:
        t_min = total_2
        min_pos = i + 1
ans = 0
ans2 = 0

for i, num in enumerate(alst):
    if max_pos <= i < max_pos + k:
        ans += num
    else:
        ans += max(num, 0)
        
    if min_pos <= i < min_pos + k:
        pass
    else:
        ans2 += max(num, 0)

print(max(ans, ans2))

Solution (Python):
N,K=map(int,input().split())
a=list(map(int,input().split()))
ans=0
tmp=0
sa=[0]*(N+1)
A=[0]*(N+1)
for i in range(N):
  sa[i+1]=sa[i]+a[i]
  if a[i]>0:
    A[i+1]=A[i]+a[i]
  else:
    A[i+1]=A[i]
for i in range(N-K+1):
  tmp=sa[i+K]-sa[i]
  tmp2=A[i]+(A[-1]-A[i+K])
  
  if max(0,tmp)+tmp2>ans:
    ans=max(0,tmp)+tmp2
print(ans)

Solution (Python):
n,k = map(int,input().split())
a = list(map(int,input().split()))

cs_l = [0] * (n+2)
cs_r = [0] * (n+2)
for cs,ax in zip([cs_l,cs_r],[a,a[::-1]]):
    for i in range(n):
        cs[i+1] = cs[i] + max(ax[i],0)

cs_r = cs_r[::-1]

ans = 0
center = sum(a[:k])
for i in range(n-k+1):
    ans = max(ans, max(0,center) + cs_l[i] + cs_r[i+k+1])
    if(i==n-k):
        break
    center += a[i+k] - a[i]
print(ans)

Solution (Python):

printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True 
BIG = 10**18
R = 10**9 + 7


def ddprint(x):
  if DBG:
    print(x)

n,k = inm()
a = inl()
if n<-4 and k==2:
    3/0
mx = sum(a)
lacc = [0]*(n+1)
racc = [0]*(n+1)
for i in range(n):
    lacc[i+1] = lacc[i]+max(a[i],0)
for i in range(n-1,-1,-1):
    racc[i] = racc[i+1]+max(a[i],0)
sk = sum(a[:k])
for i in range(n-k+1):
    mx = max(mx,lacc[i]+max(sk,0)+racc[i+k])
    if i<n-k:
        sk += a[i+k]-a[i]
print(mx)

Solution (Python):
from itertools import accumulate
N, K = map(int, input().split())
As = list(map(int, input().split()))

csum = list(accumulate(As, initial = 0))
csum_of_positives = list(accumulate([max(A, 0) for A in As], initial = 0))


max_score = 0
for i in range(N-K+1):
    score = 0
    all_black = csum[i+K] - csum[i]
    if all_black > 0: 
        score += all_black
    score += csum_of_positives[i] 
    score += csum_of_positives[N] - csum_of_positives[i+K] 
    max_score = max(max_score, score)

print(max_score)

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

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

white = [0] * (N + 1)
black = [0] * (N + 1)
for i, d in enumerate(a):
  if d < 0:
    white[i + 1] += d
  else:
    black[i + 1] += d
  white[i + 1] += white[i]
  black[i + 1] += black[i]

score = 0
for i in range(N - K + 1):
  score = max(black[N] + white[i + K] - white[i], black[N] - black[i + K] + black[i], score)

print(score)

Solution (Python):
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from itertools import accumulate
    n, k = map(int, readline().split())
    a = list(map(int, readline().split()))
    b = [0] * (n + 1)
    c = [0] * (n + 1)

    for i, x in enumerate(a, 1):
        b[i] = b[i - 1] + max(x, 0)
        c[i] = c[i - 1] + x

    ans = 0
    for i in range(n - k + 1):
        score = b[i] + max(0, c[i + k] - c[i]) + (b[n] - b[i + k])
        ans = max(ans, score)

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
n,k=map(int,input().split())
a=list(map(int,input().split()))
maxans=0
sumplus=[0]
for i in range(n):
  if a[i]>0:
    maxans+=a[i]
  sumplus.append(maxans)
penalty=10**18
summinus=[0]
current=0
for i in range(n):
  if a[i]<0:
    current-=a[i]
  summinus.append(current)
for i in range(k,n+1):
  penalty=min(penalty,sumplus[i]-sumplus[i-k])
  penalty=min(penalty,summinus[i]-summinus[i-k])
print(maxans-penalty)

Solution (Python):
N,K=map(int,input().split())
A=list(map(int,input().split()))
B=[0]
C=[0]
for i in range(N):
  B.append(B[i]+max(0,A[i]))
  C.append(C[i]-min(0,A[i]))
P=10**20
for i in range(N-K+1):
  P=min(P,B[i+K]-B[i],C[i+K]-C[i])
print(B[N]-P)

Solution (Python):
import sys
import numpy as np
from numba import njit

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit('(i8,i8,i8[:])', cache=True)
def main(N, K, A):
    B = np.maximum(A, 0)
    Acum = np.zeros(len(A) + 1, np.int64)
    Bcum = np.zeros(len(A) + 1, np.int64)
    Acum[1:] = np.cumsum(A)
    Bcum[1:] = np.cumsum(B)
    ret = -(10**18)
    for l in range(N - K + 1):
        r = l + K
        sum1 = Bcum[l]
        sum2 = Bcum[-1] - Bcum[r]
        sum3 = Acum[r] - Acum[l]
        x = sum1 + sum2 + max(sum3, 0)
        ret = max(ret, x)
    return ret

N, K = map(int, readline().split())
A = np.array(read().split(), np.int64)

print(main(N, K, A))

Solution (Python):
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, K = map(int, readline().split())
A = np.array(read().split(), np.int64)

def main(N, K, A):
    B = np.maximum(A, 0)
    Acum = np.zeros(N + 1, np.int64)
    Bcum = np.zeros(N + 1, np.int64)
    Acum[1:] = np.cumsum(A)
    Bcum[1:] = np.cumsum(B)
    sum1 = Bcum[:N - K + 1]
    sum2 = Bcum[-1] - Bcum[K:]
    sum3 = Acum[K:] - Acum[:N - K + 1]
    x = sum1 + sum2 + np.maximum(sum3, 0)
    return x.max()

print(main(N, K, A))

Solution (Python):
import sys
import numpy as np
from numba import njit

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, K = map(int, readline().split())
A = np.array(read().split(), np.int64)

@njit('(i8,i8,i8[:])', cache=True)
def main(N, K, A):
    B = np.maximum(A, 0)
    Acum = np.zeros(len(A) + 1, np.int64)
    Bcum = np.zeros(len(A) + 1, np.int64)
    Acum[1:] = np.cumsum(A)
    Bcum[1:] = np.cumsum(B)
    ret = -(10**18)
    for l in range(N - K + 1):
        r = l + K
        sum1 = Bcum[l]
        sum2 = Bcum[-1] - Bcum[r]
        sum3 = Acum[r] - Acum[l]
        x = sum1 + sum2 + max(sum3, 0)
        ret = max(ret, x)
    return ret

print(main(N, K, A))

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")



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


def cumsum(a, pos=False):
    """l[i] = sum(a[:i]) なるlを返す
    sum(a[i:j]) == l[j+1] - l[i]
    """
    c = 0
    l = [None] * (len(a)+1)
    for i,num in enumerate(a):
        l[i] = c
        c += num if not pos else max(0, num)
    l[-1] = c
    return l

ca = cumsum(a)
pca = cumsum(a, pos=True)
ans = 0
for i in range(0, n-k+1):
    ans = max(ans, pca[i] + max(0,ca[i+k]-ca[i]) + (pca[n]-pca[i+k]))
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

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

    L = [0] * (N + 1)
    for i in range(N):
        L[i + 1] = L[i]
        if A[i] > 0:
            L[i + 1] += A[i]
    
    R = [0] * (N + 1)
    for i in range(N - 1,-1,-1):
        R[i] = R[i + 1]
        if A[i] > 0:
            R[i] += A[i]
    
    ans = 0
    range_sum = sum(A[:K])
    for i in range(K,N + 1):
        ret = max(L[i - K] + range_sum + R[i],L[i - K] + R[i])
        ans = max(ans,ret)
        range_sum -= A[i - K]
        if i < N:
            range_sum += A[i]
    print(ans)
if __name__ == '__main__':
    main()

Solution (Python):

N,K = map(int,input().split())
a = [0] + list(map(int,input().split()))
ans = 0
tmp = [0,0]
for i in range(1,K+1):
    ans += max(0,a[i])
    tmp[a[i]>=0] += abs(a[i])
loss = min(tmp)
for i in range(K+1,N+1):
    ans += max(0,a[i])
    tmp[a[i-K]>=0] -= abs(a[i-K])
    tmp[a[i]>=0] += abs(a[i])
    loss = min(loss,min(tmp))
print(ans-loss)

Solution (Python):
import math

import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,k = map(int,ipt().split())
    a = [int(i) for i in ipt().split()]
    sm = 0
    for i in a:
        if i > 0:
            sm += i
    ws = 0
    bs = 0
    for i in a[:k:]:
        if i > 0:
            ws += i
        else:
            bs -= i
    ms = min(ws,bs)
    for i in range(n-k):
        ai = a[i]
        af = a[i+k]
        if ai > 0:
            ws -= ai
        else:
            bs += ai
        if af > 0:
            ws += af
        else:
            bs -= af
        if ms > ws:
            ms = ws
        elif ms > bs:
            ms = bs
    print(sm-ms)



    return

if __name__ == '__main__':
    main()

Solution (Python):
N, K = map(int, input().split())
A = [int(x) for x in input().split()]

S0 = 0
S1 = sum(A[i] for i in range(K))
S2 = sum(A[i] for i in range(K, N) if A[i] > 0)
A.append(0)

ans = sum(A)
for i in range(N-K+1):

    ans = max(ans, S0 + max(S1, 0) + S2)
    if A[i] > 0:
        S0 += A[i]
    if A[i+K] > 0:
        S2 -= A[i+K]
    S1 = S1 - A[i] + A[i+K]
print(ans)

Solution (Python):
n, k = map(int, input().split())
A = list(map(int, input().split()))
B = [max(0, a) for a in A]

from itertools import accumulate
A = [0]+A
A = list(accumulate(A))
B = [0]+B
B = list(accumulate(B))




ans = -10**18
for i in range(n-k+1):
    temp = max(0, A[i+k]-A[i])
    temp += B[i]-B[0]
    temp += B[-1]-B[i+k]
    
    ans = max(ans, temp)
print(ans)

Solution (Python):
n, k = map(int, input().split())
A = list(map(int, input().split()))
B = [max(0, a) for a in A]

from itertools import accumulate
A = [0]+A
A = list(accumulate(A))
B = [0]+B
B = list(accumulate(B))




ans = -10**18
for i in range(n-k+1):
    temp = max(0, A[i+k]-A[i])
    temp += B[i]-B[0]
    temp += B[-1]-B[i+k]
    
    ans = max(ans, temp)
print(ans)

Solution (Python):
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    N,K = LI()
    a = LI()

    ac = [0]
    ap = [0]
    for x in a:
        ac.append(ac[-1]+x)
        ap.append(ap[-1]+(x if x>0 else 0))

    ans = -INF
    for i in range(N-K+1):
        bw = max(ac[i+K] - ac[i],0)
        l = ap[i]
        r = ap[N] - ap[i+K]
        ans = max(ans,bw+l+r)
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
N, K = map(int, input().split())
A = list(map(int, input().split()))

mx = sum(map(lambda a: max(a, 0), A))

M = sum(map(lambda a: max(a, 0), A[:K]))
S = sum(A[:K])

ans = mx - M + max(0, S)

for l, r in zip(A, A[K:]):
    M -= max(l, 0)
    M += max(r, 0)
    S -= l
    S += r

    ans = max(ans, mx - M + max(S, 0))

print(ans)

Solution (Python):
from itertools import accumulate
import sys
def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    *A, = map(int, input().split())

    C = [0] + list(accumulate(A))
    D = [0] + list(accumulate([a if a > 0 else 0 for a in A]))
    ans = -10 ** 10
    for i in range(1, N + 1 - K + 1):
        s = D[i - 1] + D[N] - D[i + K - 1]
        t = C[i + K - 1] - C[i - 1]
        s += t if t > 0 else 0
        ans = max(ans, s)
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline

n, k = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]

s = sum(a[:k])
t = 0
for i in range(k, n):
    if a[i] > 0:
        t += a[i]
ans = max(t, s + t)

for i in range(n - k):
    s -= a[i]
    s += a[k + i]
    if a[k + i] > 0:
        t -= a[k + i]
    if a[i] > 0:
        t += a[i]
    ans = max(ans, s + t, t)
    
print(ans)

Solution (Python):
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))

    cum_all = [0 for _ in range(n+1)]
    cum_positive = [0 for _ in range(n+1)]
    for i in range(n):
        cum_all[i+1] = cum_all[i] + a[i]
        cum_positive[i+1] = cum_positive[i] + max(0, a[i])

    ans = 0
    for i in range(n-k+1):
        score1 = (cum_positive[i] - cum_positive[0]) + (cum_positive[n] - cum_positive[i+k])
        if score1 > ans:
            ans = score1
        score2 = (cum_positive[i] - cum_positive[0]) + (cum_all[i+k] - cum_all[i]) + (cum_positive[n] - cum_positive[i+k])
        if score2 > ans:
            ans = score2

    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline

N, K = map(int, input().split())
a = list(map(int, input().split()))
acc1 = [0]
acc2 = [0]

for ai in a:
    acc1.append(acc1[-1]+ai)
    acc2.append(acc2[-1]+max(0, ai))

ans = 0

for i in range(N-K+1):
    ans = max(ans, max(0, acc1[i+K]-acc1[i])+acc2[i]+acc2[N]-acc2[i+K])

print(ans)

Solution (Python):
n,k=map(int,input().split())
a=list(map(int,input().split()))
b=[0]+a
for i in range(n):
  b[i+1]=min(b[i+1],0)
  b[i+1]+=b[i]
c=[0]+a
for i in range(n):
  c[i+1]=max(c[i+1],0)
  c[i+1]+=c[i]
m=sum(max(i,0)for i in a)
ans=[]
for i in range(n-k+1):
  s=b[i+k]-b[i]
  ss=c[i+k]-c[i]
  ans+=[m+s,m-ss]
print(max(ans))

Solution (Python):
from itertools import accumulate
import sys
input = sys.stdin.readline

N, K = map(int, input().split())
a = list(map(int, input().split()))
cum = list(accumulate([0, 0] + a))
left = [0] * (N+2)
for i in range(1, N+1):
    left[i] = left[i-1]
    if a[i-1] > 0:
        left[i] += a[i-1]
right = [0] * (N+2)
for i in range(1, N+1)[::-1]:
    right[i] = right[i+1]
    if a[i-1] > 0:
        right[i] += a[i-1]
ans = 0
for i in range(1, N-K+2):
    tmp = left[i-1] + right[i+K]
    if cum[i+K] - cum[i] > 0:
        tmp += cum[i+K] - cum[i]
    ans = max(ans, tmp)
print(ans)

Solution (Python):
N,K,*A = map(int, open(0).read().split())
m = sum(A[:K])
n = sum(c if c>0 else 0 for c in A[K:])
ans = max(m+n,n)
for i in range(N-K):
  m -= A[i]
  m += A[i+K]
  if A[i]>0:
    n += A[i]
  if A[i+K]>0:
    n -= A[i+K]
  ans = max(ans,n+m,n)
print(ans)

Solution (Python):
N, K = map(int, input().split())
A = list(map(int, input().split()))

ans = 0  


best = [0]
for a in A:
    if a < 0:
        a = 0
    best.append(best[-1] + a)

for i in range(N - K + 1):
    if i == 0:
        black = sum(A[:K])
    else:
        black = black + A[i + K - 1] - A[i - 1]
    score_white = best[N] - best[i + K] + best[i] - best[0]
    score_black = black + score_white
    ans = max(ans, score_white, score_black)


print(ans)

Solution (Python):
N, K = map(int, input().split())
A = list(map(int, input().split()))

ans = sum([a for a in A if a > 0])
B = [a if a <= 0 else 0 for a in A]

s = sum(B[:K])
s_max = s
for i in range(N-K):
  s += B[i+K] - B[i]
  s_max = max(s_max, s)

B = [a if a > 0 else 0 for a in A]
s = sum(B[:K])
s_min = s
for i in range(N-K):
  s += B[i+K] - B[i]
  s_min = min(s_min, s)

print(max(ans+s_max, ans-s_min))

Solution (Python):
N, K = map(int, input().split())
A = list(map(int, input().split()))

ans = sum([a for a in A if a > 0])
B = [a if a <= 0 else 0 for a in A]

s = sum(B[:K])
s_max = s
c = sum([1 for a in A[:K] if a <= 0])
c_max = c
for i in range(N-K):
  s += B[i+K] - B[i]
  s_max = max(s_max, s)
  c += (A[i+K]<=0) - (A[i]<=0)
  c_max = max(c_max, c)

if c_max == K:
  print(ans)
  quit()

B = [a if a > 0 else 0 for a in A]
s = sum(B[:K])
s_min = s
for i in range(N-K):
  s += B[i+K] - B[i]
  s_min = min(s_min, s)

print(max(ans+s_max, ans-s_min))

Solution (Python):
N,K=map(int,input().split())
a=list(map(int,input().split()))
sumf=[0 for i in range(N)]
sumb=[0 for i in range(N)]
Ksum=[0 for i in range(N)]

sumf[0]=(a[0]>=0)*a[0]
for i in range(1,N):
    sumf[i]=sumf[i-1]+(a[i]>=0)*a[i]

sumb[-1]=(a[-1]>=0)*a[-1]
for i in range(1,N):
    sumb[-i-1]=sumb[-i]+(a[-i-1]>=0)*a[-i-1]

s=sum(a[:K])
Ksum[0]=s
for i in range(1,N-K+1):
    s-=a[i-1]
    s+=a[i+K-1]
    Ksum[i]=s

ans=-float("inf")
for i in range(0,N-K+1):
    test=0
    if i!=0:
        test+=sumf[i-1]
    if i!=N-K:
        test+=sumb[i+K]
    test2=test
    test+=Ksum[i]

    ans=max(ans,test,test2)

print(ans)

Solution (Python):
from itertools import accumulate

def resolve():
    n,k = map(int, input().split())
    a = list(map(int, input().split()))
    x = [i if i > 0 else 0 for i in a]
    ans = 0
    acc = [0] + list(accumulate(x))
    aaa = [0] + list(accumulate(a))
    for i in range(n+1-k):
        tmp = acc[i] + acc[-1] - acc[i+k]
        if tmp > ans:
            ans = tmp
        if tmp + aaa[i+k] - aaa[i] > ans:
            ans = tmp + aaa[i+k] - aaa[i]

    print(ans)

if __name__ == '__main__':
    resolve()

Solution (Python):
n, k = map(int,input().split())
A = list(map(int,input().split()))

pos = 0
neg = 0

for a in A[:k]:
  if a>0:
    pos += a
  else:
    neg += a
  
wp = pos
wn = neg
ans = float('inf')
for i,a in enumerate(A[k:]):
  if a>0:
    pos += a
    wp += a
  else:
    neg += a
    wn += a
  b = A[i]
  if b>0:
    wp -= b
  else:
    wn -= b
  ans = min(ans, wp, -wn)
print(max(pos - ans, pos+neg, 0))

Solution (Python):
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))





N,K = LI()
a = LI()

dp_l = [0]*N
for i in range(N):
    if a[i] > 0:
        dp_l[i] = dp_l[i-1] + a[i]
    else:
        dp_l[i] = dp_l[i-1]

dp_r = [0]*N
dp_r[N-1] = a[i] if a[i] > 0 else 0
for i in range(N-1)[::-1]:
    if a[i] > 0:
        dp_r[i] = dp_r[i+1] + a[i]
    else:
        dp_r[i] = dp_r[i+1]

kblacks = [0]*(N-K+1)
kblacks[0] = sum(a[:K])
for i in range(1,N-K+1):
    kblacks[i] = kblacks[i-1]+a[K+i-1]-a[i-1]

ans = -float('inf')
for i in range(N-K+1):
    temp = 0
    if i-1 >= 0:
        temp += dp_l[i-1]
    if i+K <= N-1:  
        temp += dp_r[i+K]
    ans = max(ans,temp,temp+kblacks[i])

print(ans)

Solution (Python):
from itertools import accumulate

n,k = map(int, input().split())
a = list(map(int, input().split()))
b = [max(0,i) for i in a]
cumsum_a = [0] + list(accumulate(a))
cumsum_b = [0] + list(accumulate(b))
ans = 0
for i in range(n-k+1):
  tmp = max(0,cumsum_a[i+k]-cumsum_a[i]) + cumsum_b[i] + cumsum_b[n] - cumsum_b[i+k]
  ans = max(ans,tmp)
print(ans)

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
from pprint import pprint
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(2147483647)
INF = 10 ** 15
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, k = LI()
A = LI()
acc = [0] + list(accumulate(A))
plus_acc = [0] + list(accumulate([i if i > 0 else 0 for i in A]))
ans = -INF
for l in range(n - k + 1):
    r = l + k
    ans = max(ans, max(acc[r] - acc[l], 0) + plus_acc[l] + plus_acc[n] - plus_acc[r])

print(ans)

Solution (Python):

import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, K = lr()
A = lr()
streak = N
neg_max = N
for i in range(N):
    if A[i] <= 0:
        streak += 1
    else:
        neg_max = min(neg_max, streak)
        streak = 0

Anp = np.array(A)
positive_sum = Anp[Anp>0].sum()
answer = - 10 ** 15
if neg_max >= K:
    answer = positive_sum
else:
    neg_sum = 0
    pos_sum = 0
    for i in range(K):
        if A[i] < 0:
            neg_sum += A[i]
        else:
            pos_sum += A[i]
    for i in range(N-K+1):
        temp = positive_sum + neg_sum
        temp2 = positive_sum - pos_sum
        answer = max(answer, temp, temp2)
        if i + K >= N:
            break
        if A[i] > 0:
            pos_sum -= A[i]
        else:
            neg_sum -= A[i]
        if A[i+K] > 0:
            pos_sum += A[i+K]
        else:
            neg_sum += A[i+K]

print(answer)

Solution (Python):
import sys
input = sys.stdin.buffer.readline

def main():
    N,K = map(int,input().split())
    a = list(map(int,input().split()))
    
    cum = [0]
    pluscum = [0]
    
    for i in range(N):
        cum.append(cum[-1]+a[i])
        if a[i] > 0:
            pluscum.append(pluscum[-1]+a[i])
        else:
            pluscum.append(pluscum[-1])

    ans = -(10**15)
    for i in range(N-K+1):
        ret = pluscum[i]+(pluscum[-1]-pluscum[i+K])+max((cum[i+K]-cum[i]),0)
        ans = max(ans,ret)
    
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
n,k = map(int,input().split())
a = list(map(int, input().split()))
al = [0]*(n+1)
pl = [0]*(n+1)
ans = 0
for i in range(n):
  al[i+1] = al[i] + a[i]
  pl[i+1] = pl[i]
  if a[i] > 0: pl[i+1] += a[i]
for r in range(k,n+1):
  l = r-k
  cur = pl[l] + max(0, al[r] - al[l]) + pl[n] - pl[r]
  if ans < cur: ans = cur
print(ans)

Solution (Python):
n,k = map(int,input().split())
a = list(map(int, input().split()))
al = [0]*(n+1)
pl = [0]*(n+1)
ans = 0
for i in range(n):
  al[i+1] = al[i] + a[i]
  pl[i+1] = pl[i]
  if a[i] > 0: pl[i+1] += a[i]
for r in range(k-1,n):
  l = r-k+1
  cur = pl[l] + max(0, al[r+1] - al[l]) + pl[n] - pl[r+1]
  if ans < cur: ans = cur
print(ans)

Solution (Python):
from itertools import accumulate

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

a_plus = [e if e > 0 else 0 for e in a]

acc = [0] + list(accumulate(a))
acc_plus = [0] + list(accumulate(a_plus))
ans = 0
for i in range(1, n - k + 2):
    white = acc_plus[i-1] + acc_plus[n] - acc_plus[i+k-1]
    black = white + acc[i+k-1] - acc[i-1]
    ans = max(ans, white, black)

print(ans)

Solution (Python):


n, k  = [int(i) for i in input().split()]
a     = [int(i) for i in input().split()]

plus,minus = [0],[0] 
plus_accumulate  = 0
minus_accumulate = 0

for v in a:
    if v>=0:
        plus_accumulate += v
    else:
        minus_accumulate += abs(v) 
    plus.append(plus_accumulate)
    minus.append(minus_accumulate)    
        
minimum_lost = 10**18
for i in range(n-k+1):
    black_lost = minus[i+k] - minus[i]
    white_lost = plus[i+k] - plus[i]
    minimum_lost = min(minimum_lost, black_lost, white_lost)

print(plus_accumulate - minimum_lost)

Solution (Python):
n,k=map(int,input().split())
a=list(map(int,input().split()))
sum_a=[0]*(n+1)
b=[max(0,a[i]) for i in range(n)]
sum_b=[0]*(n+1)
sum_a[1]=a[0]
sum_b[1]=b[0]
for i in range(1,n):
  sum_a[i+1]=sum_a[i]+a[i]
  sum_b[i+1]=sum_b[i]+b[i]
ans=-10**18
for i in range(n-k+1):
  l,r=i,i+k
  cnt=sum_b[l]-sum_b[0]
  cnt+=max(0,sum_a[r]-sum_a[l])
  cnt+=sum_b[n]-sum_b[r]
  ans=max(ans,cnt)
print(ans)

Solution (Python):

N,K = map(int, input().split())
A = [int(i) for i in input().split()]


S1 = [0] * (N + 1)

S2 = [0] * (N + 1)
for i in range(N):
    S1[i+1] = S1[i] + A[i]
    S2[i+1] = S2[i] + (A[i] if A[i] >= 0 else 0)

ans = -float("inf")
for i in range(N - K + 1):
    left, right = i, i + K
    
    tmp = S2[left] - S2[0] 
    tmp += max(0, S1[right] - S1[left]) 
    tmp += S2[N] - S2[right] 

    ans = max(ans, tmp)

print(ans)

Solution (Python):
from itertools import accumulate
n,k=map(int,input().split())
l=list(map(int,input().split()))
b=[0 for i in range(n+1)]
h=[0 for i in range(n+1)]
for i,j in enumerate(l,1):
    if j>0:
        b[i]=j
    else:
        h[i]=-j
b,h=list(accumulate(b)),list(accumulate(h))
ma=b[-1]
ans=0
for i in range(n-k+1):
    ans=max(ans,ma-(b[i+k]-b[i]),ma-(h[i+k]-h[i]))
print(ans)

Solution (Python):
from itertools import accumulate as acc
N, K, *A = map(int, open(0).read().split())
B = [0]+list(acc(A))
M = list(acc(a if a>0 else 0 for a in A))
ans = -10**30
for i in range(N-K+1):
  mi = B[i+K]-B[i]
  c = M[N-1] - M[i+K-1]
  if i>0:
    c += M[i-1]
  ans = max(ans,mi+c,c)
print(ans)