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

Submission status: Accepted

Solution code:

import sys
input = sys.stdin.readline
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
# A = [ int(input()) for _ in range(N) ]
##############################

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

#print(S)

# 区間を白/黒、区間の外を白/黒で比較
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(tmp, sum_in, sum_left, sum_right, l, r)


print(ans)

Submission status: Accepted

Solution code:
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])
#print(Acu)
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])
#print(Acu_p)
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)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#AGC8 B

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)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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]
    #print(t)
    ans = max(t,ans)

print(ans)

Submission status: Accepted

Solution code:
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):  # []left - left + K) を捨てる or 加える
        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()

Submission status: Accepted

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

import numpy as np

# どこかの長さKは最後に単色で残る
# そこを残すと決めると他は自由に設定できる

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)]

# 各地点を左端として、長さKの区間の合計を求める
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)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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]

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)]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
###template###
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)
# 4近傍（右, 下, 左, 上）
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())
###template###

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

c_m = [] # cumsum_minus
c_p = [] # cumsum_plus

#番兵的に0を追加しておく
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): #0 ~ N-K までループ
  # [i, i+K) を all or nothing にする
  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]#左端からi-1までの累積和([i-1+1]) + i+kから右端までの累積和 [i+k, N)
  ans = max(ans, tmpans)

print(ans)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
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

#A
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

#B
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

#C
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

#D
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

#E
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

#F
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

#Solve
if __name__ == "__main__":
    F()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from itertools import*
from math import*
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = float("inf")
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)

#色を塗るタイプの操作は逆順に見ていけば確定した色が上書きされることは無いと思える
N,K = map(int,input().split())
a = list(map(int,input().split()))
A = [0]*(N+1)
S = [0]*(N+1)

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

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

print(ans)

Submission status: Accepted

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

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

S1 = [0]
s = 0

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

print(max_score)

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

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

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

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

Submission status: Accepted

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

ans=-10**18

for i in range(n-k+1):
    ans=max(ans,acc[i+k]-acc[i]+pos[i]+pos[-1]-pos[i+k])
    ans=max(ans,pos[i]+pos[-1]-pos[i+k])
print(ans)

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

Submission status: Accepted

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

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

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

b = [black]
w = [white]

for i in range(n-k):
    if a[i]>0:
        white += a[i]
    else:
        black -= a[i]
    if a[i+k] > 0:
        white -= a[i+k]
    else:
        black += a[i+k]
    b.append(black)
    w.append(white)

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

Submission status: Accepted

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

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


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

print(num)

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
from itertools import accumulate as acc

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

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

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


print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

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

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

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

Submission status: Accepted

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

Submission status: Accepted

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

from itertools import accumulate

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

    return ans

print(main())

Submission status: Accepted

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

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

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

Submission status: Accepted

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


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

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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from itertools import accumulate
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

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

Submission status: Accepted

Solution code:
# coding:utf-8

import sys
# from collections import Counter, defaultdict

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

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


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

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

    ans = 0
    # １つの[j, j+k)以外の全てのマスは白と黒好きに塗ることができる
    # ai > 0なら黒，それ以外は白に塗る
    for i in range(n - k + 1):
        ans = max(ans, max(C[i + k] - C[i], 0) + C2[i] + C2[-1] - C2[i + k])

    return ans


print(main())

Submission status: Accepted

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

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

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

Submission status: Accepted

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

Submission status: Accepted

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