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 = list(map(int, input().split()))

cum = []
abscum = []

cu = 0
acu = 0
for i in range(n):
    cu += a[i]
    acu += max(0, a[i])
    cum.append(cu)
    abscum.append(acu)

ans = 0
for i in range(n-k+1):
    if i == 0:
        ans = max(ans, abscum[n-1] - abscum[i+k-1] + max(0, cum[i+k-1]))
    else:
        ans = max(ans, abscum[n - 1] - (abscum[i + k - 1] - abscum[i-1]) + max(0, cum[i + k - 1] - cum[i-1]))

print(ans)

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = [int(m) for m in input().split()]
sum = 0
for i in range(n):
    if a[i] > 0:
        sum += a[i]

sei = 0
fu = 0
for i in range(k):
    if a[i] > 0:
        sei += a[i]
    else:
        fu += a[i]
zen = sei + fu
ansli = []
if zen > 0:
    ansli.append(sum + fu)
else:
    ansli.append(sum - sei)
for i in range(k, n):
    if a[i] > 0:
        sei += a[i]
    else:
        fu += a[i]
    if a[i - k] > 0:
        sei -= a[i - k]
    else:
        fu -= a[i - k]
    zen = sei + fu
    if zen > 0:
        ansli.append(sum + fu)
    else:
        ansli.append(sum - sei)
print(max(ansli))

Submission status: Accepted

Solution code:
from itertools import accumulate

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

b_list = []
for a in a_list:
    if a > 0:
        b_list.append(a)
    else:
        b_list.append(0)
b_list = list(accumulate(b_list))
a_acc = list(accumulate(a_list))

b_list.insert(0, 0)
b_list.append(b_list[-1])
a_acc.insert(0, 0)
ans = 0


for i in range(N - K + 1):

    ans = max(ans, b_list[i] + a_acc[i + K] - a_acc[i] + b_list[N] - b_list[i + K])
    ans = max(ans, b_list[i] + b_list[N] - b_list[i + K])
print(ans)

Submission status: Accepted

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

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

ans = -float('inf')
for l in range(N-K+1):
    free = cums_p[l] + cums_p[-1] - cums_p[l+K]
    cont = cums[l+K] - cums[l]
    ans = max(ans, free, free+cont)
print(ans)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
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())

acc_all = [0]
acc_pos = [0]

for ai in a:
    if ai > 0:
        acc_all.append(acc_all[-1] + ai)
        acc_pos.append(acc_pos[-1] + ai)
    else:
        acc_all.append(acc_all[-1] + ai)
        acc_pos.append(acc_pos[-1])

ans = 0    
for st in range(n-k+1):
    black = (acc_all[st+k] - acc_all[st])\
            + (acc_pos[n] - acc_pos[st+k])\
            + (acc_pos[st] - acc_pos[0])
    white = (acc_pos[n] - acc_pos[st+k])\
            + (acc_pos[st] - acc_pos[0])

    ans = max(ans, black, white)
    
print(ans)

Submission status: Accepted

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

M1=0
for i in range(N):
    if a[i]>=0:
        M1+=a[i]
        
s=0
for i in range(K):
    s+=max(0,a[i])
m1=s
for i in range(N-K):
    s=s+max(0,a[K+i])-max(0,a[i])
    if m1>s:
        m1=s

s=0

for i in range(K):
    s+=min(0,a[i])
m2=s
for i in range(N-K):
    s=s+min(0,a[K+i])-min(0,a[i])
    if m2<s:
        m2=s
print(max(M1-m1,M1+m2))

Submission status: Accepted

Solution code:
import itertools
N, K = [int(_) for _ in input().split()]
A = [0] + [int(_) for _ in input().split()]

cumsum_p = list(
    itertools.accumulate([A[i] if A[i] > 0 else 0 for i in range(N + 1)]))
cumsum_m = list(
    itertools.accumulate([A[i] if A[i] < 0 else 0 for i in range(N + 1)]))
ans = -float('inf')
for i in range(N - K + 1):
    ans = max(ans, -(cumsum_p[i + K] - cumsum_p[i]),
              cumsum_m[i + K] - cumsum_m[i])
ans += cumsum_p[-1]
print(ans)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
A=[int(i) for i in input().split()]
P=[0]*(N+1)
T=[0]*(N+1)
for i in range(N):
    P[i+1]=P[i]+A[i]
    if A[i]>=0:
        T[i+1]=T[i]+A[i]
    else:
        T[i+1]=T[i]
a=max(sum(A),0)
for i in range(K,N+1):
    t=P[i]-P[i-K]
    s=T[i-K]-T[0]
    u=T[N]-T[i]
    a=max(a,s+t+u,s+u)
    #print(a,s,t,u)
print(a)

Submission status: Accepted

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

b = [0] #a[i]までのsum
c = [0] #a[i]までの+のみのsum

for i in range(n):
    b.append(b[-1]+a[i])
    if a[i] > 0:
        c.append(c[-1]+a[i])
    else:
        c.append(c[-1])


res = 0
for i in range(n-k+1):
    if b[i+k]-b[i] > 0:
        w = b[i+k]-b[i] + (c[i]-c[0]) + (c[n]-c[i+k])
    else:
        w = c[i]-c[0]+c[n]-c[i+k]
    res = max(res,w)
print(res)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
rui = [0]*(n+1)
wa = 0
for i in range(n):
  rui[i+1] = rui[i] + a[i]
pura = 0
for i in range(n-k):
  if a[i] >0:
    pura += a[i]
for i in range(n-k,-1,-1):
  wa = max(pura+rui[i+k]-rui[i],pura,wa)
  if a[i-1] >0:
    pura -= a[i-1]
  if a[i+k-1]>0:
    pura += a[i+k-1]
print(wa)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
a=[int(i) for i in input().split()]
S=[0]
p=[0]


for i in range(1,N+1):
  S.append(S[i-1]+a[i-1])
  if a[i-1]>0:
    p.append(p[i-1]+a[i-1])
  else:
    p.append(p[i-1])

ans=0
for i in range(1,N-K+2):
  res=0
  res+=max(S[i+K-1]-S[i-1],0)
  res+=p[i-1]
  res+=p[-1]-p[i+K-1]
  ans=max(res,ans)
print(ans)

Submission status: Accepted

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

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

Score = max(max(0, Whole[K] - Whole[0]) + Plus[N] - Plus[K], Plus[N-K] - Plus[0] + max(0, Whole[N] - Whole[N-K]))
for i in range(1, N-K):
    temp = Plus[i] + max(0, Whole[i+K] - Whole[i]) + Plus[N] - Plus[i+K]
    Score = max(Score, temp)

print(Score)

Submission status: Accepted

Solution code:
def inpl(): return [int(i) for i in input().split()]

N, K = inpl()
a = inpl()
b = [i if i>0 else 0 for i in a ]
c = [i if i<0 else 0 for i in a ]
d = [0 for _ in range(N-K+1)]
d[0] = sum(c[:K])
e = [0 for _ in range(N-K+1)]
e[0] = sum(b[:K])
for i in range(N-K):
    d[i+1] = d[i] - c[i] + c[i+K]
    e[i+1] = e[i] - b[i] + b[i+K]
print(max(0, sum(b)+max(d), sum(b)-min(e)))

Submission status: Accepted

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

a = list(map(int, input().split()))
a_plus = [max(a[i], 0) for i in range(n)]

a_sum = [0]
a_plus_sum = [0]

for i in range(n):
    a_sum.append(a_sum[-1] + a[i])
    a_plus_sum.append(a_plus_sum[-1] + a_plus[i])

best = -1
best_lost = 10**16
for i in range(k, n+1):
    temp_lost = (a_plus_sum[i] - a_plus_sum[i-k]) - max((a_sum[i] - a_sum[i-k]), 0)
    if best_lost >  temp_lost:
        best_lost = temp_lost
        best = i
        
ans = a_plus_sum[n] - best_lost
print(max(ans, 0))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n,k = map(int, input().split())
a = [int(x) for x in input().split()]

acc_a = []
acc_b = []
acc_a.append(0)
acc_b.append(0)

for i in range(n):
    acc_a.append(a[i]+acc_a[-1])
    acc_b.append(max(0,a[i]) + acc_b[-1])

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

    t = 0
    t += acc_b[i] - acc_b[0]
    t += acc_b[n] - acc_b[i+k]
    ans = max(ans,t)
print(ans)

Submission status: Accepted

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

sumRest = sum([A for A in As[K:] if A > 0])
sumPlus = sumMinus = 0
for A in As[:K]:
    if A > 0:
        sumPlus += A
    else:
        sumMinus += A

ans = 0
for i in range(N - K + 1):
    score = sumRest + max(sumPlus + sumMinus, 0)
    ans = max(ans, score)

    if As[i + K] > 0:
        sumRest -= As[i + K]
        sumPlus += As[i + K]
    else:
        sumMinus += As[i + K]

    if As[i] > 0:
        sumRest += As[i]
        sumPlus -= As[i]
    else:
        sumMinus -= As[i]

print(ans)

Submission status: Accepted

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

# Kの連続する数列ひとつだけ黒か白に統一されている縛りがある
# ほかは任意なので、正は黒に、負は白にぬればよい

CumS = [0] * (N+1)
CumSPos = [0] * (N+1)

for i in range(N):
  CumS[i+1] = CumS[i] + A[i]
  CumSPos[i+1] = CumSPos[i] + (A[i] if A[i] > 0 else 0)

ans = (-1) * float("inf")
# i : 統一されてるシークエンスの始まりindex。1-indexed
for i in range(1,N+1): #1-index
  if i+K-1 > N:
    break
  work = 0
  work += CumSPos[i-1] # pos -> black, neg -> white
  work += max(CumS[i+K-1] - CumS[i-1], 0) # black or white
  work += CumSPos[N] - CumSPos[i+K-1]  # pos -> black, neg -> white
  ans = max(ans, work)
  #print(i,work, CumSPos[i-1], max(CumS[i+K-1] - CumS[i-1], 0), CumSPos[N] - CumSPos[i+K-1])
  
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
ai = lambda: list(map(int,input().split()))

n,k = ai()
a = ai()

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

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

ans = -float('inf')
for i in range(n-k+1):
    ans = max(ans, max(0, sa[i+k]-sa[i]) + spa[i] + (spa[n]-spa[i+k]))
print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
sum_a = [0]
for ai in a:
    sum_a.append(sum_a[-1] + (ai if ai > 0 else 0))
sum_sk = sum(a[:k])
ans = max(sum_sk + sum_a[n] - sum_a[k], sum_a[n] - sum_a[k])
for i in range(n - k):
    sum_sk = sum_sk - a[i] + a[i + k]
    ans = max(ans,
              sum_sk + sum_a[n] - (sum_a[i + k + 1] - sum_a[i + 1]),  # 黒色
              sum_a[n] - (sum_a[i + k + 1] - sum_a[i + 1]))  # 白色
print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate as acc
N, K, *a = map(int, open(0).read().split())
*b, = map(lambda x: max(x, 0), a)
*Sa, = acc([0] + a)
*Sb, = acc([0] + b)
print(max(Sb[i] + max(0,Sa[i+K]-Sa[i]) + Sb[N]-Sb[i+K] for i in range(N-K+1)))

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

def li(): return [int(x) for x in stdin.readline().split()]
def li_(): return [int(x)-1 for x in stdin.readline().split()]
def lf(): return [float(x) for x in stdin.readline().split()]
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(ns())
def nf(): return float(ns())

from itertools import accumulate

n,k = li()
a = li()

a_cum = list(accumulate([0] + a))
a_pl = [ai if ai>0 else 0 for ai in a]
a_left = list(accumulate([0] + a_pl))
a_right = list(accumulate([0] + a_pl[::-1]))

ans = 0

for i in range(n-k+1):
    # a[i:i+k]を黒にするとき
    cand = a_cum[i+k] - a_cum[i]
    cand += (a_left[i] + a_right[n-(i+k)])
    ans = max(ans,cand)
    
    
    # a[i:i+k]を白にするとき
    cand = 0
    cand += (a_left[i] + a_right[n-(i+k)])
    ans = max(ans,cand)
    
    
print(ans)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
a=[int(i) for i in input().split()]
b=[max([a[i],0]) for i in range(N)]
S=[0 for i in range(N+1)]
T=[0 for i in range(N+1)]
for i in range(N):
    S[i+1]=S[i]+a[i]
    T[i+1]=T[i]+b[i]
ans=0
for i in range(N-K+1):
    tmp=T[N]+S[i+K]-T[i+K]+T[i]-S[i]
    if ans<tmp:
        ans=tmp
for i in range(N-K+1):
    tmp=T[N]
    M=T[i+K]-T[i]
    tmp-=M
    if ans<tmp:
        ans=tmp
print(ans)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
a=[int(i) for i in input().split()]
b=[max([a[i],0]) for i in range(N)]
S=[0 for i in range(N+1)]
T=[0 for i in range(N+1)]
for i in range(N):
    S[i+1]=S[i]+a[i]
    T[i+1]=T[i]+b[i]
ans=-10**15
for i in range(N-K+1):
    tmp=T[N]+S[i+K]-T[i+K]+T[i]-S[i]
    if ans<tmp:
        ans=tmp
for i in range(N-K+1):
    tmp=T[N]
    M=T[i+K]-T[i]
    tmp-=M
    if ans<tmp:
        ans=tmp
print(ans)

Submission status: Accepted

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

ans = -float("inf")

for i in range(n - k + 1):
	ans = max(ans, range_sum(i, i + k - 1) + range_pos(0, i - 1) + range_pos(i + k, n - 1), range_pos(0, i - 1) + range_pos(i + k, n - 1))

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())

N,K = inpl()
aa  = inpl()

SUM_aa = [0]
ABS_aa = [0]
tmp1 = tmp2 = 0
for a in aa:
	tmp1 += a
	tmp2 += max(a,0)
	SUM_aa.append(tmp1)
	ABS_aa.append(tmp2)

SUM = ABS_aa[N]
ans = 0
for i in range(N-K+1):
	left = ABS_aa[i]
	right = SUM - ABS_aa[i+K]
	mid = SUM_aa[i+K]-SUM_aa[i]
	ans = max(ans,left+right+max(0,mid))

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, K, A):

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

    ans = 0
    for i in range(N-K+1):
        l = sa0[i]
        r = sa0[-1] - sa0[i+K]
        c = sa[i+K] - sa[i]
        ans = max(ans, l + r)
        ans = max(ans, l + c + r)

    return ans


def main():
    N, K = read_int_n()
    A = read_int_n()
    print(slv(N, K, A))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

    ans = 0
    for i in range(n-k+1):
        ss = sb[i] + sb[n] - sb[i+k]
        s1 = sa[i+k] - sa[i] + ss
        ans = max(ans, s1, ss)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=[0]+list(map(int,input().split()))
s=[0]
p=[0]
for i in range(1,n+1):
  s.append(s[i-1]+a[i])
  p.append(p[i-1]+max(0,a[i]))
ans=0
for i in range(1,n-k+2):
  t=max(0,s[i+k-1]-s[i-1])
  t+=p[i-1]+p[n]-p[i+k-1]
  ans=max(ans,t)
print(ans)

Submission status: Accepted

Solution code:
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import *
from bisect import bisect
 
def read():
  return int(input())
 
def reads():
  return [int(x) for x in input().split()]

N, K = reads()
a = reads()

ppsum = [0] * (N+1)
psum = [0] * (N+1)

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

ansb = max(ppsum[i] + psum[i+K] - psum[i] + ppsum[N] - ppsum[i+K] for i in range(N-K+1))
answ = max(ppsum[i] + ppsum[N] - ppsum[i+K] for i in range(N-K+1))

print(max(ansb, answ))

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
b = sum([i for i in A[:K] if i <= 0])
bMax = b
w = sum([i for i in A[:K] if i >= 0])
wMin = w
for i in range(N-K):
    b = b - min(A[i], 0) + min(A[K+i], 0)
    w = w - max(A[i], 0) + max(A[K+i], 0)
    bMax = max(bMax, b)
    wMin = min(wMin, w)
print(sum(i for i in A if i >= 0) + max(bMax, -wMin))

Submission status: Accepted

Solution code:
n,k = (int(i) for i in input().split())
a = [int(i) for i in input().split()]
x,y,ans = [0],[0],0
for i in range(n):
	x.append(x[-1]+a[i])
	y.append(y[-1]+max(0,a[i]))
for i in range(1,n-k+2):
	num,num2 = y[i-1]+y[n]-y[i+k-1],x[i+k-1]-x[i-1]
	ans = max(ans,num,num+num2)
print(ans)

Submission status: Accepted

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

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

result = max(w, b)

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

print(result)

Submission status: Accepted

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

#最後に（白か黒か）塗るKマスの位置を求める。
#重要なのは該当部分以外はKマスの制約を考えなくて良いこと。i->i+K-1マス黒く塗った後にi+1->i+Kマス白く塗れば独立する

#plは当該区間の正の総和、maは当該区間の負の総和。
#最後に選ぶ連続するK個は以下の条件を満たすK個
#黒く塗ると仮定すると損をする値（ma）と白く塗る場合損をする値（pl)のminをとり、その最小値区間(reで記録)。
pl=0
ma=0
re=0

#まずは０を起点とするK個の情報を記録。その後、始点と追加点を加減しながらO(N)で求める
for i in range(K):
  if A[i] >= 0:
    pl+=A[i]
  else:
    ma+=(-A[i])
re=min(pl,ma)

for i in range(1,N-K+1):
  if A[i-1] >= 0:
    pl-=A[i-1]
  else:
    ma+=A[i-1]
  if A[i+K-1]>=0:
    pl+=A[i+K-1]
  else:
    ma+=(-A[i+K-1])
  if min(pl,ma) < re:
    re=min(pl,ma)
    
#最後に塗るK以外の区間は自由に塗る。
#最後に塗るKの区間は黒く塗る場合でも白く塗る場合でも、結果に影響するのは(-re)分のみ。
ans=0
for i in range(N):
  ans+=max(0,A[i])
    
print(ans-re)

Submission status: Accepted

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

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

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

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

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

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

    # 区間leftからrightまで、負になるなら0（白色)、正になるなら累積和をもとに（黒色）
    score = max(0, cumsum[right] - cumsum[left])
    # 左端からleftまで自由に色を塗る
    score += cummaxsum[left]
    # rightから右端まで自由に色を塗る
    score += cummaxsum[-1] - cummaxsum[right]

    ans = max(ans, score)

print(ans)

Submission status: Accepted

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

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

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

Submission status: Accepted

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

white_start, black_start = 0, 0
white_sum, black_sum = 0, 0#K区間を白、黒にしたときの"損失"
for i in range(K):
  white_sum += max(-a[i],0)
  black_sum += max(a[i],0)
curr_white = white_sum
curr_black = black_sum

for i in range(N-K):
  curr_white += max(-a[i+K],0) - max(-a[i],0)
  curr_black += max(+a[i+K],0) - max(+a[i],0)
  if curr_white < white_sum :
    white_sum = curr_white
    white_start = i+1
  if curr_black < black_sum :
    black_sum = curr_black
    black_start = i+1
ans = 0
if white_sum < black_sum:#白塗りのほうがいい
  for i in range(N):
    if i < white_start or i >= white_start+K:
      ans += max(a[i],0)
    else: ans+=a[i]
  print(ans)
else:
  for i in range(N):
    if i < black_start or i >= black_start+K:
      ans += max(a[i],0)
  print(ans)

Submission status: Accepted

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

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

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

print(ans)

Submission status: Accepted

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 - 1] + a[K + i - 1])
    sk_pl.append(sk_pl[-1] - pl[i - 1] + pl[K + i - 1])

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

print(ans)

Submission status: Accepted

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


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

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


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

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

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#AGc008B

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

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

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

print res

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

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

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

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

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

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

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

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

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

result = 0

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

print result

Submission status: Accepted

Solution code:
import numpy as np

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

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

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

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

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]]) + (imosW[sepB[1]] - imosW[sepB[0]])
	for i in range(1, N+1):
		if a[i] > 0 and not(i > sepB[0] and i <= sepB[1]):
			ansB += a[i]

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

Submission status: Accepted

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_sum0
	if i==0:
		loss_min = loss
	if loss<loss_min:
		k = i
		loss_min = loss
K_sum_result = max(0, sum(A[k:k+K]))
result = K_sum_result + sum(map(lambda x:max(0, x), A[:k]+A[k+K:]))
print(result)

Submission status: Accepted

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

# 解説どおりのやりかた

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

ans = 0

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

print(ans)

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

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

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

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

print(ans)