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=map(int,input().split())
arr=list(map(int,input().split()))
cum1=[0]*n
cum1[0]=arr[0]
cum2=[0]*n
if arr[0]>=0:
  cum2[0]=arr[0]
for i in range(1,n):
  cum1[i]=arr[i]+cum1[i-1]
  cum2[i]=cum2[i-1]
  if arr[i]>=0:
    cum2[i]+=arr[i]
ans=0
for i in range(n-k+1):
  if i==0:
    tmp=max(0,cum1[i+k-1])+(cum2[n-1]-cum2[i+k-1])
  elif i==n-k:
    tmp=max(0,(cum1[i+k-1]-cum1[i-1]))+cum2[i-1]
  else:
    tmp=max(0,(cum1[i+k-1]-cum1[i-1]))+(cum2[n-1]-cum2[i+k-1]+cum2[i-1])
  ans=max(ans,tmp)
print(ans)

Solution (Python):
N,K = map(int,input().split())
*A, = map(int,input().split())
S = [0]*(N+1)
Sp = [0]*(N+1)
for i,a in enumerate(A,1):
    S[i] = S[i-1]+a
    Sp[i] = Sp[i-1] + max(0,a)
ans = 0
for i in range(N-K+1):
    ans = max(ans,max(0,S[K+i]-S[i]) + Sp[-1] - (Sp[K+i]-Sp[i]))
print(ans)

Solution (Python):
from itertools import*
from math import*
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())
a = list(map(int,input().split()))
A = [0]*(N+1)
S = [0]*(N+1)

for i in range(N):
    A[i+1] = A[i]+max(0,a[i])
    S[i+1] = S[i]+a[i]

ans = -inf
for i in range(0,N-K+1):
    ans = max(ans,A[i]+max(0,S[i+K]-S[i])+(A[N]-A[i+K]))

print(ans)

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

S = [0]
s = 0
for i in range(N):
    s+=a[i]
    S.append(s)

S1 = [0]
s = 0

for i in range(N):
    s+=max(0,a[i])
    S1.append(s)
max_score=0
for i in range(N-K+1):
    max_score=max(S1[i]+max(S[i+K]-S[i],0) + S1[N]-S1[i+K],max_score)

print(max_score)

Solution (Python):
import sys
input = sys.stdin.readline
n,k=map(int,input().split())
A=[int(i) for i in input().split()]
S,SS=[0]*(n+1),[0]*(n+1)
for i in range(n):
  S[i+1]=S[i]+A[i]
  SS[i+1]=SS[i]+max(0,A[i])
ans=-float("inf")
for i in range(n-k+1):
  ans=max(ans,SS[i]+SS[n]-SS[k+i]+max(0,S[k+i]-S[i]))
print(ans)

Solution (Python):
N, K = map(int,input().split())
L = list(map(int,input().split()))
M = []
for e in L:
    M.append(max(0,e))

S = [0]*(N+1)
T = [0]*(N+1)
for k in range(N):
    S[k+1] = L[k]+S[k]
    T[k+1] = M[k]+T[k]
ans = 0
for k in range(N-K+1):
    ans = max(ans, T[k] + max(0,S[k+K]-S[k]) + T[N]-T[k+K])
print(ans)

Solution (Python):
n, k = [int(item) for item in input().split()]
a = [int(item) for item in input().split()]

asum = [0] * (n + 1)
aplussum = [0] * (n + 1)
for i in range(0, n):
    asum[i+1] += asum[i] + a[i]
    aplussum[i+1] += aplussum[i] + max(a[i], 0)

l = 1; r = k
ans = 0
while r <= n:
    lr = aplussum[n] - aplussum[r] + aplussum[l-1]
    mid = max(asum[r] - asum[l-1], 0)
    ans = max(ans, lr + mid)
    l += 1; r += 1 
print(ans)

Solution (Python):
n,k=map(int,input().split())
a=[int(i) for i in input().split()]
acc=[0]*(n+1)
pos=[0]*(n+1)
for i in range(n):
    acc[i+1]+=a[i]+acc[i]
    pos[i+1]+=max(a[i],0)+pos[i]

ans=-10**18

for i in range(n-k+1):
    ans=max(ans,acc[i+k]-acc[i]+pos[i]+pos[-1]-pos[i+k])
    ans=max(ans,pos[i]+pos[-1]-pos[i+k])
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 = -10**10
for i in range(n):
  al[i+1] = al[i] + a[i]
  pl[i+1] = pl[i] + max(0,a[i])
for i in range(n-k+1):
  l,r = i,i+k-1
  cur = max(0,al[r+1]-al[l]) + pl[l] + pl[-1] - pl[r+1]
  if cur > ans:
    ans = cur
print(ans)

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

black = sum(a[:k])
white = 0

for i in range(k,n):
    if a[i]>0:
        white += a[i]
black += white

b = [black]
w = [white]

for i in range(n-k):
    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]
    b.append(black)
    w.append(white)

print(max(max(b),max(w)))

Solution (Python):
N, K = map(int, input().split())
a = list(map(int, input().split()))
sa = [0]
for i in range(N):
    sa.append(sa[-1] + a[i])

sb = [0]
for i in range(N):
    sb.append(sb[-1] + max(0, a[i]))


num = 0
for i in range(N - K + 1):
    num = max(num, sb[i] + max(0, sa[i + K] - sa[i]) + sb[N] - sb[i + K])

print(num)

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

al, bl = [0], [0]
for a in alist:
  al.append(al[-1] + a)
  bl.append(bl[-1] + max(0, a))

al.append(al[-1])
bl.append(bl[-1])

ans = 0
for i in range(0, n - k + 2):
  bsum = bl[-1] - bl[i + k] + bl[i]
  bb = bsum + al[i + k] - al[i]
  ans = max(ans, bb, bsum)
print(ans)

Solution (Python):
from itertools import accumulate as acc

N,K=map(int,input().split())
a=list(map(int,input().split()))
b=[max(a[i],0) for i in range(N)]

A=list(acc(a))
B=list(acc(b))

ans=0
for i in range(N-K+1):
    if i==0: tmp=max(A[K-1],0)+(B[N-1]-B[K-1])
    elif i==N-K: tmp=B[N-K-1]+max(A[N-1]-A[N-K-1],0)
    else: tmp=B[i-1]+max(A[i+K-1]-A[i-1],0)+(B[N-1]-B[i+K-1])
    ans=max(ans,tmp)


print(ans)

Solution (Python):
n, k = map(int, input().split())
a = list(map(int, input().split()))
asum = [0 for _ in range(n+1)]
psum = [0 for _ in range(n+1)]
for i in range(n):
    asum[i+1] = asum[i] + a[i]
    psum[i+1] = psum[i] + max(0, a[i])
ans = 0
for i in range(n-k+1):
    ans = max(ans, psum[i]-psum[0]+asum[i+k]-asum[i]+psum[n]-psum[i+k])
    ans = max(ans, psum[i]-psum[0]+psum[n]-psum[i+k])
print(ans)

Solution (Python):
import numpy as np
n, k = map(int, input().split())
a = list(map(int, input().split()))
a = np.array(a)

cs_plus = np.cumsum((a > 0) * a)
cs_plus = [0] + list(cs_plus)
plus = [v2 - v1 for v1, v2 in zip(cs_plus[:-k], cs_plus[k:])]

cs_minus = np.cumsum((a < 0) * a)
cs_minus = [0] + list(cs_minus)
minus = [v2 - v1 for v1, v2 in zip(cs_minus[:-k], cs_minus[k:])]

print(cs_plus[-1] - min(min(plus), -max(minus)))

Solution (Python):
from itertools import accumulate as ac
n,k=map(int,input().split())
a=list(map(int,input().split()))
b=[0]+list(ac(a))
c=[0]+list(ac([(0 if i<0 else i)for i in a]))
d=0
for i in range(n-k+1):
    d=max(d,max(b[i+k]-b[i],0)+c[i]+c[-1]-c[i+k])
print(d)

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()

from itertools import accumulate

def main():
    N, K = LI()
    A = LI()
    negs = [min(0, a) for a in A]
    poss = [max(0, a) for a in A]
    nacc = [0] + list(accumulate(negs))
    pacc = [0] + list(accumulate(poss))
    neg = max(q - p for p, q in zip(nacc, nacc[K:]))
    pos = min(q - p for p, q in zip(pacc, pacc[K:]))
    ans = sum(a for a in A if a > 0) + max(neg, -pos)

    return ans

print(main())

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

sa = [0]
sb = [0]
for i in range(N):
    sa.append(sa[-1] + a[i])
    sb.append(sb[-1] + max(0, a[i]))

ans = 0
for i in range(N - K + 1):
    a = sa[i + K] - sa[i]
    b = sb[i + K] - sb[i]
    ans = max(ans, sb[N] - b + max(a, 0))
print(ans)

Solution (Python):
import sys
from collections import deque
import copy
import math
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline


def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, K] = [int(input_raw[0]), int(input_raw[1])]
    input_raw = read_func().strip().split()
    A = [int(input_raw[i]) for i in range(N)]

    sumA = [0 for i in range(N + 1)]
    sumAplus = [0 for i in range(N + 1)]
    for i in range(N):
        sumA[i + 1] = sumA[i] + A[i]
        sumAplus[i + 1] = sumAplus[i] + max(A[i], 0)

    max_score_b = 0
    max_score_w = 0
    for i in range(1, N - K + 2):
        score_b = (sumAplus[i - 1] - sumAplus[0]) + (sumA[i + K - 1] - sumA[i - 1]) + (sumAplus[N] - sumAplus[i + K - 1])
        max_score_b = max(max_score_b, score_b)
        score_w = (sumAplus[i - 1] - sumAplus[0]) + (sumAplus[N] - sumAplus[i + K - 1])
        max_score_w = max(max_score_w, score_w)
    print max(max_score_b, max_score_w)


if __name__ == '__main__':
    main()

Solution (Python):
N,K = map(int,input().split())
A = list(map(int,input().split()))
plusminus = [0]*len(A)
plusor0 = [0]*len(A)
plusminus[0] = A[0]
plusor0[0] = max(0,A[0])
for i in range(1,N):
  plusminus[i] = plusminus[i-1]+A[i]
  plusor0[i] = plusor0[i-1]+max(0,A[i])
plusminus.insert(0,0)
plusor0.insert(0,0)
ans = 0
for i in range(N-K+1):
  s = plusminus[i+K]-plusminus[i]
  if i == 0:
    s += plusor0[N]-plusor0[K]
  elif i == N-K:
    s += plusor0[N-K]
  else:
    s += plusor0[i]+plusor0[N]-plusor0[i+K]
  if ans <= s:
    ans = s
for i in range(N-K+1):
  s = 0
  if i == 0:
    s += plusor0[N]-plusor0[K]
  elif i == N-K:
    s += plusor0[N-K]
  else:
    s += plusor0[i]+plusor0[N]-plusor0[i+K]
  if ans <= s:
    ans = s
print(ans)

Solution (Python):
from itertools import accumulate

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N, K = map(int, input().split())
L = list(map(int, input().split()))
accL = [0] + list(accumulate(L))
_pos = [l if l > 0 else 0 for l in L]
accPos = [0]+list(accumulate(_pos))
sumPos = accPos[-1]

ans = -float('inf')
for s in range(0, N-K+1):
    tmpS = accL[s+K]-accL[s]
    posS = accPos[s+K]-accPos[s]
    ans = max(ans, tmpS+sumPos-posS, sumPos-posS)
print(ans)

Solution (Python):


import sys


INF = float('inf')
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


def main():
    n, k = LI()
    A = LI()

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

    ans = 0
    
    
    for i in range(n - k + 1):
        ans = max(ans, max(C[i + k] - C[i], 0) + C2[i] + C2[-1] - C2[i + k])

    return ans


print(main())

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

s = sum(i for i in a if i > 0)

ans = 0
psum = 0
asum = 0
for i in range(n-k+1):
    if i == 0:
        for j in range(k):
            if a[j]>0:
                psum += a[j]
            asum += a[j]
    else:
        if a[i-1] > 0:
            psum -= a[i-1]
        asum -= a[i-1]
        if a[i+k-1] > 0:
            psum += a[i+k-1]
        asum += a[i+k-1]
    ans = max(ans, s - psum +[0,asum][asum>0])
print(ans)

Solution (Python):
import sys
input=sys.stdin.readline
from itertools import accumulate
n,k=map(int,input().split())
A=list(map(int,input().split()))
SA=[0]+list(accumulate(A))
B=[]
for a in A:
    B.append(max(0,a))
SB=[0]+list(accumulate(B))
SB.append(SB[-1])
ans=0
for i in range(n-k+1):
    ans=max(ans,SB[i]+SA[i+k]-SA[i]+SB[n]-SB[i+k])
    ans=max(ans,SB[i]+SB[n]-SB[i+k])
print(ans)

Solution (Python):
import numpy as np
n,k=map(int, input().split())
a=np.array(list(map(int, input().split())))
b=np.maximum(a,0)
sm=sum(a[:k])
at=sum(b[k:])
ans=max(sm,0)+at
for i in range(k,n):
    sm+=a[i]-a[i-k]
    at+=b[i-k]-b[i]
    ans=max(max(0,sm)+at,ans)
print(ans)

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

cum = []
abscum = []

cu = 0
acu = 0
for i in range(n):
    cu += a[i]
    acu += max(0, a[i])
    cum.append(cu)
    abscum.append(acu)

ans = 0
for i in range(n-k+1):
    if i == 0:
        ans = max(ans, abscum[n-1] - abscum[i+k-1] + max(0, cum[i+k-1]))
    else:
        ans = max(ans, abscum[n - 1] - (abscum[i + k - 1] - abscum[i-1]) + max(0, cum[i + k - 1] - cum[i-1]))

print(ans)

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

cums = [0]
cump = [0]
for a in A:
    cums.append(cums[-1] + a)
    cump.append(cump[-1] + max(0,a))

ans = 0
for i in range(N-K+1):
    tmp = cump[i] + cump[-1] - cump[i+K]
    tmp += max(0, cums[i+K] - cums[i])
    ans = max(ans, tmp)
print(ans)

Solution (Python):
n, k = map(int, input().split())
a = [int(m) for m in input().split()]
sum = 0
for i in range(n):
    if a[i] > 0:
        sum += a[i]

sei = 0
fu = 0
for i in range(k):
    if a[i] > 0:
        sei += a[i]
    else:
        fu += a[i]
zen = sei + fu
ansli = []
if zen > 0:
    ansli.append(sum + fu)
else:
    ansli.append(sum - sei)
for i in range(k, n):
    if a[i] > 0:
        sei += a[i]
    else:
        fu += a[i]
    if a[i - k] > 0:
        sei -= a[i - k]
    else:
        fu -= a[i - k]
    zen = sei + fu
    if zen > 0:
        ansli.append(sum + fu)
    else:
        ansli.append(sum - sei)
print(max(ansli))

Solution (Python):
from itertools import accumulate

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

b_list = []
for a in a_list:
    if a > 0:
        b_list.append(a)
    else:
        b_list.append(0)
b_list = list(accumulate(b_list))
a_acc = list(accumulate(a_list))

b_list.insert(0, 0)
b_list.append(b_list[-1])
a_acc.insert(0, 0)
ans = 0


for i in range(N - K + 1):

    ans = max(ans, b_list[i] + a_acc[i + K] - a_acc[i] + b_list[N] - b_list[i + K])
    ans = max(ans, b_list[i] + b_list[N] - b_list[i + K])
print(ans)

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

cums = [0]
cums_p = [0]
for a in A:
    cums.append(cums[-1] + a)
    cums_p.append(cums_p[-1] + max(0,a))

ans = -float('inf')
for l in range(N-K+1):
    free = cums_p[l] + cums_p[-1] - cums_p[l+K]
    cont = cums[l+K] - cums[l]
    ans = max(ans, free, free+cont)
print(ans)

Solution (Python):
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
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())

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

acc_all = [0]
acc_pos = [0]

for ai in a:
    if ai > 0:
        acc_all.append(acc_all[-1] + ai)
        acc_pos.append(acc_pos[-1] + ai)
    else:
        acc_all.append(acc_all[-1] + ai)
        acc_pos.append(acc_pos[-1])

ans = 0    
for st in range(n-k+1):
    black = (acc_all[st+k] - acc_all[st])\
            + (acc_pos[n] - acc_pos[st+k])\
            + (acc_pos[st] - acc_pos[0])
    white = (acc_pos[n] - acc_pos[st+k])\
            + (acc_pos[st] - acc_pos[0])

    ans = max(ans, black, white)
    
print(ans)

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

M1=0
for i in range(N):
    if a[i]>=0:
        M1+=a[i]
        
s=0
for i in range(K):
    s+=max(0,a[i])
m1=s
for i in range(N-K):
    s=s+max(0,a[K+i])-max(0,a[i])
    if m1>s:
        m1=s

s=0

for i in range(K):
    s+=min(0,a[i])
m2=s
for i in range(N-K):
    s=s+min(0,a[K+i])-min(0,a[i])
    if m2<s:
        m2=s
print(max(M1-m1,M1+m2))

Solution (Python):
import itertools
N, K = [int(_) for _ in input().split()]
A = [0] + [int(_) for _ in input().split()]

cumsum_p = list(
    itertools.accumulate([A[i] if A[i] > 0 else 0 for i in range(N + 1)]))
cumsum_m = list(
    itertools.accumulate([A[i] if A[i] < 0 else 0 for i in range(N + 1)]))
ans = -float('inf')
for i in range(N - K + 1):
    ans = max(ans, -(cumsum_p[i + K] - cumsum_p[i]),
              cumsum_m[i + K] - cumsum_m[i])
ans += cumsum_p[-1]
print(ans)

Solution (Python):
N,K=map(int,input().split())
A=[int(i) for i in input().split()]
P=[0]*(N+1)
T=[0]*(N+1)
for i in range(N):
    P[i+1]=P[i]+A[i]
    if A[i]>=0:
        T[i+1]=T[i]+A[i]
    else:
        T[i+1]=T[i]
a=max(sum(A),0)
for i in range(K,N+1):
    t=P[i]-P[i-K]
    s=T[i-K]-T[0]
    u=T[N]-T[i]
    a=max(a,s+t+u,s+u)
    
print(a)

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[-1]+a[i])
    if a[i] > 0:
        c.append(c[-1]+a[i])
    else:
        c.append(c[-1])


res = 0
for i in range(n-k+1):
    if b[i+k]-b[i] > 0:
        w = b[i+k]-b[i] + (c[i]-c[0]) + (c[n]-c[i+k])
    else:
        w = c[i]-c[0]+c[n]-c[i+k]
    res = max(res,w)
print(res)

Solution (Python):
n,k = map(int,input().split())
a = list(map(int,input().split()))
rui = [0]*(n+1)
wa = 0
for i in range(n):
  rui[i+1] = rui[i] + a[i]
pura = 0
for i in range(n-k):
  if a[i] >0:
    pura += a[i]
for i in range(n-k,-1,-1):
  wa = max(pura+rui[i+k]-rui[i],pura,wa)
  if a[i-1] >0:
    pura -= a[i-1]
  if a[i+k-1]>0:
    pura += a[i+k-1]
print(wa)

Solution (Python):
N,K=map(int,input().split())
a=[int(i) for i in input().split()]
S=[0]
p=[0]


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

ans=0
for i in range(1,N-K+2):
  res=0
  res+=max(S[i+K-1]-S[i-1],0)
  res+=p[i-1]
  res+=p[-1]-p[i+K-1]
  ans=max(res,ans)
print(ans)

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

Plus, Whole = [0], [0]
for i in range(N):
    Plus.append(Plus[-1] + max(A[i], 0))
    Whole.append(Whole[-1] + A[i])

Score = max(max(0, Whole[K] - Whole[0]) + Plus[N] - Plus[K], Plus[N-K] - Plus[0] + max(0, Whole[N] - Whole[N-K]))
for i in range(1, N-K):
    temp = Plus[i] + max(0, Whole[i+K] - Whole[i]) + Plus[N] - Plus[i+K]
    Score = max(Score, temp)

print(Score)

Solution (Python):
def inpl(): return [int(i) for i in input().split()]

N, K = inpl()
a = inpl()
b = [i if i>0 else 0 for i in a ]
c = [i if i<0 else 0 for i in a ]
d = [0 for _ in range(N-K+1)]
d[0] = sum(c[:K])
e = [0 for _ in range(N-K+1)]
e[0] = sum(b[:K])
for i in range(N-K):
    d[i+1] = d[i] - c[i] + c[i+K]
    e[i+1] = e[i] - b[i] + b[i+K]
print(max(0, sum(b)+max(d), sum(b)-min(e)))

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

a = list(map(int, input().split()))
a_plus = [max(a[i], 0) for i in range(n)]

a_sum = [0]
a_plus_sum = [0]

for i in range(n):
    a_sum.append(a_sum[-1] + a[i])
    a_plus_sum.append(a_plus_sum[-1] + a_plus[i])

best = -1
best_lost = 10**16
for i in range(k, n+1):
    temp_lost = (a_plus_sum[i] - a_plus_sum[i-k]) - max((a_sum[i] - a_sum[i-k]), 0)
    if best_lost >  temp_lost:
        best_lost = temp_lost
        best = i
        
ans = a_plus_sum[n] - best_lost
print(max(ans, 0))

Solution (Python):

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

acc_a = []
acc_b = []
acc_a.append(0)
acc_b.append(0)

for i in range(n):
    acc_a.append(a[i]+acc_a[-1])
    acc_b.append(max(0,a[i]) + acc_b[-1])

ans = 0
for i in range(n-k+1):
    t = acc_a[i+k] - acc_a[i]
    t += acc_b[i] - acc_b[0]
    t += acc_b[n] - acc_b[i+k]
    ans = max(ans,t)

    t = 0
    t += acc_b[i] - acc_b[0]
    t += acc_b[n] - acc_b[i+k]
    ans = max(ans,t)
print(ans)

Solution (Python):
N, K = map(int, input().split())
As = list(map(int, input().split())) + [0]

sumRest = sum([A for A in As[K:] if A > 0])
sumPlus = sumMinus = 0
for A in As[:K]:
    if A > 0:
        sumPlus += A
    else:
        sumMinus += A

ans = 0
for i in range(N - K + 1):
    score = sumRest + max(sumPlus + sumMinus, 0)
    ans = max(ans, score)

    if As[i + K] > 0:
        sumRest -= As[i + K]
        sumPlus += As[i + K]
    else:
        sumMinus += As[i + K]

    if As[i] > 0:
        sumRest += As[i]
        sumPlus -= As[i]
    else:
        sumMinus -= As[i]

print(ans)

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




CumS = [0] * (N+1)
CumSPos = [0] * (N+1)

for i in range(N):
  CumS[i+1] = CumS[i] + A[i]
  CumSPos[i+1] = CumSPos[i] + (A[i] if A[i] > 0 else 0)

ans = (-1) * float("inf")

for i in range(1,N+1): 
  if i+K-1 > N:
    break
  work = 0
  work += CumSPos[i-1] 
  work += max(CumS[i+K-1] - CumS[i-1], 0) 
  work += CumSPos[N] - CumSPos[i+K-1]  
  ans = max(ans, work)
  
  
print(ans)

Solution (Python):
n,k = map(int,input().split())
lis = list(map(int,input().split()))
num = 0
ans = 0
cou = 0
co = 0
for i in range(n):num += max(0,lis[i])
li = [0 for i in range(n-k+1)]
for i in range(k-1):
  cou += max(0,lis[i])
  co += max(0,-lis[i])
for i in range(n-k+1):
  cou += max(0,lis[i+k-1])
  co += max(0,-lis[i+k-1])
  if cou >= co:ans = max(ans,num-co)
  else:ans = max(ans,num-cou)
  cou -= max(0,lis[i])
  co -= max(0,-lis[i])
print(ans)

Solution (Python):
ai = lambda: list(map(int,input().split()))

n,k = ai()
a = ai()

sa = [0]
for i in range(n):
    sa.append(sa[-1]+a[i])

spa = [0]
for i in range(n):
    spa.append(spa[-1]+max(a[i], 0))

ans = -float('inf')
for i in range(n-k+1):
    ans = max(ans, max(0, sa[i+k]-sa[i]) + spa[i] + (spa[n]-spa[i+k]))
print(ans)

Solution (Python):
n, k = map(int, input().split())
a = list(map(int, input().split()))
sum_a = [0]
for ai in a:
    sum_a.append(sum_a[-1] + (ai if ai > 0 else 0))
sum_sk = sum(a[:k])
ans = max(sum_sk + sum_a[n] - sum_a[k], sum_a[n] - sum_a[k])
for i in range(n - k):
    sum_sk = sum_sk - a[i] + a[i + k]
    ans = max(ans,
              sum_sk + sum_a[n] - (sum_a[i + k + 1] - sum_a[i + 1]),  
              sum_a[n] - (sum_a[i + k + 1] - sum_a[i + 1]))  
print(ans)

Solution (Python):
from itertools import accumulate as acc
N, K, *a = map(int, open(0).read().split())
*b, = map(lambda x: max(x, 0), a)
*Sa, = acc([0] + a)
*Sb, = acc([0] + b)
print(max(Sb[i] + max(0,Sa[i+K]-Sa[i]) + Sb[N]-Sb[i+K] for i in range(N-K+1)))

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

def li(): return [int(x) for x in stdin.readline().split()]
def li_(): return [int(x)-1 for x in stdin.readline().split()]
def lf(): return [float(x) for x in stdin.readline().split()]
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(ns())
def nf(): return float(ns())

from itertools import accumulate

n,k = li()
a = li()

a_cum = list(accumulate([0] + a))
a_pl = [ai if ai>0 else 0 for ai in a]
a_left = list(accumulate([0] + a_pl))
a_right = list(accumulate([0] + a_pl[::-1]))

ans = 0

for i in range(n-k+1):
    
    cand = a_cum[i+k] - a_cum[i]
    cand += (a_left[i] + a_right[n-(i+k)])
    ans = max(ans,cand)
    
    
    
    cand = 0
    cand += (a_left[i] + a_right[n-(i+k)])
    ans = max(ans,cand)
    
    
print(ans)

Solution (Python):
N,K=map(int,input().split())
a=[int(i) for i in input().split()]
b=[max([a[i],0]) for i in range(N)]
S=[0 for i in range(N+1)]
T=[0 for i in range(N+1)]
for i in range(N):
    S[i+1]=S[i]+a[i]
    T[i+1]=T[i]+b[i]
ans=0
for i in range(N-K+1):
    tmp=T[N]+S[i+K]-T[i+K]+T[i]-S[i]
    if ans<tmp:
        ans=tmp
for i in range(N-K+1):
    tmp=T[N]
    M=T[i+K]-T[i]
    tmp-=M
    if ans<tmp:
        ans=tmp
print(ans)

Solution (Python):
N,K=map(int,input().split())
a=[int(i) for i in input().split()]
b=[max([a[i],0]) for i in range(N)]
S=[0 for i in range(N+1)]
T=[0 for i in range(N+1)]
for i in range(N):
    S[i+1]=S[i]+a[i]
    T[i+1]=T[i]+b[i]
ans=-10**15
for i in range(N-K+1):
    tmp=T[N]+S[i+K]-T[i+K]+T[i]-S[i]
    if ans<tmp:
        ans=tmp
for i in range(N-K+1):
    tmp=T[N]
    M=T[i+K]-T[i]
    tmp-=M
    if ans<tmp:
        ans=tmp
print(ans)

Solution (Python):
n, k = map(int, input().split())
a = list(map(int, input().split()))
cumsum = [0]
cumsum_pos = [0]
for i in range(n):
	cumsum.append(cumsum[-1] + a[i])
	cumsum_pos.append(cumsum_pos[-1] + max(0, a[i]))
def range_sum(l, r):
	if l > r:
		return 0
	else:
		return cumsum[r + 1] - cumsum[l]
def range_pos(l, r):
	if l > r:
		return 0
	else:
		return cumsum_pos[r + 1] - cumsum_pos[l]

ans = -float("inf")

for i in range(n - k + 1):
	ans = max(ans, range_sum(i, i + k - 1) + range_pos(0, i - 1) + range_pos(i + k, n - 1), range_pos(0, i - 1) + range_pos(i + k, n - 1))

print(ans)

Solution (Python):
from itertools import accumulate as ac
n,k=map(int,input().split())
*l,=map(int,input().split())
*m,=map(lambda x:max(x,0),l)
*acc,=ac([0]+l)
*acm,=ac([0]+m)
v=0
for i in range(n-k+1):
  v=max(v,max(0,acc[i+k]-acc[i])+acm[n]-acm[i+k]+acm[i])
print(v)

Solution (Python):
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())

N,K = inpl()
aa  = inpl()

SUM_aa = [0]
ABS_aa = [0]
tmp1 = tmp2 = 0
for a in aa:
	tmp1 += a
	tmp2 += max(a,0)
	SUM_aa.append(tmp1)
	ABS_aa.append(tmp2)

SUM = ABS_aa[N]
ans = 0
for i in range(N-K+1):
	left = ABS_aa[i]
	right = SUM - ABS_aa[i+K]
	mid = SUM_aa[i+K]-SUM_aa[i]
	ans = max(ans,left+right+max(0,mid))

print(ans)

Solution (Python):

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(10000)


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, A):

    sa = [0]
    sa0 = [0]
    for a in A:
        sa.append(sa[-1]+a)
        sa0.append(sa0[-1]+max(0, a))

    ans = 0
    for i in range(N-K+1):
        l = sa0[i]
        r = sa0[-1] - sa0[i+K]
        c = sa[i+K] - sa[i]
        ans = max(ans, l + r)
        ans = max(ans, l + c + r)

    return ans


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


if __name__ == '__main__':
    main()

Solution (Python):

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(10000)


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, A):

    sa = [0]
    sa0 = [0]
    for a in A:
        sa.append(sa[-1]+a)
        sa0.append(sa0[-1]+max(0, a))

    ans = 0
    for i in range(N-K+1):
        l = sa0[i]
        r = sa0[-1] - sa0[i+K]
        c = sa[i+K] - sa[i]
        ans = max(ans, l + r)
        ans = max(ans, l + c + r)

    return ans


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


if __name__ == '__main__':
    main()

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

    sa, sb = [0 for i in range(n+1)], [0 for i in range(n+1)]
    for i in range(1, n+1):
        sa[i] = sa[i-1] + a[i-1]
        sb[i] = sb[i-1] + max(0, a[i-1])

    ans = 0
    for i in range(n-k+1):
        ss = sb[i] + sb[n] - sb[i+k]
        s1 = sa[i+k] - sa[i] + ss
        ans = max(ans, s1, ss)

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
n,k=map(int,input().split())
a=[0]+list(map(int,input().split()))
s=[0]
p=[0]
for i in range(1,n+1):
  s.append(s[i-1]+a[i])
  p.append(p[i-1]+max(0,a[i]))
ans=0
for i in range(1,n-k+2):
  t=max(0,s[i+k-1]-s[i-1])
  t+=p[i-1]+p[n]-p[i+k-1]
  ans=max(ans,t)
print(ans)

Solution (Python):
n,k=map(int,input().split())
a=[0]+list(map(int,input().split()))
s=[0]
p=[0]
for i in range(1,n+1):
  s.append(s[i-1]+a[i])
  p.append(p[i-1]+max(0,a[i]))
ans=0
for i in range(1,n-k+2):
  t=max(0,s[i+k-1]-s[i-1])
  t+=p[i-1]+p[n]-p[i+k-1]
  ans=max(ans,t)
print(ans)

Solution (Python):
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import *
from bisect import bisect
 
def read():
  return int(input())
 
def reads():
  return [int(x) for x in input().split()]

N, K = reads()
a = reads()

ppsum = [0] * (N+1)
psum = [0] * (N+1)

for i in range(N):
  ppsum[i+1] = ppsum[i] + max(0, a[i])
  psum[i+1] = psum[i] + a[i]

ansb = max(ppsum[i] + psum[i+K] - psum[i] + ppsum[N] - ppsum[i+K] for i in range(N-K+1))
answ = max(ppsum[i] + ppsum[N] - ppsum[i+K] for i in range(N-K+1))

print(max(ansb, answ))

Solution (Python):
N, K = map(int, input().split())
A = list(map(int, input().split()))
b = sum([i for i in A[:K] if i <= 0])
bMax = b
w = sum([i for i in A[:K] if i >= 0])
wMin = w
for i in range(N-K):
    b = b - min(A[i], 0) + min(A[K+i], 0)
    w = w - max(A[i], 0) + max(A[K+i], 0)
    bMax = max(bMax, b)
    wMin = min(wMin, w)
print(sum(i for i in A if i >= 0) + max(bMax, -wMin))

Solution (Python):
n,k = (int(i) for i in input().split())
a = [int(i) for i in input().split()]
x,y,ans = [0],[0],0
for i in range(n):
	x.append(x[-1]+a[i])
	y.append(y[-1]+max(0,a[i]))
for i in range(1,n-k+2):
	num,num2 = y[i-1]+y[n]-y[i+k-1],x[i+k-1]-x[i-1]
	ans = max(ans,num,num+num2)
print(ans)