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



Sample input:
5 3
-10 10 -10 10 -10


Sample output:
10

Submission status: Wrong Answer

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

cont_sum = -float("inf")
cont_index = None
for i in range(n - k + 1):
	if range_sum(i, i + k - 1) > cont_sum:
		cont_index = i
		cont_sum = range_sum(i, i + k - 1)

ans_pos = 0
for i in range(n):
	if cont_index <= i < cont_index + k:
		ans_pos += a[i]
	else:
		ans_pos += max(0, a[i])

cont_sum = float("inf")
cont_index = None
for i in range(n - k + 1):
	if range_sum(i, i + k - 1) < cont_sum:
		cont_index = i
		cont_sum = range_sum(i, i + k - 1)

ans_neg = 0
for i in range(n):
	if cont_index <= i < cont_index + k:
		continue
	else:
		ans_neg += max(0, a[i])

print(max(ans_pos, ans_neg))

Submission status: Wrong Answer

Solution code:
n, k = list(map(int,input().split()))
a = list(map(int,input().split()))
l = [i for i in a if i>0]
ans = sum(l)
t = 0
for i in range(k):
    t += a[i]
c = 0
import sys
for i in range(k,n):
    f = True
    for j in range(k):
        if a[i-j]>=0:
            f = False
            break
    if f:
        print(ans)
        sys.exit()
    if a[i]>a[i-k]:
        c = i
        t += a[i]-a[i-k]
a = a[:c-k]+a[c+1:]
l = [i for i in a if i>0]
print(sum(l)+t)

Submission status: Wrong Answer

Solution code:
n, k = list(map(int,input().split()))
a = list(map(int,input().split()))
l = [i for i in a if i>0]
ans = sum(l)
t = 0
for i in range(k):
    t += a[i]
c = 0
import sys
for i in range(k,n):
    f = True
    for j in range(k):
        if j>=0:
            f = False
            break
    if f:
        print(ans)
        sys.exit()
    if a[i]>a[i-k]:
        c = i
        t += a[i]-a[i-k]
a = a[:c-k]+a[c+1:]
l = [i for i in a if i>0]
print(sum(l)+t)

Submission status: Wrong Answer

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

dp=[0 for x in range(N)]

#最後に（白か黒か）塗るKマスを求める。
#dp[i]：iからKマスの総和。
#max(dp[i])が該当箇所。
#max(dp[i])<0ならば塗らない方が良いので０を出力。max(dp[i])>0ならばその部分を最後に黒く塗る。
#重要なのは該当部分以外はKマスの制約を考えなくて良いこと。i->i+K-1マス黒く塗った後にi+1->i+Kマス白く塗れば独立する

for i in range(N-(K-1)):
  dp[i]=sum(A[i:i+K])

#もっとも大きい総和をもつ長さKの区間とその開始位置を探索。
en=N
ab=-(10**10)
for i in range(N-(K-1)):
  if dp[i]>ab:
    ab=dp[i]
    en=i
    
#上記は最後に黒く塗るのでそれ以外は自由に塗ることができる
#どの区間をとっても０以下ならば塗らないので答えは０
ans=0
if ab>0:
  ans+=dp[en]
  for i in range(N):
    if not(en<= i <=en+(K-1)):
      ans+=max(0,A[i])

print(ans)

Submission status: Wrong Answer

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

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)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
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] + a[K + i - 1])
    sk_pl.append(sk_pl[-1] - pl[i] + 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)

Submission status: Wrong Answer

Solution code:
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):
    tmp1=s1[i+k-1]-s1[max(0,i-1)]
    tmp2=s2[n-1]-(s2[i+k-1]-s2[max(0,i-1)])
    ans=max(ans,tmp1+tmp2,tmp2)
print ans

Submission status: Wrong Answer

Solution code:
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]
    if a[i]>0:
        s2[i]+=s2[i-1]+a[i]
ans=-float("inf")
for i in xrange(n-k+1):
    tmp1=s1[i+k-1]-s1[max(0,i-1)]
    tmp2=s2[n-1]-(s2[i+k-1]-s2[max(0,i-1)])
    ans=max(ans,tmp1+tmp2,tmp2)
print ans

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = [int(i) for i in input().split()]
ans = 0
for i in range(N):
	if A[i] > 0:
		ans += A[i]
		A[i] = 0
s = 0
t = 0
for a in A:
	if not a:
		t += 1
		s = 1
	else:
		t = 1
		s += 1
	if t >= K or s >= K:
		print(ans)
		exit()
m = sum(A[:K])
for i in range(N-K):
	M = m - A[i] + A[i+K]
	m = max(M,m)
print(max(ans+m,0))

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = [int(i) for i in input().split()]
ans = 0
for i in range(N):
	if A[i] > 0:
		ans += A[i]
		A[i] = 0
t = 1
for a in A:
	if not a:
		t += 1
	else:
		t = 1
	if t >= K:
		print(ans)
		exit()
m = sum(A[:K])
for i in range(N-K):
	M = m - A[i] + A[i+K]
	m = max(M,m)
print(max(ans+m,0))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
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]]
	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)))

Submission status: Wrong Answer

Solution code:
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_sum
	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)

Submission status: Wrong Answer

Solution code:
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] = 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]]
	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)))

Submission status: Wrong Answer

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

d = [sum(L[0:K])]
for i in range(N-K):
    d += [d[i] - L[i] + L[i+K]]
c1 = c2 = 0
for i in range(N-K+1):
    if d[i] > d[c1] : c1 = i
    if d[i] < d[c2] : c2 = i
a = sum(L[x] for x in range(N) if L[x] > 0 or (x >= c1 and x < c1+K))
b = sum(L[x] for x in range(N) if L[x] > 0 and not (x >= c2 and x < c2+K))
print(max(0, a, b))

Submission status: Wrong Answer

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

d = [sum(L[0:K])]
for i in range(N-K):
    d += [d[i] - L[i] + L[i+K]]
c = 0
for i in range(N-K+1):
    if d[i] > d[c] : c = i

print(max(0, sum(L[x] for x in range(N) if L[x] > 0 or (x >= c and x < c+K))))

Submission status: Wrong Answer

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

d = [sum(L[0:K])]
for i in range(N-K):
    d += [d[i] - L[i] + L[i+K]]
c = 0
for i in range(N-K+1):
    if d[i] > d[c] : c = i

print(max(0, sum(L[x] for x in range(N) if L[x] > 0 and not(x >= c and x < c+K)))+d[c])

Submission status: Wrong Answer

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

d = [sum(L[0:K])]
for i in range(N-K):
    d += [d[i] - L[i] + L[i+K]]
c = 0
for i in range(N-K+1):
    if d[i] > d[c] : c = i

print(max(0, sum(L[x] for x in range(N) if L[x] > 0 and not(x >= c and x <= c+K)))+d[c])

Submission status: Wrong Answer

Solution code:
N, K = map(int, raw_input().split())
A = map(int, raw_input().split())
ans, mi = 0, -1
for i in range(N-K+1):
    ans, mi = max(ans, sum(A[i:i+K])), i
if mi != -1:
    for i in range(N):
        if mi <= i < mi + K:
            continue
        ans += max(0, A[i])
print ans

Submission status: Wrong Answer

Solution code:
from collections import deque

n, k = map(int, input().split())
a = list(map(int, input().split()))
q = deque(a[:k])
max_ = min_ = cur = sum(q)
plus = cur_plus = plus_in_max = plus_in_min = sum(x for x in q if x > 0)
for b in a[k:]:
    c = q.popleft()
    q.append(b)
    cur += b - c
    if b > 0:
        plus += b
        cur_plus += b
    if c > 0:
        cur_plus -= c
    if max_ < cur or (max_ == cur and plus_in_max > cur_plus):
        max_ = cur
        plus_in_max = cur_plus
    if min_ > cur or (min_ == cur and plus_in_min > cur_plus):
        min_ = cur
        plus_in_min = cur_plus
print(max(plus + max_ - plus_in_max, plus - plus_in_min))

Submission status: Wrong Answer

Solution code:
from collections import deque

n, k = map(int, input().split())
a = list(map(int, input().split()))
q = deque(a[:k])
max_ = min_ = c = sum(q)
plus = plus_in_max = plus_in_min = sum(x for x in q if x > 0)
for b in a[k:]:
    c -= q.popleft()
    c += b
    q.append(b)
    if max_ < c:
        max_ = c
        plus_in_max = sum(x for x in q if x > 0)
    if min_ > c:
        min_ = c
        plus_in_min = sum(x for x in q if x > 0)
    if b > 0:
        plus += b
print(max(plus + max_ - plus_in_max, plus - plus_in_min))

Submission status: Wrong Answer

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

def f(arr):
    s = sum(a[N-K:N])
    if s<0:
        s = 0
    for i in range(N - K):
        if a[i] > 0:
            s += a[i]
    return s

print(max(f(a), f(a[::-1])))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

def main():
    N,K = map(int,input().split())
    a = list(map(int,input().split()))
    def point(x):
        use = a[:x]+a[x+K:]
        borf = a[x:x+K]
        score = 0
        for num in use:
            if num > 0:
                score += num
        if sum(borf) > 0:
            score += sum(borf)
        return(score)
        
    ans = 0
    for i in range(N-K+1):
        ans = max(ans,point(i))
        
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
*A, = map(int, input().split())
ans = -float('inf')
for i in range(N - K + 1):
    ans = max(ans, max(sum(A[i: i+K]), 0) + sum([a for a in A[:i] + A[i+K:] if a > 0]))
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
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)
v=0
for i in range(n-k+1):
  v=max(v,max(0,acc[i+k]-acc[i])+sum(m[i+k:])+sum(m[:i]))
print(v)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
N, K = map(int, input().split())
a = list(map(int, input().split()))

pl = [(x if (x > 0) else 0) for x in a]
ans = 0
if lambda x: x > 0 in a:
    for i in range(N - K + 1):
        ans = max(ans, max(0, sum(a[i:K + i])) + sum(pl[:i]) + sum(pl[K + i:]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
k = 0
for i in range(N-K+1):
	K_sum = max(0, sum(A[i:i+K]))
	K_pos = sum(map(lambda x:max(0, x), A[i:i+K]))
	loss = K_pos-K_sum
	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)

Submission status: Time Limit Exceeded

Solution code:
### B
N, K = map(int, input().split())
A = list(map(int, input().split()))
result = 0
for i in range(N-K+1):
	K_sum = max(0, sum(A[i:i+K]))
	N_sum = K_sum + sum(map(lambda x:max(0, x), A[:i]+A[i+K:]))
	result = max(result, N_sum)
print(result)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
arr=list(map(int,input().split()))
brr=list(map(lambda x: max(x,0),arr))
total=0
for i in range(n-k+1):
    total=max(total,sum(brr[:i])+max(0,sum(arr[i:i+k]))+sum(brr[i+k:]))
print(total)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,raw_input().split())
a=map(int,raw_input().split())
total=[0]*(n+1)
for i in xrange(n):
    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=0
    for j in xrange(i,i+k):
        tmp+=a[j]
    ans=max(ans,tmp+total[i]+total[n]-total[i+k],total[i]+total[n]-total[i+k])

print(ans)

Submission status: Time Limit Exceeded

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

import numpy as np
a = np.array(a, dtype=np.int32)
c = a.clip(min=0)
s = np.sum(c)

ans = 0
for i in range(N - K + 1):
    tmp = s - np.sum(c[i:i + K]) + max(0, np.sum(a[i:i + K]))
    ans = max(ans, tmp)

print(ans)

Submission status: Time Limit Exceeded

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

print max([max(sum(a[i:i+k]), 0) + sum([i for i in a[:i] + a[i+k:] if i > 0]) for i in range(n-k+1)])

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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):
    #print(ans)
    amid+=a[i+k]
    amid-=a[i]
    ans=max(ans,ac[i]+max(amid,0)+acr[n-k-i-1])
    #print(ans,ac[i],amid,acr[n-k-i-1])
print(ans)

Submission status: Accepted

Solution code:
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(black,white)
print(ans)

Submission status: Accepted

Solution code:
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
# ansb:黒に塗った時、理想値からの差分
# answ:白に塗った時、理想値からの差分
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))

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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])
  #print(max(0,tmp),tmp2)
  if max(0,tmp)+tmp2>ans:
    ans=max(0,tmp)+tmp2
print(ans)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
#from collections import deque,defaultdict
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 # and False
BIG = 10**18
R = 10**9 + 7
#R = 998244353

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)

Submission status: Accepted

Solution code:
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))

#[i, i+K) will be all white/black.
max_score = 0
for i in range(N-K+1):
    score = 0
    all_black = csum[i+K] - csum[i]
    if all_black > 0: # if [i, i+K) is worth painting with black 
        score += all_black
    score += csum_of_positives[i] #[0, i)
    score += csum_of_positives[N] - csum_of_positives[i+K] #[i+K, N)    
    max_score = max(max_score, score)

print(max_score)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# B - Contiguous Repainting
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)

Submission status: Accepted

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
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()