Problem:


Score : 400 points

Problem Statement

We have N dice arranged in a line from left to right. The i-th die from the left shows p_i numbers from 1 to p_i with equal probability when thrown.

We will choose K adjacent dice, throw each of them independently, and compute the sum of the numbers shown. Find the maximum possible value of the expected value of this sum.

Constraints

1 ≤ K ≤ N ≤ 200000

1 ≤ p_i ≤ 1000

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K
p_1 ... p_N

Output

Print the maximum possible value of the expected value of the sum of the numbers shown.

Your output will be considered correct when its absolute or relative error from our answer is at most 10^{-6}.

Sample Input 1

5 3
1 2 2 4 5

Sample Output 1

7.000000000000

When we throw the third, fourth, and fifth dice from the left, the expected value of the sum of the numbers shown is 7. This is the maximum value we can achieve.

Sample Input 2

4 1
6 6 6 6

Sample Output 2

3.500000000000

Regardless of which die we choose, the expected value of the number shown is 3.5.

Sample Input 3

10 4
17 13 13 12 15 20 10 13 17 11

Sample Output 3

32.000000000000



Sample input:
5 3
1 2 2 4 5


Sample output:
7.000000000000

Submission status: Accepted

Solution code:
from collections import deque
N, K = map(int, input().split())
p = list(map(int, input().split()))
max_ans = 0
tmp_ans = 0
queue = deque([])
for i in range(N):
    e = (p[i] + 1) / 2 
    tmp_ans += e
    queue.append(e)
    if len(queue) > K:
        tmp_ans = tmp_ans - queue.popleft()
    max_ans = max(max_ans, tmp_ans)
print(max_ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
p = list(map(int, input().split()))
tmp = sum(p[:k])
res = tmp
for i in range(n - k):
    tmp -= p[i]
    tmp += p[i + k]
    res = max(res, tmp)
print((res + k) / 2)

Submission status: Accepted

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

val = 0
for i in range(k):
    val += p[i]
point = 0

cnt = val
for i in range(k,n):
    cnt = cnt +  p[i] - p[i-k]
    if cnt > val:
        val = cnt
        point = i-k+1
#print(point)

ans = 0
for i in range(k):
    ans += (p[point] + 1) / 2
    point += 1

print(ans)

Submission status: Accepted

Solution code:
def func(x):
    return (x+1)/2

n, k = map(int, input().split())
P = list(map(func, map(int, input().split())))
t = sum(P[0:k])
r = t
for i in range(n-k):
    t = t-P[i]+P[i+k]
    r = r if r>t else t
print(r)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
p = list(map(int,input().split()))
x = []
for i in p:
    if i % 2 == 0:
        x.append(i//2 + 0.5)
    else:
        x.append(i // 2 + 1)

ans = 0
for i in range(K):
    ans += x[i]

ans_list = [ans]
if N != K:
    for i in range(K,N):
        ans_list.append(ans_list[len(ans_list)-1]+x[i]-x[i-K])
print(max(ans_list))

Submission status: Accepted

Solution code:
import itertools

N, K=map(int, input().split())
p=list(map(int, input().split()))
acup=list(itertools.accumulate(map(lambda x:(x+1)/2, p)))
ans=acup[K-1]
for i in range(K, N):
    ans=max(ans, acup[i]-acup[i-K])
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
n,k = map(int, input().split())
p = np.array(list(map(int, input().split())))
m = (p+1)/2
s = sum(m[:k])
r = s
for i in range(n-k):
    s -= m[i]
    s += m[i+k]
    r = max(r,s)
print(r)

Submission status: Accepted

Solution code:
from itertools import accumulate

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

A = []
for i in P:
    A.append(1/2*(i+1))
    #A.append(1/2*i*(i+1)/i)

ans = 0
'''
for i in range(len(A)):
    ans = max(ans,sum(A[i:i+K]))
'''
    
accum = [0] + list(accumulate(A))
for i in range(len(accum)):
    ans = max(ans,accum[i] - accum[i-K])
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 # 998244353
input=lambda:sys.stdin.readline().rstrip()
from collections import deque
def resolve():
    n, k =map(int,input().split())
    Q = deque([])
    sum = 0
    ans = 0
    for a in map(int,input().split()):
        Q.append(a)
        sum += a
        if(len(Q)==k):
            ans = max(ans, (sum+k)/2)
            sum -= Q.popleft()

    print(ans)
resolve()

Submission status: Accepted

Solution code:
def solve(n, k, p):
    mu = [(p[i] + 1) / 2.0 for i in range(n)]
    best = sum(mu[:k])
    cur = best
    for i in range(k, n):
        cur += mu[i] - mu[i-k]
        best = max(best, cur)
    return best

n, k = map(int, input().split())
p = list(map(int, input().split()))
print(solve(n, k, p))

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
P = list(map(int,input().split()))
Q = []
R = P[K:]
s = 0.0
for i in range(K):
    Q.append((P[i]+1)/2)
s = sum(Q)
ans = s
for j in range(len(R)):
    r = (R[j] + 1)/2
    Q.append(r)
    s += (r - Q[j])
    ans = max(s,ans)
print(ans)

Submission status: Accepted

Solution code:
import math
import itertools
import fractions
import heapq
import collections
import bisect
import sys
import copy

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

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
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 I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

n,k = LI()
p = LI()

def a(num):
    return (num+1)/2

l = [a(i) for i in p]
ll = [0] + list(itertools.accumulate(l))
ans=0
for i in range(n-k+1):
    ans = max(ans,ll[i+k]-ll[i])
print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
ppp = list(map(int, input().split()))
tot = sum(ppp[:k])
ans = tot
for i in range(k, n):
    tot += ppp[i] - ppp[i - k]
    ans = max(ans, tot)
print((ans + k) / 2)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
p = list(map(int, input().split()))
l = [0 for i in range(n)]
ans = 0
cnt = 0
for i in range(n):
  l[i] = p[i]*(p[i]+1)/(2*p[i])
if n == k:
  ans = sum(l)
else:
  ans = sum(l[:k])
  cnt = ans
  for i in range(n-k):
    cnt = cnt - l[i] + l[i+k]
    if cnt > ans:
      ans = cnt
print(ans)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
p = input().split(' ')
# print(p)
ans = 0

start,end = 0,k - 1
cur = 0
for i in range(k):
    cur += (int(p[i]) + 1)/2
ans = max(ans,cur)
for i in range (k,n):
    cur += ((int(p[i]) + 1)/2)
    cur -= ((int(p[i - k]) + 1)/2)
    ans = max(ans,cur)
print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
p = list(map(int, input().split()))
e = [(1 + p[i]) / 2.0 for i in range(n)]
res = 0
cur = 0
for i in range(k):
    cur += e[i]
res = cur
for i in range(k, n):
    cur += e[i] - e[i-k]
    res = max([res, cur])
print(res)

Submission status: Accepted

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

s = 0
s_max = 0

for i in range(n):
    if i < k:
        s += p[i]
        if i == k-1:
            s_max = s
    else:
        s += p[i] - p[i-k]
        s_max = max(s_max, s)

print((k+s_max)/2)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# D - Dice in Line
from itertools import accumulate


def main():
    N, K, *P = map(int, open(0).read().split())
    # cumsum[i] = cumulative sum of expected values in [0, i]
    cumsum = tuple(accumulate([0] + [(i + 1) / 2 for i in P]))
    ans = max(right - left for left, right in zip(cumsum, cumsum[K:]))
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N, K = list(map(int, input().split()))
p = list(map(int, input().split()))
tmp = (sum(p[0:K]) + K) / 2
ret = tmp
for i in range(N-K):
    tmp = tmp - (p[i] - p[i+K]) / 2
    ret = max(tmp, ret)
print(ret)

Submission status: Accepted

Solution code:
# D - Dice in Line
from itertools import accumulate


def main():
    N, K, *P = map(int, open(0).read().split())
    # cumsum[i] = cumulative sum of expected values in [0, i]
    cumsum = tuple(accumulate([0] + [i * (1 + i) / (2 * i) for i in P]))
    ans = max(right - left for left, right in zip(cumsum, cumsum[K:]))
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

for i in range(n-1):
    A[i+1]+=A[i]

ans=0.0
A.reverse()
A.append(0)
A.reverse()

for i in range(n-k+1):
    now=A[i+k]-A[i]
    if now>ans:
        ans=now

print((ans+k)/2)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
A=list(map(int,input().split()))
for i in range(n):
    A[i]+=1

for i in range(n-1):
    A[i+1]+=A[i]

ans=0.0
A.reverse()
A.append(0)
A.reverse()

for i in range(n-k+1):
    now=A[i+k]-A[i]
    if now>ans:
        ans=now

print(ans/2)

Submission status: Accepted

Solution code:
from collections import deque

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

queue = deque()
currentSum = 0
maxSum = 0
for i in range(len(p)):
    currentSum = currentSum + p[i] + 1
    queue.append(p[i] + 1)
    if i >= K:
        currentSum = currentSum - queue.popleft()

    if i >= K - 1:
        maxSum = max(maxSum, currentSum)

print("{:.12f}".format(maxSum / 2))

Submission status: Accepted

Solution code:
# D - Dice in Line
from itertools import accumulate


def main():
    N, K, *P = map(int, open(0).read().split())
    # cumsum[i] = cumulative sum of expected values in [0, i]
    cumsum = tuple(accumulate(i * (1 + i) / (2 * i) for i in P))
    if N == K:
        print(cumsum[-1])
        return
    ans = 0
    for i in range(N - K):
        ans = max(ans, cumsum[i + K] - cumsum[i])
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,k = map(int, input().split())
dice = list(map(int, input().split()))
dice_sum = [0]
for i in dice:dice_sum.append(dice_sum[-1]+(i+1)/2)
def SumArea(r, l):
    return dice_sum[l]-dice_sum[r]

ans = 0
for i in range(n-k+1):
    tmp = SumArea(i, i+k)
    if tmp >= ans:
        ans = tmp
print(ans)

Submission status: Accepted

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

cml_sum = [(P[0]+1)/2.0]
for i in range(1, N):
    cml_sum.append(cml_sum[i-1] + (P[i]+1)/2.0)

ans = cml_sum[K-1]
for i in range(N-K):
    target = cml_sum[i+K] - cml_sum[i]
    if ans < target:
        ans = target

print(ans)

Submission status: Accepted

Solution code:
import numpy as np

N,K,*P = map(int,open(0).read().split())
E = np.cumsum([(P[i]+1)/2 for i in range(N)])#期待値の累積和

#初期値としてKまでの期待値の累積和を使用
#0始まりのためindexがK-1となることに注意
M = E[K-1]

for i in range(N-K):
  #E[i+K]-E[i]:O(1)でsum(P[i:i+K]):O(K)と同じ計算をする
  #forループと合わせると後者はO(NK)，N<=K<=2*10e6のためTLEする
  if M < E[K+i]-E[i]:
    M = E[K+i]-E[i]

print(M)

Submission status: Accepted

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

res = sum(p[:K])
res_max = res
i_max = 0
for i in range(1, N-K+1):
    res += p[i+K-1] - p[i-1]
    if res > res_max:
        res_max = res
        i_max = i

ans = 0
for j in range(K):
    ans += (p[i_max + j] + 1) / 2
print(ans)

Submission status: Accepted

Solution code:
import queue

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

queue = queue.Queue()
currentSum = 0
maxSum = 0
for i in range(len(p)):
    currentSum = currentSum + p[i] + 1
    queue.put(p[i] + 1)
    if i >= K:
        currentSum = currentSum - queue.get()

    if i >= K - 1:
        maxSum = max(maxSum, currentSum)

print("{:.12f}".format(maxSum / 2))

Submission status: Accepted

Solution code:
import queue

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

for i in range(len(p)):
    p[i] = p[i] + 1

queue = queue.Queue()
currentSum = 0
maxSum = 0
for i in range(len(p)):
    currentSum = currentSum + p[i]
    queue.put(p[i])
    if i >= K:
        currentSum = currentSum - queue.get()

    if i >= K - 1:
        maxSum = max(maxSum, currentSum)

print("{:.12f}".format(maxSum / 2))

Submission status: Accepted

Solution code:
import queue

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

for i in range(len(p)):
    p[i] = p[i] + 1

queue = queue.Queue()
currentSum = 0
maxSum = 0
for i in range(len(p)):
    currentSum = currentSum + p[i]
    queue.put(p[i])
    if queue.qsize() > K:
        currentSum = currentSum - queue.get()
    
    if queue.qsize() == K:
        maxSum = max(maxSum, currentSum)

print("{:.12f}".format(maxSum / 2))

Submission status: Accepted

Solution code:
import numpy as np

N,K,*P = map(int,open(0).read().split())
P = [(P[i]+1)/2 for i in range(N)]
P = np.cumsum(P)
M = P[K-1]
#print(P)
for i in range(N-K):
  #print(P[i+K],P[i])
  if M < P[i+K]-P[i]:
    M = P[i+K]-P[i]
print(M)

Submission status: Accepted

Solution code:
n,k =map(int,input().split())
p = list(map(int,input().split()))
kitai = []
for i in range(n):
    sum_k = 0
    sum_k = (1 + p[i])/2
    kitai.append(sum_k)
ans = []
sum_ans = 0
for i in range(k):
    sum_ans += kitai[i]
ans.append(sum_ans)
j = 0
cnt = 0
for i in range(k,len(kitai)):
    sum_ans = ans[cnt]
    sum_ans -=kitai[j] 
    sum_ans += kitai[i]
    j +=1
    cnt+=1
    ans.append(sum_ans)
print(max(ans))

Submission status: Accepted

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

Submission status: Accepted

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

p = list(map(lambda x: x * (x+1) /2 /x, p))

for i in range(1, n):
    p[i] = p[i-1] + p[i]

m = p[k-1]
for i in range(k, n):
    a = p[i] - p[i-k]
    if m < a:
        m = a

print(m)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
p = list(map(int,input().split()))
wa = sum(p[0:k])
next_wa = wa
for i in range(n-k):
    next_wa = next_wa - p[i] + p[i+k]
    if  next_wa > wa:
        wa = next_wa
print(0.5*(wa+k))

Submission status: Accepted

Solution code:
n,k = map(int, input().split())
p = [int(x) for x in input().split()]

li = []
count=0
ans = 0

for i in range(len(p)):
    p[i] += 1
    li.append(p[i])
    if len(li) < k:
        continue
    elif len(li) == k:
        max = sum(li)
        buf = max
    elif len(li) > k:
        tmp = buf - li[count] + li[-1]
        buf = tmp
        if tmp >= max:
            max = tmp
        count+=1

print(max/2)

Submission status: Accepted

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

scope_index = 0
max_sum = 0
for i in range(k):
    max_sum += p_list[i]

now_sum = max_sum
for p_i in range(k, len(p_list)):
    now_sum -= p_list[p_i - k]
    now_sum += p_list[p_i]

    if max_sum < now_sum:
        scope_index = p_i
        max_sum = now_sum

ex = (max_sum+k)/2
print(ex)

Submission status: Accepted

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

N, K = map(int, readline().split())
A = np.array(readline().split(), dtype=np.int64) + 1


Acum = np.zeros(N+1, np.float64)
Acum[1:] = A.cumsum()

x = Acum[K:] - Acum[:-K]
print(x.max()/2)

Submission status: Accepted

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

N, K = map(int, readline().split())
A = np.array(readline().split(), dtype=np.int64)
A = np.array([(1+a)/2 for a in A])

Acum = np.zeros(N+1, np.float64)
Acum[1:] = A.cumsum()

x = Acum[K:] - Acum[:-K]
print(x.max())

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
p = [int(i) for i in input().split()]
expp = [(i + 1) / 2 for i in p]
cumu, cumu_expp = 0, []
for i in expp:
    cumu += i
    cumu_expp.append(cumu)

max_expp = cumu_expp[k - 1]
for i in range(n - k):
    sumpk = cumu_expp[i + k] - cumu_expp[i]
    if max_expp < sumpk:
        max_expp = sumpk
print(max_expp)

Submission status: Accepted

Solution code:
import math

n,k = input().split()
p = input().split()

n = int(n)
k = int(k)
#p = [int(s) for s in p]

#print(p)

ex =0
ext = []
ext2 = []
for f in range(n):
    pi = int(p[f])
    xs =(pi+1)/2
    ext.append(xs)

ext2.append(ext[0])
for i in range(1,n):
    ext2.append(ext2[i-1]+ext[i])

ex = ext2[k-1]
for j in range(1,n-k+1):
    ext3 =ext2[j+k-1]-ext2[j-1]
    if ext3 > ex: ex = ext3

print('{:.12f}'.format(ex))

Submission status: Accepted

Solution code:
N,K,*P = map(int,open(0).read().split())
P = [(P[i]+1)/2 for i in range(N)]
M = m = sum(P[:K])

for i in range(N-K):
  if M < m-P[i]+P[i+K]:
    M = m-P[i]+P[i+K]
  m= m-P[i]+P[i+K]

print(M)

Submission status: Accepted

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

E = []
value=0
#期待値の計算,累積和の計算
for P_i in p:
    value += (1+P_i)/2
    E.append(value)

flag = E[K-1]
#隣接するK項の計算
for k in range(K,N):
    S = E[k] - E[k-K]
    if flag < S:
        flag = S
print(format(flag,'.12f'))

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
P = list(map(int,input().split()))
E = [(p+1)/2 for p in P]
temp = sum(E[0:K])
S =  temp
for i in range(N-K):
  temp -= E[i]
  temp += E[i+K]
  if S < temp:
    S = temp  
print(S)

Submission status: Accepted

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

expect = [(e + 1) / 2 for e in A]
window = sum(expect[0:K])
max_s = window
for i in range(N - K):
    window -= expect[i]
    window += expect[i + K]
    if window > max_s:
        max_s = window
print(max_s)

Submission status: Accepted

Solution code:
s=list(map(int,input().split()))
t=list(map(int,input().split()))
c=s[1]
d=0
a=sum(t[0:c])
b=0
for j in range(s[0]-s[1]+1):
  if j==0:
    b=sum(t[:c])
    continue
  else:
    a+=(t[j+c-1]-t[j-1])
    b=max(b,a)
b+=s[1]
print(b/2)

Submission status: Accepted

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

sums = [0 for _ in range(n+1)]
for i in range(n):
    exp = (1 + l[i]) / 2
    sums[i+1] = sums[i] + exp

ans = 0
for idx in range(n-k+1):
    diff = sums[idx+k] - sums[idx]
    ans = max(ans, diff)

print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
list=list(map(int, input().split()))
a=[]
sum=0
for i in list:
    sum+=((i-1)*(1/2)+1)
    a.append(sum)
ma=a[K-1]
for i in range(N-K):
    ma = max(ma, a[i+K]-a[i])
print(ma)

Submission status: Accepted

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

S = [0]*(N+1)
for i in range(N):
  S[i+1] = S[i] + (1+p[i])/2

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

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
P = list(map(int, input().split()))
A = [0, 1.0]
for i in range(2, 1001):
    A.append(A[i-1]+0.5)
index = 0
tmp = sum(P[0:K])
B = [tmp]
for i in range(K, N):
    total = B[-1]-P[i-K]+P[i]
    if tmp < total:
        index = i-K+1
        tmp = total
    B.append(total)
ans = 0
for i in range(index, index+K):
    ans += A[P[i]]
print(ans)

Submission status: Accepted

Solution code:
n,k,*p=map(int,open(0).read().split())
s=m=k
for i in range(n):s+=p[i]-p[i-k]*(i>=k);m=max(m,s)
print(m/2)

Submission status: Accepted

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

def main():
    N, K = map(int, input().split())
    P = list(map(int, input().split()))

    tmp_max = sum(P[:K])
    tmp = sum(P[:K])
    for i in range(N-K):
        tmp += P[i+K]
        tmp -= P[i]

        if tmp > tmp_max:
            tmp_max = tmp

    print((tmp_max + K) / 2)

main()

Submission status: Accepted

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

pn_t = [0]
for i in range(N):
    pn_t.append(pn[i]+pn_t[i])

l = 0
for i in range(N-K+1):
    l = max(l, pn_t[K+i]-pn_t[i])
ans = (l+K)/2
print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
p = list(map(int, input().split()))
for i in range(n):
    p[i] = (1 + p[i]) / 2
sum = 0
for i in range(k):
    sum += p[i]
ans = sum
for i in range(k, n):
    sum -= p[i - k]
    sum += p[i]
    ans = max(ans, sum)
print('{:.10f}'.format(ans))

Submission status: Accepted

Solution code:
import sys
import numpy as np

val = np.fromstring(sys.stdin.buffer.read(), np.int64, sep=' ')
n,k = val[:2]
p_list = val[2:]

S = np.zeros(n+1, np.int64)
S[1:] = p_list.cumsum()

KS = S[k:] - S[0:-k]
print((KS.max()+k)/2)

Submission status: Accepted

Solution code:
import queue

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

for i in range(n):
    p[i] += 1

s = 0
mx = 0
q = queue.Queue()

for i in range(n):
    s += p[i]
    q.put(p[i])
    if q.qsize() > k:
        s -= q.get()
    if q.qsize() == k:
        mx = max(mx, s)
    
ans = float(mx) / 2.0
print(ans)

Submission status: Accepted

Solution code:
n,k,*p=map(int,open(0).read().split())
s=m=sum(p[:k])+k
for i in range(k,n):s+=p[i]-p[i-k];m=max(m,s)  
print(m/2)

Submission status: Accepted

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

dicesSum=[]
l1=ps[0:K]
dicesSum.append(sum(l1))

if K==N:
    exp= (K+ dicesSum[0])/2
    print(exp)
else:
    for i in range(1,N-K+1):
        dicesSum.append(dicesSum[i-1]-ps[i-1]+ps[i+K-1])
    max_value = max(dicesSum)
    exp= (K+ max_value)/2
    print(exp)

Submission status: Accepted

Solution code:
n,k,*p=map(int,open(0).read().split())
s=m=sum(p[:k])
for i in range(k,n):s+=p[i]-p[i-k];m=max(m,s)  
print((m+k)/2)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
p = list(map(int, input().split()))
s = [0] * (n+1)

for i in range(0, n):
    s[i+1] = s[i] + p[i]

s_max = -1
pos = 0
for i in range(n-k+1):
    ss = s[i+k] - s[i]
    if ss > s_max:
        s_max = ss
        pos = i

ans = 0.0
for i in range(pos, pos+k):
    ans += (p[i]+1) / 2

print(ans)

Submission status: Accepted

Solution code:
N, K = map(int,input().split())
P = [int(i) for i in input().split()]
e = [0]*N
L = [0]*(N-K+1)
for i in range(N):
  e[i] = (P[i]*(P[i]+1)/2)/P[i]
for i in range(K):
  L[0] += e[i]
for i in range(K,N):
  L[i-K+1] = L[i-K]-e[i-K]+e[i]
print(max(L))

Submission status: Accepted

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

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

    if ans is None or ans < s:
        ans = s

print(ans/2)

Submission status: Accepted

Solution code:
from sys import stdin
from itertools import accumulate
n,k = map(int,stdin.readline().rstrip().split())
li = list(map(int,stdin.readline().rstrip().split()))
ma = 0
lin = []
for i in li:
    lin.append((i+1)/2)
lis = [0]+list(accumulate(lin))
ma = 0
for i in range(n-k+1):
    if i+k > n:
        break
    l = lis[i+k]-lis[i]
    ma = max(ma,l)
print(ma)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
 
n, k = map(int, input().split())
p = list(map(int, input().split()))

summation = 0
exp_val = []
for i in range(n):
    summation += (p[i]+1)/2
    exp_val.append(summation)
exp_val.insert(0, 0)
#print(exp_val)

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

print(ans)

Submission status: Accepted

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

max_pos = 0
max_value = sum(P[:K])
tmp_sum = max_value
for i in range(N-K):
    tmp_sum = tmp_sum - P[i] + P[i+K]
#    print(i, max_value, tmp_sum, P[i:i+K], "-", P[i], "+", P[i+K])
    if tmp_sum > max_value:
        max_value = tmp_sum
        max_pos = i + 1

#print("--------", max_pos)
total = 0
for i in range(max_pos, max_pos + K):
    total += (P[i] + 1) / 2
#    print(i, total, sum(list(range(1, P[i] + 1))) / P[i])

print(total)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
p = list(map(int, input().split()))
ans = 0
now = sum(p[:k-1])
for i in range(n - k + 1):
    now += p[i + k - 1]
    if now > ans:
        ans = now
    now -= p[i]
ans += k
ans /= 2
print(ans)

Submission status: Accepted

Solution code:
n,k,*p=map(int,open(0).read().split())
p+=0,
for i in range(n):p[i]-=~p[i-1]
print(max(p[i+k]-p[i]for i in range(-1,n-k))/2)

Submission status: Accepted

Solution code:
import itertools

def solve():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    # スコアの累積和
    l = list(itertools.accumulate(A))

    score = sum(A[:M])
    for i in range(1, N-M):
        score = max(score, l[i+M] - l[i])
        
    ans = (M + score) / 2

    return ans

print(solve())

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
List = list(map(int,input().split()))
result = [(1+i)/2 for i in List]
Answer = 0
if N == 1:
  print(result[0])
  exit()
elif N == K:
  print(sum(result))
  exit()
base = [sum(result[0:K])]
for i in range(N-K):
  counter = base[i]-result[i]+result[i+K]
  if counter > Answer:
    Answer = counter
  base.append(counter)
print(Answer)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N,K=map(int,input().split())
P=list(map(int,input().split()))
kouho=0
def saikorokitaiti(A):
    return ((P[A]*(1+P[A])/2)/P[A])
kari=[]
hako=[]
kitaiti=0
if K==1:
    print(saikorokitaiti(P.index(max(P))))
    exit()
for i in range(K):
    hako.append(saikorokitaiti(i))
    kitaiti+=saikorokitaiti(i)
    kouho=kitaiti
b=0
for j in range(N-K+1):
    if j==0:
        continue
    elif j+K-1<N:
        hako.append(saikorokitaiti(j+K-1))
        kitaiti+=saikorokitaiti(j+K-1)
        kitaiti-=hako[b]
        b+=1
        kouho=max(kouho,kitaiti)
#print(kouho)
print(kouho)

Submission status: Accepted

Solution code:
import numpy as np

N, K = map(int, input().split())
x = np.array(list(map(float, input().split())))

for i in range(N):
	x[i] = (1 + x[i]) / 2

data = np.sum(x[:K])
ans = data

for i in range(N-K):
	data = data + x[i+K] - x[i]
	if data > ans:
		ans = data

print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
p=list(map(int,input().split()))
l=[sum(p[:k])]

for i in range(n-k):
    l1=l[i] - p[i] + p[i+k]
    l.append(l1)

print((max(l)+k)/2)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, K: int, p: "List[int]"):
    M = m = sum(p[:K])
    for i in range(N-K):
        m = m - p[i] + p[i + K]
        M = max(M, m)
    print((1*K+M)/2)



# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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
    p = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, K, p)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

for i in range(len(p)):
    p[i] = (p[i] + 1) / 2

sum = 0
S = [0]

for i in p:
    sum += i
    S.append(sum)

# print(S)

max = 0

for i in range(len(p) - K + 1):
    s = S[i + K] - S[i]
    # print(s)
    if max < s:
        max = s

print(max)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
p = [(int(i)+1)/2 for i in input().split()] #期待値にして格納

#累積和を求める
for i in range(1,n):
    p[i]=p[i-1]+p[i]
mx = p[k-1]
for i in range(k,n):
    a = p[i] - p[i-k]
    if a > mx:
        mx = a
        
print(mx)

Submission status: Accepted

Solution code:
n, k, *p = map(int, open(0).read().split())

q = []
for p_i in p:
  q.append((p_i+1)/2)
  
s = [0]
pre_s = 0
for q_i in q:
  pre_s += q_i
  s.append(pre_s)

ans = 0
for i in range(n-k+1):
  if ans < (s[i+k] - s[i]):
    ans = s[i+k] - s[i]
    
print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
p = list(map(int, input().split()))
a = [0 for i in range(n)]

for i in range(n):
	a[i] = (p[i]*(p[i]+1)//2)/p[i]
s = sum(a[:k])
mx = s
for j in range(k,n):
	s += a[j]
	s -= a[j-k]
	mx = max(mx,s)
	#print (mx)
print (mx)

Submission status: Accepted

Solution code:
import numpy as np
 
def main():
    N, K = map(int, input().split(" "))
    ps = np.array(input().split(" "))
    ps = ps.astype("int64")
 
    ps_means = np.zeros(N)
    maxval = 0
 
    for i in range(N):
        ps_means[i] = ((1 + ps[i]) * ps[i])/ (2 * ps[i])
        if i + 1 >= K:
            if i + 1 == K:
                sumval = np.sum(ps_means[i-K+1:i+1])
            else:
                sumval -= ps_means[i-K]
                sumval += ps_means[i]
            if sumval > maxval:
                maxval = sumval
 
    ans = maxval
    print(ans)
 
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import accumulate

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

q=[0]+p
q=list(accumulate(q)) 

ans=[]
for i in range(N-K+1):
    ans.append(((q[i+K]-q[i])+K)*0.5)

print(max(ans))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)

def InMap(): return list(map(int, sys.stdin.readline().split(' ')))
def In(): return int(sys.stdin.readline())
def InS(): return sys.stdin.readline()

N, K = InMap()
P = InMap()

tmp = sum(P[0:K])
Res = [0]*(N-K+1)
for i in range(K, N):
    Res[i - K] = tmp
    tmp -= P[i - K]
    tmp += P[i]
Res[-1] = tmp
print((max(Res) + K) / 2)

Submission status: Accepted

Solution code:
import numpy as np
 
def main():
    N, K = map(int, input().split(" "))
    ps = np.array(input().split(" "))
    ps = ps.astype("int64")
 
    ps_means = np.zeros(N)
    maxval = 0
 
    for i in range(N):
        ps_means[i] = ((1 + ps[i]) * ps[i])/ 2
        if i + 1 >= K:
            if i + 1 == K:
                sumval = np.sum(ps_means[i-K+1:i+1] / ps[i-K+1:i+1])
            else:
                sumval -= ps_means[i-K] / ps[i-K]
                sumval += ps_means[i] / ps[i]
            if sumval > maxval:
                maxval = sumval
 
    ans = maxval
    print(ans)
 
if __name__ == '__main__':
    main()