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: Accepted

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

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

ans = sum(A)
for i in range(N-K+1):
#     print(i, i+K, S0, S1, S2)
    ans = max(ans, S0 + max(S1, 0) + S2)
    if A[i] > 0:
        S0 += A[i]
    if A[i+K] > 0:
        S2 -= A[i+K]
    S1 = S1 - A[i] + A[i+K]
print(ans)

Submission status: Accepted

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

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

#print(A)
#print(B)

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

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

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

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

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

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

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

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

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

print(ans)

Submission status: Accepted

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

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

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

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

ans = 0

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

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from itertools import accumulate
import sys
input = sys.stdin.readline

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

Submission status: Accepted

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

Submission status: Accepted

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

ans = 0  # 何も操作しない

# 何かしら操作するなら、最後に黒がK列または白がK列残った状態になる。他は任意っぽそうなのでベストを尽くす
best = [0]
for a in A:
    if a < 0:
        a = 0
    best.append(best[-1] + a)

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


print(ans)

Submission status: Accepted

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

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

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

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

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

Submission status: Accepted

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

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

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

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

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

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

Submission status: Accepted

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

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

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

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

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

    ans=max(ans,test,test2)

print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate

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

    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

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

pos = 0
neg = 0

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

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

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

mod = 10**9 + 7

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

#################

# "どこかの連続したK個が同じ色"が必要十分

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

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

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

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

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

print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate

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

Submission status: Accepted

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


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


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

print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
import numpy as np

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

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

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

print(answer)
# 54

Submission status: Accepted

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

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

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

if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from itertools import accumulate

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

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

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

print(ans)

Submission status: Accepted

Solution code:
#b
#from itertools import accumulate
n, k  = [int(i) for i in input().split()]
a     = [int(i) for i in input().split()]

plus,minus = [0],[0] #initialize for the beginning
plus_accumulate  = 0
minus_accumulate = 0

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

print(plus_accumulate - minimum_lost)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# 解説AC
N,K = map(int, input().split())
A = [int(i) for i in input().split()]

# 累積和
S1 = [0] * (N + 1)
# 正のみの累積和
S2 = [0] * (N + 1)
for i in range(N):
    S1[i+1] = S1[i] + A[i]
    S2[i+1] = S2[i] + (A[i] if A[i] >= 0 else 0)

ans = -float("inf")
for i in range(N - K + 1):
    left, right = i, i + K
    
    tmp = S2[left] - S2[0] # 左側
    tmp += max(0, S1[right] - S1[left]) # 連続部分列
    tmp += S2[N] - S2[right] # 右側

    ans = max(ans, tmp)

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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]
#print(csp, cs)
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)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

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)

Submission status: Accepted

Solution code:
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
# print(a)
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
# print(a,ai,b)

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)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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
#        print(now1,now2)
        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()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# K個の連番の単色があればよい。単色の場所を決め打って貪欲

import numpy as np

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

Aplus = np.maximum(A,0)

# K個の連番の左端のインデックスに合わせる
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)

Submission status: Accepted

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

# 連続する長さKの区間を黒/白で塗る
# 残りを自由に塗る

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

    # A[:i] までは任意、A[i:i+k]は塗るか塗らないかの2択、A[i+k:]からは任意
    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()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
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))  # type: int
    K = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, K, a)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:

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)

Submission status: Accepted

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