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):
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
s = sum(A)
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)

Solution (Python):
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
a = list(map(int, input().split()))
cs = [0] * (N + 1)
for i in range(N): cs[i + 1] = cs[i] + a[i]
pa = [0] * N
for i in range(N): pa[i] = a[i] * (a[i] > 0)
csp = [0] * (N + 1)
for i in range(N): csp[i + 1] = csp[i] + pa[i]

res = 0
for i in range(N - K + 1):
  x = cs[i + K] - cs[i]
  y = csp[-1] - (csp[i + K] - csp[i])
  t = max(0, x) + y
  res = max(res, t)
print(res)

Solution (Python):
n, k = map(int, input().split())
A = list(map(int, input().split()))
S = sum(A[:k])
T = 0
for i in range(k, n):
  T += max(0, A[i])
ans = max(0, S) + T
for i in range(k, n):
  S -= A[i-k]
  S += A[i]
  T += max(0, A[i-k])
  T -= max(0, A[i])
  ans = max(ans, max(0, S)+T)
print(ans)

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

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

tmp = sum(A[:K])
ans = lst[N] - lst[K] + max(0, tmp)
for i in range(K, N):
    tmp += A[i] - A[i - K]
    next_ = (lst[N] - lst[i + 1]) + max(0, tmp) + lst[i - K + 1] - lst[0]

    ans = max(ans, next_)

print (ans)

Solution (Python):


import sys
from itertools import accumulate

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, K = MAP()
A = LIST()

B = [0] * N
for i, a in enumerate(A):
    if a > 0:
        B[i] = a

acc = [0] + list(accumulate(A))
acc2 = [0] + list(accumulate(B))
acc2rev = [0] + list(accumulate(B[::-1]))[::-1] + [0]

ans = -INF
for i in range(1, N-K+2):
    cnt = max(acc[i+K-1] - acc[i-1], 0)
    cnt += acc2[i-1] + acc2rev[i+K]
    ans = max(ans, cnt)
print(ans)

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

s = sum(A[:k])
t = 0
for i in range(k):
    t += max(A[i], 0)
a = min(t-s, t)
ai = 0
b = 1 if t > t-s else 0

for i in range(1, n-k+1):
    s -= A[i-1]
    s += A[i+k-1]
    t -= max(A[i-1], 0)
    t += max(A[i+k-1], 0)
    if a > t:
        a = t
        ai = i
        b = 0
    if a > t-s:
        a = t-s
        ai = i
        b = 1

ans = 0


for i in range(0, ai):
    ans += max(0, A[i])
for i in range(ai+k, n):
    ans += max(0, A[i])

if b > 0:
    ans += sum(A[ai:ai+k])

print(ans)

Solution (Python):
from itertools import accumulate
n,k = map(int,input().split())
a = list(map(int,input().split()))
suma = 0
for i in range(k,n):
  suma += max(0,a[i])
acca = [0]+list(accumulate(a))
ans = [max(suma,suma+acca[k])]
for i in range(1,n-k+1):
  suma += max(0,a[i-1])
  suma -= max(0,a[i+k-1])
  ans.append(max(suma,suma+acca[i+k]-acca[i]))
print(max(ans))

Solution (Python):
def examA():
    x, y = LI()
    ans = 0
    if x<0 and y<0:
        if x<=y:
            ans = y-x
        else:
            ans = x-y+2
    elif x<0 and 0<=y:
        if -x<=y:
            ans = y+x+1
        else:
            ans = min(-(x+y)+1,y-x)
    elif y<=0:
        ans = abs(y+x)+1
    else:
        if x<=y:
            ans = y-x
        else:
            ans = x-y+2
    print(ans)
    return

def examB():
    B, K = LI()
    A = LI()
    cumA = [0]*(B+1); negA = [0]*(B+1)
    for i,a in enumerate(A):
        cumA[i+1] = cumA[i]
        negA[i+1] = negA[i]
        if a>0:
            cumA[i+1] +=a
        else:
            negA[i+1] +=a
    ans = 0
    for i in range(B-K+1):
        curC = cumA[K+i]-cumA[i]; curN = negA[K+i]-negA[i]
        now1 = cumA[B] + curN
        now2 = cumA[B] - curC

        ans = max(ans,now1,now2)
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18

if __name__ == '__main__':
    examB()

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



import numpy as np

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

Aplus = np.maximum(A,0)


left = np.zeros(N-K+1,np.int64)
left[1:N-K+1] = Aplus[:N-K].cumsum()
right = np.zeros(N-K+1,np.int64)
right[0:N-K] = Aplus[::-1][:N-K].cumsum()[::-1]

Acum = np.cumsum(A)
mid = Acum[K-1:N] - Acum[0:N-K+1] + A[0:N-K+1]
mid = np.maximum(mid,0)

x = left + mid + right
answer = x.max()
print(answer)

Solution (Python):
from itertools import accumulate

N, K = map(int, input().split())
*A, = map(int, input().split())
acc = (0,) + tuple(accumulate(A))
acc_p = (0,) + tuple(accumulate(x if x > 0 else 0 for x in A))

ret = -10 ** 14
for i in range(N - (K - 1)):
    sum_ = acc[i + K] - acc[i]
    ret = max(ret, (acc_p[-1] - acc_p[i + K]) + acc_p[i] + (sum_ if sum_ > 0 else 0))

print(ret)

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

Solution (Python):
n,k=map(int,input().split())
a=list(map(int,input().split()))
b=[0]
c=[0]
for i in a:
  b.append(b[-1]+i)
  c.append(c[-1]+max(0,i))
ans=-float('inf')
for i in range(n-k+1):
  x=b[i+k]-b[i]
  y=c[n]-c[i+k]+c[i]
  ans=max(ans,y+max(0,x))
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n,k=map(int,input().split())
    A=list(map(int,input().split()))
    B=[max(a,0) for a in A] 
    S=[0]*(n+1)
    for i in range(n):
        S[i+1]=S[i]+A[i]

    T=[0]*(n+1)
    for i in range(n):
        T[i+1]=T[i]+B[i]

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

    print(ans)
resolve()

Solution (Python):
from itertools import accumulate
def main():
	n, k, *a = map(int, open(0).read().split())
	p = [x if x > 0 else 0 for x in a]
	acc = [0] + list(accumulate(a))
	p_acc = [0] + list(accumulate(p))
	rev_p_acc = [0] + list(accumulate(p[::-1]))
	print(max(max(0, acc[k + i] - acc[i]) + p_acc[i] + rev_p_acc[n - k - i] for i in range(n - k + 1)))
	
if __name__=="__main__":
	main()

Solution (Python):
from itertools import accumulate
n,k,*a=map(int,open(0).read().split())
p=[x if x>0 else 0 for x in a]
acc=[0]+list(accumulate(a))
p_acc=[0]+list(accumulate(p))
rev_p_acc=[0]+list(accumulate(p[::-1]))
print(max(max(0,acc[k+i]-acc[i])+p_acc[i]+rev_p_acc[n-k-i] for i in range(n-k+1)))

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

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

P = []
p = 0
for a in A:
    if a > 0:
        p += a
    P.append(p)

S = [0]
s = 0
for a in A:
    s += a
    S.append(s)

ans = 0
for i in range(N-K+1):
    others = 0
    if i != 0:
        others += P[i-1]
    others += P[-1] - P[i+K-1]
    ans = max(ans, others)
    ans = max(ans, others+(S[i+K]-S[i]))

print(ans)

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

s = [0] + a[::]
t = [0] + [a[i] if a[i] > 0 else 0 for i in range(N)]

for i in range(1, N + 1) :
    s[i] += s[i-1]
    t[i] += t[i-1]

ret = -float('inf')
for i in range(1, N - K + 2) :
    ret = max(ret, t[N] - t[i+K-1] + t[i-1] + max(0, s[i+K-1] - s[i-1]))
print(ret)

Solution (Python):

import sys
sys.setrecursionlimit(10000)
INF = 1<<48


def solve(N: int, K: int, a: "List[int]"):

    v = [0] * (N+1)
    for i in range(N):
        v[i+1] = v[i]+a[i]
    w = [0] * (N+1)
    for i in range(N):
        w[i+1] = w[i] + max(0, a[i])

    ans = -INF
    for i in range(0, N-K+1):
        tmp = w[N]
        tmp += max(v[i+K]-v[i], 0)
        tmp -= w[i+K]-w[i]
        
        ans = max(ans, tmp)

    
    print(ans)

    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    K = int(next(tokens))  
    a = [int(next(tokens)) for _ in range(N)]  
    solve(N, K, a)

if __name__ == '__main__':
    main()

Solution (Python):
def cumsum(inlist):
    s = 0
    outlist = []
    for i in inlist:
        s += i
        outlist.append(s)
    return outlist


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


cum_num, cum_num_2 = [0] + cumsum(num), [0] + cumsum(num_2)

ans = 0
for i in range(n-k+1):
    ansl = cum_num_2[i]
    ansm = cum_num[k+i] - cum_num[i]
    ansr = cum_num_2[n] - cum_num_2[i+k]
    ans = max(ansl+max(ansm,0)+ansr, ans)
print(ans)

Solution (Python):
from itertools import accumulate

def main():
    N, K, *A = map(int, open(0).read().split())

    M = [a if a < 0 else 0 for a in A]
    P = [a if a > 0 else 0 for a in A]

    MA = [0] + list(accumulate(M))
    PA = [0] + list(accumulate(P))

    minus = max(q - p for p, q in zip(MA, MA[K:]))
    plus = min(q - p for p, q in zip(PA, PA[K:]))

    print(sum(P) + max(minus, -plus))


if __name__ == '__main__':
    main()

Solution (Python):
from itertools import accumulate

N, K, *A = map(int, open(0).read().split())

M = [a if a < 0 else 0 for a in A]
P = [a if a > 0 else 0 for a in A]

MA = [0] + list(accumulate(M))
PA = [0] + list(accumulate(P))

minus = max(q - p for p, q in zip(MA, MA[K:]))
plus = min(q - p for p, q in zip(PA, PA[K:]))

print(sum(P) + max(minus, -plus))

Solution (Python):
N, K = [int(_) for _ in input().split()]
A = [int(_) for _ in input().split()]
B = [0] * N
max_a = 0
for i in range(N):
    if A[i] > 0:
        B[i] = A[i]
    if i > 0:
        B[i] += B[i - 1]

for i in range(1, N):
    A[i] += A[i - 1]

ans = -1e12
for i in range(N - K+1):
    x = A[i + K - 1] - (A[i - 1] if i > 0 else 0)
    y = B[-1] - (B[i + K - 1] - (B[i - 1] if i > 0 else 0))
    ans = max(y,y+x,ans)
print(ans)

Solution (Python):
N, K = map(int, input().split())
A = list(map(int, input().split()))
AS = [A[0]]
b = [max(A[0], 0)]
for i in range(N - 1):
    AS.append(AS[i] + A[i + 1])
    b.append(b[i] + max(A[i + 1], 0))
ans = -1
if N == 1 or N == K:
    ans = max(sum(A), 0)
for i in range(N - K):
    c = max(AS[i + K] - AS[i], 0)
    ans = max(ans, b[-1] - b[i + K] + b[i] + c)
print(ans)

Solution (Python):

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

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

psum = 0

for i in a:
    if i > 0:
        psum += i


nsum = 0

for i in range(K):
    nsum += a[i]

    if a[i] > 0:
        psum -= a[i]

ans = max( psum + nsum , psum )

for i in range(N - K):

    nsum -= a[i]
    if a[i] > 0:
        psum += a[i]

    nsum += a[K+i]
    if a[K+i] > 0:
        psum -= a[K+i]

    ans = max( ans , psum + nsum , psum )

print (ans)

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

Solution (Python):
def getlist():
	return list(map(int, input().split()))

con = 1000000007


def main():
	N, K = getlist()
	a = getlist()
	b = [0] * (N + 1)
	c = [0] * (N + 1)
	for i in range(1, N + 1):
		b[i] = b[i - 1] + a[i - 1]
		if a[i - 1] >= 0:
			c[i] = c[i - 1] + a[i - 1]
		else:
			c[i] = c[i - 1]

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



if __name__ == '__main__':
	main()

Solution (Python):

import sys
input = sys.stdin.readline
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7



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

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


O = [0] * (N+1)
for i in range(1, N+1):
    x = max(0, A[i-1])
    O[i] = O[i-1] + x




ans = 0
for i in range(N-K+1):
    l = i
    r = i+K-1

    
    sum_in = S[r+1] - S[l]

    
    if i == 0:
        sum_left = 0
    else:
        sum_left = O[l]-O[0]

    
    if r+1 < N:
        sum_right = O[N]-O[r+1]
    else:
        sum_right = 0

    
    tmp = 0
    tmp = max(tmp, sum_in+sum_left+sum_right)

    
    tmp = max(tmp, sum_in)

    
    tmp = max(tmp, sum_left+sum_right)

    ans = max(ans, tmp)




print(ans)

Solution (Python):
N,K = map(int,input().split())
A = list(map(int,input().split()))
Acu = [0]
Acu_p = [0]
for i in range(N):
  if i == 0:
    Acu.append(A[i])
  else:
    Acu.append(A[i]+Acu[-1])

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

ans = -float("inf")
for i in range(N-K+1):
  tmp = Acu_p[-1]
  tmp += max(Acu[i+K]-Acu[i],0)
  tmp -= Acu_p[i+K]-Acu_p[i]
  ans = max(ans,tmp)
print(ans)

Solution (Python):
N, K = map(int, input().split())
a = list(map(int, input().split()))
mae = 0
naka = sum(a[:K])
usiro = 0
for i in range(K, N):
    if a[i]>0:
        usiro+=a[i]
ans = max(mae+naka+usiro, mae+usiro)
for i in range(N-K):
    naka+=a[i+K]-a[i]
    if a[i]>0:
        mae+=a[i]
    if a[i+K]>0:
        usiro-=a[i+K]
    ans = max(ans, mae+naka+usiro, mae+usiro)
print(ans)

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

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

ans = 0
for i in range(N - K + 1):
    score = 0
    if i == 0:
        score += max(0, acum_a[K - 1])
    else:
        score += acum_b[i - 1]
        score += max(0, acum_a[i + K - 1] - acum_a[i - 1])
    score += acum_b[N - 1] - acum_b[i + K - 1]
    ans = max(ans, score)
print(ans)

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

band = sum(a[:K])
other = 0
for i in range(K, N):
    other += max(0, a[i])
ans = max(band, 0) + other
for i in range(N - K):
    band -= a[i]
    band += a[K + i]
    other += max(a[i], 0)
    other -= max(a[K + i], 0)
    ans = max(ans, max(band, 0) + other)
print(ans)

Solution (Python):
N, K = map(int, input().split())
A = [int(x) for x in input().split()]
P = [a if a > 0 else 0 for a in A]
M = [a if a < 0 else 0 for a in A]
W = [sum(P[:K])] * (N - K + 1)
B = [sum(M[:K])] * (N - K + 1)
for i in range(N - K):
  W[i + 1] = W[i] + P[i + K] - P[i]
  B[i + 1] = B[i] + M[i + K] - M[i]
print(sum(P) - min(min(W), -max(B)))

Solution (Python):
N,K = map(int,input().split())
A = list(map(int,input().split()))
L,R,C = [0],[0],[sum(A[:K])]
for i in range(N):
    L.append(L[-1]+max(A[i],0))
    R.append(R[-1]+max(A[N-i-1],0))
for i in range(N-K):
    C.append(C[-1]+A[i+K]-A[i])
ans = 0
for i in range(N-K+1):
    ans = max(ans,L[i]+C[i]+R[N-K-i],L[i]+R[N-K-i])
print(ans)

Solution (Python):



import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,k = LI()
a = LI()
b = [0] + list(accumulate(a))
c = [max(0,a[i]) for i in range(n)]
c = [0] + list(accumulate(c))
ans = -inf
for i in range(n-k+1):
    tmp = max(b[i+k] - b[i],0)
    tmp += c[i] - c[0]
    tmp += c[-1] - c[i+k]
    ans = max(tmp,ans)
print(ans)

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

plus_a = [0] * n
minus_a = [0] * n
ans = 0
for i in range(n):
    if a[i] > 0:
        plus_a[i] = a[i]
    else:
        minus_a[i] = a[i]
    ans += plus_a[i]

ruiseki_plus = [0] * (n + 1)
ruiseki_minus = [0] * (n + 1)
for i in range(n):
    ruiseki_plus[i+1] = ruiseki_plus[i] + plus_a[i]
    ruiseki_minus[i+1] = ruiseki_minus[i] + minus_a[i]

min_decreasing = -float("inf")
for i in range(n-k+1):
    
    tmp_plus = ruiseki_plus[i+k] - ruiseki_plus[i]
    tmp_minus = ruiseki_minus[i+k] - ruiseki_minus[i]
    min_decreasing = max(min_decreasing, -tmp_plus, tmp_minus)

print(ans + min_decreasing)

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

plus_a = [0] * n
minus_a = [0] * n
ans = 0
for i in range(n):
    if a[i] > 0:
        plus_a[i] = a[i]
    else:
        minus_a[i] = a[i]
    ans += plus_a[i]

ruiseki_plus = [0] * (n + 1)
ruiseki_minus = [0] * (n + 1)
for i in range(n):
    ruiseki_plus[i+1] = ruiseki_plus[i] + plus_a[i]
    ruiseki_minus[i+1] = ruiseki_minus[i] + minus_a[i]

min_decreasing = -float("inf")
for i in range(n-k+1):
    
    tmp_plus = ruiseki_plus[i+k] - ruiseki_plus[i]
    tmp_minus = ruiseki_minus[i+k] - ruiseki_minus[i]
    min_decreasing = max(min_decreasing, -tmp_plus, tmp_minus)

print(ans + min_decreasing)

Solution (Python):
n,k = map(int,input().split())
a = list(map(int,input().split()))
sum_a = [0]
for x in a:
    sum_a.append(sum_a[-1]+x)

ans = 0
ideal_a = [0]
for x in a:
    ideal_a.append(ideal_a[-1]+max(0,x))

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

print(ans)

Solution (Python):
import sys
import heapq
from operator import itemgetter
from collections import deque, defaultdict
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

def sol():
    N, K = map(int, input().split())

    A = list(map(int, input().split()))
    sumPlus = [0] * (N + 1)
    sumA = [0] * (N + 1)

    for i, a in enumerate(A):
        sumA[i + 1] = sumA[i] + a
        if a > 0:
            sumPlus[i + 1] = sumPlus[i] + a
        else:
            sumPlus[i + 1] = sumPlus[i]

    ans = 0
    for left in range(N - K + 1):  
        leftSum = sumPlus[left]
        rightSum = sumPlus[N] - sumPlus[left + K]
        midSum = sumA[left + K] - sumA[left]

        if midSum > 0:
            ans = max(ans, leftSum + rightSum + midSum)
        else:
            ans = max(ans, leftSum + rightSum)

    print(ans)

sol()

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np




N,K = map(int,input().split())
A = np.array(input().split(), dtype=np.int64)

Acum = A.cumsum()
range_sum = Acum[K-1:] - Acum[:N-(K-1)] + A[:N-(K-1)]


Acum = A.cumsum()
range_sum = Acum[K-1:] - Acum[:N-(K-1)] + A[:N-(K-1)]
best = np.maximum(A,0)
best_cum = best.cumsum()
best_range_sum = best_cum[K-1:] - best_cum[:N-(K-1)] + best[:N-(K-1)]

min_loss = (best_range_sum - np.maximum(range_sum,0)).min()

answer = best.sum() - min_loss
print(answer)

Solution (Python):
import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
from math import *
from itertools import *

N, K = map(int, input().split())
a = list(map(int, input().split()))
f = [0] * (N+1)
for i in range(N):
    f[i+1] += f[i]+a[i]
g = [0] * (N+1)
for i in range(N):
    g[i+1] += g[i]+max(0, a[i])
ans = 0
for i in range(N-K+1):
    ans = max(ans, max(0, f[i+K]-f[i])+g[i]+g[N]-g[i+K])
print(ans)

Solution (Python):
from itertools import*;A=accumulate;N,K,*a=map(int,open(0).read().split());a=[0]+a;*c,=A(a);*d,=A(max(0,i)for i in a);print(max(d[i]+max(0,c[i+K]-c[i])+d[N]-d[i+K]for i in range(N-K+1)))

Solution (Python):
from numpy import*

def section_sum(numbers,separate):
    sep1=array(numbers[separate:],dtype=int)
    sep2=array(numbers[:-separate],dtype=int)
    sep3=sum(numbers[:separate])
    return [[0,i][i>0] for i in insert(sep3+cumsum(sep1-sep2),0,sep3)]

n,k,*a=map(int,open(0).read().split())
l=[]
b=[[0,i][i>0] for i in a]
c=cumsum(b)
d=cumsum(b[::-1])[::-1]

for s,t in enumerate(section_sum(a,k)):
    if s+k<n:
        l.append(t+[0,c[s-1]][s-1>=0]+d[s+k])
    else:
        l.append(t+[0,c[s-1]][s-1>=0])
print(int(max(l)))

Solution (Python):
import bisect
import heapq
import itertools
import math
import operator
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter, mul, add, xor

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N, K = list(map(int, sys.stdin.readline().split()))
A = list(map(int, sys.stdin.readline().split()))

A = np.array([0] + A, dtype=int)
B = A.copy()
B[A < 0] = 0

cs1 = A.cumsum()
cs2 = B.cumsum()

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

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

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

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

ans=[]
for i in range(n-k+1):
  x=L[i+k]-L[i]
  y=L2[n]-L2[i+k]+L2[i]
  ans.append(max(y,x+y))
print(max(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]

a=[0]+list(accumulate(a))
b=[0]+list(accumulate(b))
s=b[-1]

print(max([max(a[i+k]-a[i],0)+s-b[i+k]+b[i] for i in range(n-k+1)]))

Solution (Python):
def main():
    N, K = map(int, input().split())
    poscs = [0] * (N+1)
    A = list(map(int, input().split()))
    for i in range(N):
        poscs[i+1] = poscs[i] + max(A[i], 0)
    total = sum(A[:K])
    ans = 0
    for i in range(N-K+1):
        tmp = poscs[i] + max(total, 0) + (poscs[N] - poscs[i+K])
        ans = max(ans, tmp)
        if i+K < N:
            total -= A[i]
            total += A[i+K]
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):

import sys
def input(): return sys.stdin.readline().rstrip()
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt, ceil, floor
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
import heapq
INF = float("inf")
MOD = 10**9 + 7
sys.setrecursionlimit(10**7)

dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
def inside(y: int, x: int, H: int, W: int) -> bool: return 0 <= y < H and 0 <= x < W
def mi(): return map(int, input().split())
def ii(): return int(input())


N, K = mi()
As = list(mi())

c_m = [] 
c_p = [] 


c_m.append(0)
c_p.append(0)

for a in As:
  if a <= 0:
    c_m.append(c_m[-1] + a)
    c_p.append(c_p[-1])
  else:
    c_p.append(c_p[-1] + a)
    c_m.append(c_m[-1])


ans = -INF
for i in range(N-K+1): 
  
  tmpans = 0
  tmpans += max(0, c_m[i+K] - c_m[i] + c_p[i+K] - c_p[i])
  tmpans += c_p[i] + c_p[N] - c_p[i+K]
  ans = max(ans, tmpans)

print(ans)

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline())[:-1]
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)]

sys.setrecursionlimit(1000000)
mod = 1000000007


def A():
    n = I()
    b = LI()
    ans = []
    for j in range(n):
        for i in range(len(b))[::-1]:
            if b[i] == i+1:
                x = b.pop(i)
                ans.append(x)
                break
    if b:
        print(-1)
    else:
        print(*ans[::-1],sep = "\n")
    return


def B():
    n,a,b,c,d = LI()
    s = S()
    a -= 1
    b -= 1
    c -= 1
    d -= 1
    k = b
    while b < d:
        if s[b+1] == ".":
            b += 1
        else:
            if s[b+2] == "
                print("No")
                return
            b += 2
    b = k
    if c < d:
        while a < c:
            if s[a+1] == ".":
                a += 1
            else:
                if s[a+2] == "
                    print("No")
                    return
                a += 2
        print("Yes")
    else:
        for i in range(b-1,d):
            if s[i:i+3].count(".") == 3:
                print("Yes")
                return
        print("No")
    return


def C():
    n,a,b,c,d = LI()
    if abs(b-a) > (n-1)*d:
        print("NO")
        return
    if 2*c <= (n-1)*(d-c):
        print("YES")
        return
    mi = a-(n-1)*d
    m = c+d
    f = 1+(n-1)*(d-c)
    if f >= m:
        print("YES")
        return
    if (b-mi)%m < f:
        print("YES")
    else:
        print("NO")
    return


def D():
    s = S()
    n = len(s)
    ans = 0
    for i in range(n):
        if s[i] == "U":
            ans += n-i-1
            ans += 2*i
        else:
            ans += 2*(n-i-1)
            ans += i
    print(ans)
    return


def E():
    n = I()
    a = LI()
    a.sort()
    b = [a[i] for i in range(n)]
    for i in range(n-1):
        b[i+1] += b[i]
    for i in range(n-1)[::-1]:
        if a[i+1] > 2*b[i]:
            break
    else:
        print(n)
        return
    print(n-i-1)
    return


def F():
    n,k = LI()
    a = LI()
    b = [a[i] for i in range(n)]
    b.append(0)
    for i in range(n)[::-1]:
        b[i] += b[i+1]
    l = [0]*(n+1)
    for i in range(n):
        if a[i] > 0:
            l[i+1] += a[i]
        l[i+1] += l[i]

    r = [0]*(n+1)
    for i in range(n)[::-1]:
        if a[i] > 0:
            r[i] += a[i]
        r[i] += r[i+1]
    ans = -float("inf")
    for i in range(n-k+1):
        j = i+k
        ans = max(ans, l[i]+r[j]+max(0,b[i]-b[j]))
    print(ans)
    return


if __name__ == "__main__":
    F()

Solution (Python):
class cumulative_sum:
    def __init__(self,A):
        N = len(A)
        self.S = [0]*(N+1)
        for i in range(N):
            self.S[i+1] = self.S[i] + A[i]
    def get(self,i,j=None):
        if j==None:j=len(self.S)-1
        if j<=i:return 0
        return self.S[j]-self.S[i]

N,K = map(int,input().split())
*A, = map(int,input().split())
B = [max(0,a) for a in A]
SA = cumulative_sum(A)
SB = cumulative_sum(B)
ans = 0
for i in range(N-K+1):
    tmp = max(0,SA.get(i,i+K)) + SB.get(0,i) + SB.get(i+K)
    ans = max(ans,tmp)
print(ans)

Solution (Python):
class cumulative_sum:
    def __init__(self,A):
        N = len(A)
        self.S = [0]*(N+1)
        for i in range(N):
            self.S[i+1] = self.S[i] + A[i]
    def get(self,i,j=None):
        if j==None:j=len(self.S)-1
        if j<=i:return 0
        return self.S[j]-self.S[i]

N,K = map(int,input().split())
*A, = map(int,input().split())
B = [max(0,a) for a in A]
SA = cumulative_sum(A)
SB = cumulative_sum(B)
ans = 0
for i in range(N-K+1):
    tmp = max(0,SA.get(i,i+K)) + SB.get(0,i) + SB.get(i+K)
    ans = max(ans,tmp)
print(ans)

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

L = [0]*(N+2)
R = [0]*(N+2)
for i in range(1,N+1):
    L[i] = L[i-1]+max(0,A[i-1])
for i in range(N,0,-1):
    R[i] = R[i+1]+max(0,A[i-1])

ans = 0
S = sum(A[:K])
for i in range(N-K+1):
    ans = max(ans,L[i]+max(0,S)+R[i+K+1])
    S += -A[i] + A[(K+i)%N]
print(ans)

Solution (Python):
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())

n, k = li()
a = list(li())
INF = 10**18

cum_raw = [0]*(n+1)
cum_max = [0]*(n+1)

for i in range(n):
    cum_raw[i+1] = cum_raw[i] + a[i]
    cum_max[i+1] = cum_max[i] + (0 if a[i] < 0 else a[i])

ans = -INF

for i in range(n-k+1):
    white_zone = (cum_max[i] - cum_max[0]) + (cum_max[n] - cum_max[i+k])
    black_zone = (cum_raw[i+k] - cum_raw[i])
    ans = max(ans, white_zone)
    ans = max(ans, white_zone + black_zone)

print(ans)

Solution (Python):
N,K=map(int,input().split())
A=list(map(int,input().split()))
p=[0]*(N+1)
m=[0]*(N+1)
for i in range(N):
    p[i+1]=p[i]
    m[i+1]=m[i]
    if A[i]>0:
        p[i+1]+=A[i]
    elif A[i]<0:
        m[i+1]-=A[i]
a=10**15
for i in range(N-K+1):
    a=min(a,p[i+K]-p[i],m[i+K]-m[i])
print(p[N]-a)

Solution (Python):
from itertools import accumulate

N, K = map(int, input().split())
*A, = map(int, input().split())
A_pos = list(map(lambda x: max(x, 0), A))
A_pos_cumsum = [0] + list(accumulate(A_pos))
ans = -float('inf')
S = sum(A[0: K])
for i in range(N - K + 1):
    ans = max(ans, max(S, 0) + A_pos_cumsum[i] + (A_pos_cumsum[-1] - A_pos_cumsum[i+K]))
    S = S - A[i] + A[i+K] if i < N - K else 0
print(ans)