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 = [int(_) for _ in input().split()]
A = [int(_) for _ in input().split()]

w = sum(x for x in A[K:] if x > 0)
b = sum(A[:K]) + w

result = max(w, b)

for i in range(N - K):
    j = i + K
    Ai = A[i]
    Aj = A[j]
    if Ai > 0:
        w += Ai
    if Ai < 0:
        b -= Ai
    if Aj > 0:
        w -= Aj
    if Aj < 0:
        b += Aj
    result = max(result, w, b)

print(result)

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







pl=0
ma=0
re=0


for i in range(K):
  if A[i] >= 0:
    pl+=A[i]
  else:
    ma+=(-A[i])
re=min(pl,ma)

for i in range(1,N-K+1):
  if A[i-1] >= 0:
    pl-=A[i-1]
  else:
    ma+=A[i-1]
  if A[i+K-1]>=0:
    pl+=A[i+K-1]
  else:
    ma+=(-A[i+K-1])
  if min(pl,ma) < re:
    re=min(pl,ma)
    


ans=0
for i in range(N):
  ans+=max(0,A[i])
    
print(ans-re)

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

if N == K:
    print(max(sum(a), 0))
    exit()

a_plus = []
a_minus = []
for i in range(N):
    if i == 0:
        if a[i] > 0:
            a_plus.append(a[i])
            a_minus.append(0)
        else:
            a_plus.append(0)
            a_minus.append(a[i])
    else:
        if a[i] > 0:
            a_plus.append(a_plus[i-1] + a[i])
            a_minus.append(a_minus[i-1])
        else:
            a_plus.append(a_plus[i-1])
            a_minus.append(a_minus[i-1] + a[i])

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

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

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

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

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

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

ans = 0
for left in range(N-K+1):
    right = left + K

    
    score = max(0, cumsum[right] - cumsum[left])
    
    score += cummaxsum[left]
    
    score += cummaxsum[-1] - cummaxsum[right]

    ans = max(ans, score)

print(ans)

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

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

ans = -float('inf')
for l in range(N-K+1):
    r = l + K
    tmp = p_cums[l]
    tmp += max(0, cums[r] - cums[l])
    tmp += p_cums[-1] - p_cums[r]
    ans = max(ans, tmp)
print(ans)

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

white_start, black_start = 0, 0
white_sum, black_sum = 0, 0
for i in range(K):
  white_sum += max(-a[i],0)
  black_sum += max(a[i],0)
curr_white = white_sum
curr_black = black_sum

for i in range(N-K):
  curr_white += max(-a[i+K],0) - max(-a[i],0)
  curr_black += max(+a[i+K],0) - max(+a[i],0)
  if curr_white < white_sum :
    white_sum = curr_white
    white_start = i+1
  if curr_black < black_sum :
    black_sum = curr_black
    black_start = i+1
ans = 0
if white_sum < black_sum:
  for i in range(N):
    if i < white_start or i >= white_start+K:
      ans += max(a[i],0)
    else: ans+=a[i]
  print(ans)
else:
  for i in range(N):
    if i < black_start or i >= black_start+K:
      ans += max(a[i],0)
  print(ans)

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
if any((x > 0 for x in a)):
    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):

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

pl = [(x if (x > 0) else 0) for x in a]
s = sum(pl)
sk_a = [sum(a[:K])]
sk_pl = [sum(pl[:K])]
for i in range(1, N - K + 1):
    sk_a.append(sk_a[-1] - a[i - 1] + a[K + i - 1])
    sk_pl.append(sk_pl[-1] - pl[i - 1] + pl[K + i - 1])

ans = 0
if lambda x: x > 0 in a:
    for i in range(N - K + 1):
        ans = max(ans, s - sk_pl[i] + max(0, sk_a[i]))

print(ans)

Solution (Python):
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
INF = float("inf")


class CumulativeSum:
    def __init__(self, l):
        self.dp = [0] * (len(l) + 1)
        for i, v in enumerate(l):
            self.dp[i + 1] = v + self.dp[i]

    
    def total(self, left, right):
        assert 0 <= left <= right < len(self.dp)
        return self.dp[right + 1] - self.dp[left]


def main():
    N, K = map(int, input().split())
    a_list = list(map(int, input().split()))
    b_list = [max(0, a) for a in a_list]

    cs_a = CumulativeSum(a_list)
    cs_b = CumulativeSum(b_list)

    ans = -INF
    total = sum(b_list)
    for i in range(N - K + 1):
        a = max(0, cs_a.total(i, i + K - 1))
        rest = total - cs_b.total(i, i + K - 1)
        ans = max(ans, rest + a)
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):


n,k=map(int,raw_input().split())
a=map(int,raw_input().split())
w=[0 for i in xrange(n+1)]
b=[0 for i in xrange(n+1)]

for i in xrange(n):
 w[i+1]=w[i]+a[i]
 b[i+1]=b[i]+max(0,a[i])

res=0
for i in xrange(n-k+1):
 x=(b[i]-b[0])+(b[n]-b[i+k])
 y=x+(w[i+k]-w[i])
 res=max(res,x,y)

print res

Solution (Python):
n,k=map(int,raw_input().split())
a=map(int,raw_input().split())
s1=[0]*n
s1[0]=a[0]
s2=[0]*n
if a[0]>0:
    s2[0]=a[0]
for i in xrange(1,n):
    s1[i]+=s1[i-1]+a[i]
    s2[i]+=s2[i-1]
    if a[i]>0:
        s2[i]+=a[i]
ans=-float("inf")
for i in xrange(n-k+1):
    if i==0:
        tmp1=s1[i+k-1]
        tmp2=s2[n-1]-s2[i+k-1]
    else:
        tmp1=s1[i+k-1]-s1[i-1]
        tmp2=s2[n-1]-(s2[i+k-1]-s2[i-1])
    ans=max(ans,tmp1+tmp2,tmp2)
print ans

Solution (Python):



def readln(ch):
    _res = list(map(int,str(input()).split(ch)))
    return _res

s = readln(' ')
n,k = s[0],s[1]
a = [0 for i in range(0,n+1)]
a[1:] = readln(' ')
s = a[:]
r = a[:]
for i in range(1,n+1):
    s[i] = s[i-1] + s[i]
    if r[i] > 0:
        r[i] = r[i-1] + r[i]
    else:
        r[i] = r[i-1]

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

print(ans)

Solution (Python):
N, K = map(int, input().split())
A = [int(i) for i in input().split()]
a = 0
for i in range(N):
	if A[i] > 0:
		a += A[i]
p = sum([i for i in A[:K] if i > 0])
m = sum([i for i in A[:K] if i < 0])
ans = max(a+m,a-p)
for i in range(N-K):
	p = p - max(0,A[i]) + max(0,A[i+K])
	m = m - min(0,A[i]) + min(0,A[i+K])
	ans = max(ans, a-p, a+m)
print(ans)

Solution (Python):
n, k = map(int, raw_input().strip().split())
a = map(int, raw_input().strip().split())

sum_k = [0] * (n - k + 1)
pos_k = [0] * (n - k + 1)

pos_all = reduce(lambda x, y: x + y if y > 0 else x, a)

sum_k[0] = sum(a[:k])
pos_k[0] = reduce(lambda x, y: x + y if y > 0 else x, a[:k])

for i in range(1, n - k + 1):
	sum_k[i] = sum_k[i - 1] + a[i + k - 1] - a[i - 1]
	pos_k[i] = pos_k[i - 1] + (a[i + k - 1] if a[i + k - 1] > 0 else 0) - (a[i - 1] if a[i - 1] > 0 else 0)

result = 0

for i in range(n - k + 1):
	t = pos_all - pos_k[i] + (sum_k[i] if sum_k[i] > 0 else 0)
	if result < t:
		result = t

print result

Solution (Python):
import numpy as np

n, k = map(int, input().split())
xs = np.array([0] + list(map(int, input().split())))

ps = np.clip(xs, 0, np.inf).astype(np.int64)
ns = -np.clip(xs, -np.inf, 0).astype(np.int64)
ps_cumsum = np.cumsum(ps)
ns_cumsum = np.cumsum(ns)

compromise = min(min(ps_cumsum[i+k]-ps_cumsum[i] for i in range(n-k+1)), min(ns_cumsum[i+k]-ns_cumsum[i] for i in range(n-k+1)))
print(ps_cumsum[-1] - compromise)

Solution (Python):
n, k = map(int, raw_input().split())
A = map(int, raw_input().split())
B = [0]*(n+1)
C = [0]*(n+1)
for i in xrange(n):
    B[i+1] = B[i] + A[i]
    C[i+1] = C[i] + A[i]*(A[i] > 0)
print max(C[i] + C[n]-C[i+k] + max(B[i+k]-B[i], 0) for i in xrange(n-k+1))

Solution (Python):
n,k=map(int,input().split())
arr=list(map(int,input().split()))
brr=list(map(lambda x: max(x,0),arr))
crr=[0]
cum=0
for b in brr[:(n-k)]:
    cum+=b
    crr.append(cum)
drr=[0]
cum=0
for b in list(reversed(brr))[:(n-k)]:
    cum+=b
    drr.append(cum)
drr.reverse()
K=sum(arr[:k])
krr=[]
for i in range(n-k):
    krr.append(max(0,K))
    K-=arr[i]
    K+=arr[i+k]
krr.append(max(0,K))

ans=0
for i in range(n-k+1):
    ans=max(ans,crr[i]+drr[i]+krr[i])
print(ans)

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


if N == K:
	print(max(0, sum(a)))
else:
	imosW = [0]*(N+2)
	imosB = [0]*(N+2)
	for i in range(1, N+1):
		imosW[i] = max(0, a[i]) + imosW[i-1]
		imosB[i] = min(0, a[i]) + imosB[i-1]

	sepW = -1
	mini = int(1e18)
	for i in range(K, N + 1):
		if mini > imosW[i] - imosW[i-K]:
			mini = imosW[i] - imosW[i-K]
			sepW = (i-K, i)

	ansW = 0
	for i in range(1, N+1):
		if a[i] > 0 and not(i > sepW[0] and i <= sepW[1]):
			ansW += a[i]

	
	sepB = -1
	maxm = int(-1e18)
	for i in range(K, N+1):
		if maxm < imosB[i] - imosB[i-K]:
			maxm = imosB[i] - imosB[i-K]
			sepB = (i-K, i)
	ansB = (imosB[sepB[1]] - imosB[sepB[0]]) + (imosW[sepB[1]] - imosW[sepB[0]])
	for i in range(1, N+1):
		if a[i] > 0 and not(i > sepB[0] and i <= sepB[1]):
			ansB += a[i]

	print(max(max(ansW, ansB), sum(a)))

Solution (Python):
N, K = map(int, input().split())
A = list(map(int, input().split()))
k = 0
for i in range(N-K+1):
	if i>0:
		K_sum = K_sum-A[i-1]+A[i+K-1]
		K_sum0 = max(0, K_sum)
		K_pos = K_pos-max(0, A[i-1])+max(0, A[i+K-1])
	else:
		K_sum = sum(A[i:i+K])
		K_sum0 = max(0, K_sum)
		K_pos = sum(map(lambda x:max(0, x), A[i:i+K]))
	loss = K_pos-K_sum0
	if i==0:
		loss_min = loss
	if loss<loss_min:
		k = i
		loss_min = loss
K_sum_result = max(0, sum(A[k:k+K]))
result = K_sum_result + sum(map(lambda x:max(0, x), A[:k]+A[k+K:]))
print(result)

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



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

ans = 0

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

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):
    if a[i] > 0:
        p[i + 1] = p[i] + a[i]
        m[i + 1] = m[i]
    else:
        p[i + 1] = p[i]
        m[i + 1] = m[i] + a[i]

pmin = p[k] - p[0]
mmax = m[k] - m[0]

for i in range(1, n - k + 1):
    pmin = min(pmin, p[i + k] - p[i])
    mmax = max(mmax, m[i + k] - m[i])

ans = p[n] - min(pmin, -mmax)

print(ans)

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

a.insert(0, 0)
s = [0] * (n+1)
c = [0] * (n+1)

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

res = 0
for i in range(1, n-k+2):
    res = max(res, c[i-1] + max(0, s[i+k-1]-s[i-1]) + c[n] - c[i+k-1])

print(res)

Solution (Python):
n,k=map(int,raw_input().split())
a=map(int,raw_input().split())
total=[0]*(n+1)
asum=[0]*(n+1)
for i in xrange(n):
    asum[i+1]=asum[i]+a[i]
    if a[i]>0:
        total[i+1]=total[i]+a[i]
    else:
        total[i+1]=total[i]
ans=0
for i in xrange(n-k+1):
    tmp=asum[i+k]-asum[i]
    ans=max(ans,tmp+total[i]+total[n]-total[i+k],total[i]+total[n]-total[i+k])

print(ans)

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



b = []
w = []
riso = []

risonow = sum([a[i] for i in range(K) if a[i]>0])
riso.append(risonow)
bnow = sum([-a[i] for i in range(K) if a[i]<0])
b.append(bnow)

for i in range(K,N):
	if a[i]>0:
		risonow+=a[i]
	else:
		bnow+=-a[i]
	if a[i-K]>0:
		risonow-=a[i-K]
	else:
		bnow-=-a[i-K]
	riso.append(risonow)
	b.append(bnow)

riso.extend(b)
print(sum([i for i in a if i>0])-min(riso))

Solution (Python):
from collections import deque

n, k = map(int, input().split())
a = list(map(int, input().split()))
q = deque(a[:k])
plus = cur_plus = min_plus = sum(x for x in q if x > 0)
cur_minus = max_minus = sum(q) - plus
for b in a[k:]:
    c = q.popleft()
    q.append(b)
    if b > 0:
        plus += b
        cur_plus += b
    else:
        cur_minus += b
    if c > 0:
        cur_plus -= c
    else:
        cur_minus -= c
    max_minus = max(max_minus, cur_minus)
    min_plus = min(min_plus, cur_plus)
print(max(plus + max_minus, plus - min_plus))

Solution (Python):
import sys
if sys.version[0] == '2':
    range, input = xrange, raw_input
N, K = map(int, input().split())
A = [int(x) for x in input().split()]
accum = [[0, 0] for _ in range(N + 1)]
for i in range(N):
    accum[i+1][0] += accum[i][0] + A[i]
    accum[i+1][1] += accum[i][1] + max(A[i], 0)
ans = 0
for i in range(N-(K-1)):
    cand = accum[i+K][0] - accum[i][0] + accum[i][1] - accum[0][1] + accum[N][1] - accum[i+K][1]
    ans = max(ans, cand, accum[i][1] - accum[0][1] + accum[N][1] - accum[i+K][1])
print(ans)

Solution (Python):
n,k = map(int, input().split())
a = list(map(int, input().split()))
ideal = 0
imos_b = sum([v for v in a[0:k]])
imos_w = sum([v if v>0 else 0 for v in a[0:k]])
right_b = [0 for i in range(n-k+1)]
right_w = [0 for i in range(n-k+1)]
for i,v in enumerate(a):
    if v>0:
        ideal += v
    if i < n-k+1:
        right_b[i] = imos_b
        right_w[i] = imos_w
        imos_b -= a[i]
        imos_w -= a[i] if a[i]>0 else 0
    if i < n-k:
        imos_b += a[i+k]
        imos_w += a[i+k] if a[i+k]>0 else 0
max_score = sum(a)
for i in range(n-k+1):
    max_score = max(max_score, ideal+right_b[i]-right_w[i], ideal-right_w[i])
print(max_score)

Solution (Python):
from sys import stdin
def main():
    n, k = map(int, stdin.readline().split())
    a = map(int, stdin.readline().split())
    s = [0] * (n + 1)
    t = [0] * (n + 1)
    for i, x in enumerate(a):
        s[i+1] = s[i] + x
        t[i+1] = t[i] + (x if x > 0 else 0)
    ans = 0
    for i in xrange(n - k + 1):
        v = s[i+k] - s[i]
        if v < 0:
            v = 0
        v += t[i] + t[n] - t[i+k]
        if ans < v:
            ans = v
    print ans
main()

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7


def main():
    n,k = list(map(int, input().split()))
    a = list(map(int, input().split()))
    r = 0
    for c in a:
        if c > 0:
            r += c
    ps = 0
    ms = 0
    for c in a[:k]:
        if c > 0:
            ps += c
        else:
            ms -= c
    mi = min(ps,ms)
    for i in range(k,n):
        kc = a[i-k]
        if kc > 0:
            ps -= kc
        else:
            ms += kc
        c = a[i]
        if c > 0:
            ps += c
        else:
            ms -= c
        mi = min(mi,ps,ms)
    return r-mi


print(main())

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

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