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:
#!/usr/bin/env python3
def main():
    def expected_val(limit):
        return (1 + limit) / 2

    N, K = map(int, input().split())
    P = [int(x) for x in input().split()]

    lst = [0]
    res = 0
    for p in P:
        res += p + 1
        lst.append(res)
    ans = 0
    for i in range(N - K + 1):
        res = lst[i + K] - lst[i]
        ans = res if res > ans else ans
    print(ans / 2)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,K= map(int,input().split())
p = list(map(int,input().split()))
sum1=0.0
for i in range (K):
    sum1=((p[i]+1)/2.0)+sum1
sum2=sum1
for i in range(N-K):
    sum1=sum1+((p[i+K]-p[i])/2.0)
    if sum1>sum2:
        sum2=sum1
print(sum2)

Submission status: Accepted

Solution code:
N,K=map(int, input().split())
P=list(map(int, input().split()))
saikoro=[1+0.5*sai for sai in range(1000)]

ruiseki=0
for i in range(K):
	ruiseki+=saikoro[P[i]-1]

ans=ruiseki
for k in range(N-K):
	ruiseki=ruiseki-saikoro[P[k]-1]+saikoro[P[K+k]-1]
	ans=max(ans,ruiseki)
	
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Mon Sep  7 22:29:36 2020

@author: liang
"""
N, K = map(int, input().split())

P = [1 + (int(p)-1)*0.5 for p in input().split()]
#print(P)

tmp = sum(P[:K])
ans = tmp
for i in range(N-K):
    tmp += P[K+i] - P[i]
    if tmp > ans:
        ans = tmp
    
print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
nums = list(map(int, input().split()))
expect = 0
answer = 0
for i in range(N):
  if i < K:
    expect += (nums[i]+1)/2
  else:
    expect += (nums[i]+1)/2 - (nums[i-K]+1)/2
  answer = max(answer, expect)
print(answer)

Submission status: Accepted

Solution code:
import sys
from sys import exit
from collections import deque
from bisect import bisect_left, bisect_right, insort_left, insort_right #func(リスト,値)
from heapq import heapify, heappop, heappush
from math import *

sys.setrecursionlimit(10**6)
INF = 10**20
eps = 1.0e-20
MOD = 10**9+7

def mint():
    return map(int,input().split())
def lint():
    return list(map(int,input().split()))
def ilint():
    return int(input()), list(map(int,input().split()))
def judge(x, l=['Yes', 'No']):
    print(l[0] if x else l[1])
def lprint(l, sep='\n'):
    for x in l:
        print(x, end=sep)

N,K = mint()
p = lint()

ans = sum(p[:K])
tmp = ans
for i in range(K,N):
    tmp = tmp-p[i-K]+p[i]
    ans = max(ans,tmp)
print((ans+K)/2)

Submission status: Accepted

Solution code:
def main():
	N, K = [int(x) for x in input().split(" ")]
	P = [int(p) for p in input().split(" ")]
	E = [sum(P[:K])]
	for i in range(N - K):
		E.append(E[-1] - P[i] + P[i + K])
	print((max(E) + K)/2)

main()

Submission status: Accepted

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

ruisekiwa = [0]

for P in Ps:
    ruisekiwa.append(P + ruisekiwa[-1])

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

Submission status: Accepted

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

a = [1+(i-1)/2 for i in p]
l = sum(a[:k])
ans = l
for i in range(1, n-k+1):
    l = l-a[i-1]+a[k+i-1]
    ans = max(ans, l)
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] = p[i] / 2 + 0.5

s = 0
for i in range(K):
    s += p[i]
maxSum = s
j = 0

for i in range(K, N):
    s = s + p[i] - p[i-K]
    maxSum = max(maxSum, s)
print(maxSum)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# coding: utf-8
# 隣接するK個のサイコロの和が大きいものを探す

nk = input().split()
N = int(nk[0])
K = int(nk[1])

Ps = [int(p) for p in input().split()]

# 累積和にしてもいいし、1つずつスライドして求めてもいい気がする

max_sum = sum(Ps[:K])
current_sum = max_sum

# K+1 ~ N-1 までスライドして見ていく
for i in range(K, N):
    current_sum -= Ps[i-K]
    current_sum += Ps[i]

    max_sum = max(max_sum, current_sum)


# 1~pのサイコロの期待値: ((1+p) * p / 2) / p = (1 + p) / 2
ans = 1.0 * (max_sum + K) / 2
print(ans)

Submission status: Accepted

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

#期待値 : (p+1)//2
range_total = sum(P[:K]) + K
max_value = range_total
for i in range(N-K):
    range_total += P[K+i] - P[i]
    max_value = max(max_value, range_total)
print(max_value / 2)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
ps = list(map(int,input().split()))
su = sum(ps[0:K])
ksum = su
ind = 0
for i in range(1,N-K+1):
    ksum -= ps[i-1]
    ksum += ps[i+K-1]
    if ksum > su:
        ind = i
        su = ksum
ki = 0

for i in range(ind, ind+K):
    ki += (ps[i]*(ps[i]+1))/2/ps[i]
print(ki)

Submission status: Accepted

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

Submission status: Accepted

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

cnt = 0

for i in range(K):
    cnt += p[i]
ans = cnt
for i in range(1,N-K+1):
    cnt -= p[i-1]
    cnt += p[K+i-1]
    ans = max(cnt,ans)


print((ans+K)/2)

Submission status: Accepted

Solution code:
nk = input().split()
n = int(nk[0])
k = int(nk[1])
p_s = input().split()
p = [int(s) for s in p_s]
max_val = 0
for i in range(0,k):
    max_val+=p[i]
tmp = max_val
for i in range(k,len(p)):
    tmp = tmp - p[i-k] + p[i]
    if tmp > max_val:
        max_val=tmp
print(max_val/2 + 0.5 * k)

Submission status: Accepted

Solution code:
def expect(n):
        return (n+1)/2

nk = input().split()
N = int(nk[0])
K = int(nk[1])
p = input().split()

tmp = 0
for i in range (K):
    tmp += expect(int(p[i]))

tmpMax = tmp

for i in range(N - K):
    tmp -= expect(int(p[i]))
    tmp += expect(int(p[i+K]))
    tmpMax = max(tmpMax, tmp)

print(tmpMax)

Submission status: Accepted

Solution code:
def rsum(n):return (n+1)*(n//2)+((n+1)//2) if n%2 else (n+1)*(n//2)
N,K=map(int,input().split())
p=list(map(int,input().split()))
l=[0]*N
for i in range(N):l[i]=rsum(p[i])*(1/p[i])
s=sum(l[0:K])
ans=0
for i in range(N-K):
    ans=max(ans,s)
    s-=l[i]
    s+=l[i+K]
print(max(ans,s))

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
import numpy as np
def main():
    n, k = map(int, input().split())
    p = np.array(read().split(), np.int32)
    p += 1
    pcum = np.zeros(n + 1, np.int32)
    pcum[1:] = p.cumsum()
    sum_k = pcum[k:] - pcum[:-k]
    print(sum_k.max()/2)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from itertools import accumulate
def main():
    n, k, *p = map(int, read().split())
    p2 = [0] + [(1 + pe) / 2 for pe in p]
    r = 0
    p2a = tuple(accumulate(p2))
    for i1 in range(k, n+1):
        r = max(r, p2a[i1] - p2a[i1-k])
    print(r)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,k = map(int, input().split())
p = list(map(lambda x: (int(x)+1)/2, input().split()))

t = sum(p[:k])
ans = t
for i in range(k,n):
  t += p[i] - p[i-k]
  if ans < t: ans = t
print(ans)

Submission status: Accepted

Solution code:
n, k = map(int,input().split())
p = list(map(int,input().split()))
mu = [(a+1)/2 for a in p]
maxsum = sum(mu[:k])
now = maxsum
left = 0
right = k
while right<n:
    now = now+mu[right]-mu[left]
    if maxsum<now:
        maxsum = now
    left += 1
    right += 1
print(maxsum)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
P = list(map(int,input().split()))
ls = [0] * (N + 1)

for i in range(N):
  ls[i+1] += ls[i] + (P[i] + 1) / 2
  
ans = 0
for j in range(N-K+1):
  tmp = ls[K+j] - ls[j]
  ans = max(ans, tmp)
  
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

# すると結局[(p_1+1)/2,...,(p_N+1)/2]の配列から、隣接するK個の和の最大値を求めればよい
# N=10^5なので、O(N)で解く
# 2重ループはO(NK)で間に合わない
# 累積和を用いるとO(N)で解ける！（累積和とは、配列上の区間の総和を求める処理を高速化する手法）
S = [0]*(N+1)
for i in range(N):
  S[i+1] = S[i] + p[i]
'''
S[0] = 0
S[1] = p[0]
S[2] = p[0] + p[1]
S[N] = p[0] + ... + p[N-1]
 
S[K]-S[0] = p[K-1] + ... + p[0]
S[K+1]-S[1] = p[K] + ... + p[1]
S[K+2]-S[2] = p[K+1] + ... + p[2]
S[N]-S[N-K] = p[N-1] + ... + p[N-K]
'''
 
ans = 0 # ans = max(S[K]-S[0],S[K+1]-S[1],...,S[N]-S[N-K])
for i in range(N-K+1):
  ans = max(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()))
  
# 「和の期待値」は「期待値の和」なので、期待値を求めておく
for i in range(N):
  p[i] = (1+p[i])/2

# すると結局[(p_1+1)/2,...,(p_N+1)/2]の配列から、隣接するK個の和の最大値を求めればよい
# N=10^5なので、O(N)で解く
# 2重ループは間に合わない・・・累積和！
# 累積和によって、配列上の区間の総和を求める処理を高速化！
S = [0]*(N+1)
for i in range(N):
  S[i+1] = S[i] + p[i]
'''
S[0] = 0
S[1] = p[0]
S[2] = p[0] + p[1]
S[N] = p[0] + ... + p[N-1]

S[K]-S[0] = p[K-1] + ... + p[0]
S[K+1]-S[1] = p[K] + ... + p[1]
S[K+2]-S[2] = p[K+1] + ... + p[2]
S[N]-S[N-K] = p[N-1] + ... + p[N-K]
'''

ans = 0
# max(S[K]-S[0],S[K+1]-S[1],...,S[N]-S[N-K]) を求める
for i in range(N-K+1):
  ans = max(ans, S[i+K] - S[i])
  
print(ans)

Submission status: Accepted

Solution code:
from functools import reduce
n, k = [int(i) for i in input().split()]
p = [int(i) for i in input().split()]
tmp_max = sum([i / 2 + 0.5 for i in p[0:k]])
tmp = tmp_max
idx = 0
for i in range(1, len(p) - k + 1):
	tmp -= p[i - 1] / 2 + 0.5
	if i + k - 1 < len(p):
		tmp += p[i + k - 1] / 2 + 0.5
	tmp_max = max(tmp_max, tmp)
print(tmp_max)

Submission status: Accepted

Solution code:
N, K = [int(s) for s in input().split(' ')]
P = [int(s) for s in input().split(' ')]
s = []
a = sum(P[0:K])
s.append(a)
for p0, p1 in zip(P, P[K:]):
    a = a - p0 + p1
    s.append(a)

print((max(s) + K) / 2)

Submission status: Accepted

Solution code:
import os, sys, re, math


def get_exp_value(number):
    if number == 0:
        return 0
    a = (number + 1) / number
    exp = a * (number // 2)
    if number % 2 != 0:
        exp += a / 2

    return exp


(N, K) = [int(n) for n in input().split()]
P = [int(n) for n in input().split()]

exps = [get_exp_value(i) for i in range(200001)]

s = sum(P[0:K])
max_sum = 0
max_pos = 0
for i in range(K, N):
    s = s - P[i - K] + P[i]
    if s > max_sum:
        max_sum = s
        max_pos = i

answer = 0
for i in range(max_pos - K, max_pos):
    answer += exps[P[i + 1]]

print(answer)

Submission status: Accepted

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

Submission status: Accepted

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

# Piの期待値 (1 + Pi) // 2
E = list(map(lambda x: (x + 1) / 2, P))
E_SUMS = [E[0]]
for i in range(1, N):
    E_SUMS.append(E_SUMS[i - 1] + E[i])

m = E_SUMS[K - 1]
for i in range(K, N):
    m = max(m, E_SUMS[i] - E_SUMS[i - K])

print(m)

Submission status: Accepted

Solution code:
n, k = list(map(int, input().split(' ')))
aaa = list(map(int, input().split(' ')))
ans = 0
v = []
for a in aaa:
  v.append((a * (a + 1)) / (2.0 * a))

current = 0
for i in range(n):
  current += v[i]
  if i >= k:
    current -= v[i-k]
  ans = max(ans, current)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

s = sum(p[:K])
ss = []
ss.append(s)

for i in range(N - K):
    s = s - p[i] + p[i+K]
    ss.append(s)

print(K + (max(ss) - K) / 2)

Submission status: Accepted

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

e = sum(range(1,p[0]+1))/p[0]
S = [e]

for i in range(1,N):
    ex = p[i]*(p[i]+1) / (2*p[i])
    S.append(ex + S[i-1])

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

print(ans)

Submission status: Accepted

Solution code:
import itertools
 
n, k = map(int, input().split())
p = list(map(int, input().split()))
acc = [0] + list(itertools.accumulate([(x+1)/2 for x in p])) # 累積和を計算
 
ans = max(acc[i]-acc[i-k] for i in range(k, n+1)) # k番目からn番目まで計算
print(ans)

Submission status: Accepted

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

p_list_E = []
p_list_E_temp = [1, 1.5, 2, 2.5, 3, 3.5]

for i in range(len(p_list)):
    p_list_E.append((p_list[i]+1)*0.5)
#print(p_list_E)

p_list_sum = [0]
for i in range(0,N):
    p_list_sum.append(p_list_sum[i]+p_list_E[i])
#print(p_list_sum)

ans = 0
for i in range(K,N+1):
    ans = max(ans, p_list_sum[i]-p_list_sum[i-K])
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

# 累積和
S = [0]*N
S[0] = p[0]
for i in range(N-1):
  S[i+1] = S[i] + p[i+1]

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

print(ans)

Submission status: Accepted

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

kitai = [0]*1000
tmp = 0
for i in range(1000):
  tmp += i+1
  kitai[i] = tmp/(i+1)
#print(kitai)

total_kitai = [0]*(n+1)
tmp = 0
for i in range(n):
  tmp += kitai[p[i]-1]
  total_kitai[i+1] = tmp
#print(total_kitai)

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

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    N, K = map(int, readline().split())
    P = [0] + list(map(int, readline().split()))

    cur = sum(P[:K])
    s_max = 0

    for i in range(N - K + 1):
        cur += P[K + i]
        cur -= P[i]
        s_max = max(s_max, cur)

    print((s_max + K) / 2)


if __name__ == '__main__':
    main()

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):# O(N)
    s[i+1] = s[i] + P[i]

# [j,j+K) の和の最大値と j を保持 
m = 0
midx = 0
for j in range(N-K+1):# O(N)
    v = s[j+K] - s[j]
    if v > m:
        m = v
        midx = j
        
E = 0
for k in range(midx,midx+K):# O(K)
    x = P[k]
    E += (1/x)*(x*(x+1)/2)
print(E)

Submission status: Accepted

Solution code:
def INT():
    return int(input())

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

def MI():
    return map(int, input().split())

N, K = MI()
p = LI()

def E(x):
    return (x + 1) / 2

for i in range(N):
    p[i] = E(p[i])
    
ans = sum(p[:K])
E_K = ans

for i in range(N - K):
    E_K += p[i + K] - p[i]
    ans = max(ans, E_K)

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,k=[int(i) for i in input().split()]
p=[(int(i)+1)/2 for i in input().split()]

ans=0
sum_num=sum(p[:k])
for i in range(n-k+1):
    if i==0:
        sum_num = sum(p[:k])
    else:
        sum_num+=p[i+k-1]-p[i-1]
    ans=max(ans,sum_num)
print(ans)

Submission status: Accepted

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

P = [((x+1) * x / 2) / x for x in P]
A = list(accumulate(P))

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

print(ans)

Submission status: Accepted

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

A = list(accumulate(P))

largest = A[K-1]
point = 0
for i in range(K, N):
    if largest < A[i] - A[i-K]:
        largest = A[i] - A[i-K]
        point = i

ans = 0
for j in range(point - K + 1, point+1):
    p = P[j]
    ans += (((p + 1) * p) / 2) / p

print(ans)

Submission status: Accepted

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

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

ans = (a + K) / 2
print(ans)

Submission status: Accepted

Solution code:
import sys

N,K=map(int,input().split())
P=list(map(int,input().split()))
Q=[(1+p)/2 for p in P]
temp=sum(Q[:K])
ans=temp
for i in range(N):
  try:
    temp=temp-Q[i]+Q[i+K]
    ans=max(ans,temp)
  except:
    pass
else:
  print(ans)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc154/tasks/abc154_d
import sys
# sys.setrecursionlimit(100000)


def input():
    return sys.stdin.readline().strip()


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def main():
    n, k = input_int_list()
    P = [0] + input_int_list()
    expected_sum = [0] * (n + 1)
    # pre-process
    for i in range(1, n + 1):
        exp = (P[i] + 1) / 2
        expected_sum[i] = expected_sum[i - 1] + exp
    ans = 0
    # query from cusum
    for i in range(k, n + 1):
        ans = max(ans, expected_sum[i] - expected_sum[i - k])
    print(ans)
    return


if __name__ == "__main__":
    main()

Submission status: Accepted

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

res = 0

P2 = []
for i in P:
  P2.append(0.5 * (i + 1))
num = 0
for i in range(K):
  num += P2[i]
res = num
for i in range(1,N-K+1):
  temp = num + P2[i+K-1] - P2[i-1]
  if temp > res:
    res = temp
  num = temp
  
print(res)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
P = [(int(x)+1)/2 for x in input().split()]

total=ans=sum(P[:K])
for n in range(K,N):
  total+=P[n]-P[n-K]
  ans=max(ans, total)

print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
P = [(int(x)+1)/2 for x in input().split()]

Q=[0]*(N+1)
for n in range(N):
  Q[n+1]=Q[n]+P[n]

ans=0
for n in range(K,N+1):
  ans=max(ans, Q[n]-Q[n-K])

print(ans)

Submission status: Accepted

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

q = sum(p[:K])
ans = q
for i in range(K, N):
    q = q + p[i] - p[i - K]
    ans = max(ans, q)
print((ans+K)/2)

Submission status: Accepted

Solution code:
import bisect,collections,copy,itertools,math,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
def main():
    n,k = LI()
    p = LI()
    for i,x in enumerate(p):
        if x%2 == 0:
            x = x//2+0.5
        else:
            x = x//2+1
        p[i] = x

    nowsum = sum(p[:k])
    ans = nowsum
    for i in range(k,n):
        nowsum = nowsum - p[i-k] + p[i]
        # print(p,lst)
        ans = max(ans,nowsum)
    
    print(ans)
main()

Submission status: Accepted

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

arr = [0]*n
for i in range(n):
  arr[i] = (A[i]+1)/2

s = sum(arr[:k])
ans = s
for j in range(n-k):
  s = s - arr[j] + arr[j+k]
  ans = max(s,ans)
print(ans)

Submission status: Accepted

Solution code:
# import itertools
# import math
# import sys
# sys.setrecursionlimit(500*500)
# import numpy as np

# N = int(input())
# S = input()
# n, *a = map(int, open(0))
N, K = map(int, input().split())
P = list(map(int, input().split()))
# B = list(map(int, input().split()))
# tree = [[] for _ in range(N + 1)]
# B_C = [list(map(int,input().split())) for _ in range(M)]
# S = input()

# B_C = sorted(B_C, reverse=True, key=lambda x:x[1])
# all_cases = list(itertools.permutations(P))
# a = list(itertools.combinations_with_replacement(range(1, M + 1), N))
# itertools.product((0,1), repeat=n)

# A = np.array(A)
# cum_A = np.cumsum(A)
# cum_A = np.insert(cum_A, 0, 0)

# def dfs(tree, s):
#     for l in tree[s]:
#         if depth[l[0]] == -1:
#             depth[l[0]] = depth[s] + l[1]
#             dfs(tree, l[0])
# dfs(tree, 1)

E = [0]
tot = 0
for p in P:
    tot += (p + 1) / 2
    E.append(tot)


m = 0
for i in range(N - (K - 1)):
    _ = E[i + K] - E[i]
    if _ > m:
        m = _

print(m)

Submission status: Accepted

Solution code:
N, K = map(int,input().split())
p = list(map(int,input().split()))
 
exp = [(x+1)/2 for x in p]
 
sums = 0
ls =[0]

for n in range(N):
  sums += exp[n]
  ls.append(sums)

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

  ans_candidate = ls[n+K]-ls[n]

  if ans < ans_candidate:
    ans = ans_candidate 
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

ans = []

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

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

print(t/2)

Submission status: Accepted

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

kitai = [(1+p[i])/2 for i in range(n)]

total = sum(kitai[i] for i in range(k))
ans = total

for i in range(0, n-k):
  total = total - kitai[i] + kitai[i+k]
  if total > ans:
    ans = total

print(ans)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
P=list(map(lambda x: (int(x)+1)/2,input().split()))
s=tmp=sum(P[:K])
for i in range(K,N):
  tmp=tmp-P[i-K]+P[i]
  s=max(s,tmp)
print(s)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
P=list(map(lambda x: (int(x)+1)/2,input().split()))
s=sum(P[:K])
tmp=s
for i in range(K,N):
  tmp=tmp-P[i-K]+P[i]
  if tmp>s:
    s=tmp
print(s)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())
def NIJIGEN(H): return [list(input()) for i in range(H)]
N,M=MAP()
L=LIST()
maxa=-(10**10)
sums=sum(L[:M])
maxa=max(maxa,sums)
for i in range(N-M):
  sums=sums-L[i]+L[i+M]
  maxa=max(maxa,sums)
print((maxa+M)/2)

Submission status: Accepted

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

l = []
for i in p:
    l.append((1/2*i*(i+1))/i)

s = [0]*len(l)
s[0] = l[0]
for i in range(1,len(l)):
    s[i] = s[i-1]+l[i]

ans = 0
for i in range(K,len(s)):
    ans = max(ans,s[i]-s[i-K])

if N == K:
    print(max(s))
    exit()

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
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
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


def sum_of_arithmetic_progression(s, d, n):
    return n * (2 * s + (n - 1) * d) // 2


def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


def lcm(a, b):
    g = gcd(a, b)
    return a / g * b


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

    v = []
    for i in range(N):
        v.append(sum_of_arithmetic_progression(1, 1, P[i]) / P[i])

    ans = 0.0
    tmp = 0.0
    for i in range(N):
        if i < K:
           tmp += v[i]
        else:
            tmp += v[i]
            tmp -= v[i - K]
        ans = max(ans, tmp)

    print(ans)


def main():
    solve()


if __name__ == '__main__':
    main()

Submission status: Accepted

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

p = [int(x) for x in input().split()]
p_kitaiti=[float((x+1)/2) for x in p]

ruisekiwa=[p_kitaiti[0]]

for i in range(1,len(p_kitaiti)):
    ruisekiwa.append(ruisekiwa[-1]+p_kitaiti[i])

ans=ruisekiwa[k-1]

for i in range(1,len(ruisekiwa)-k+1):
    ans=max(ans,ruisekiwa[i+k-1]-ruisekiwa[i-1])

print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
p = list(map(int, input().split()))
p = list(map(lambda x: (x + 1)/2, p))
ans = 0
for i in range(1, len(p)):
    p[i] += p[i - 1]
for i in range(K - 1, len(p)):
    if i == K - 1:
        ans = p[i]
    else:
        ans = max(ans, p[i] - p[i - K])
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

s = 0

for i in range(K):
    s += P[i]

s_max = s

for i in range(N - K):
    s = s - P[i] + P[i+K]
    if s > s_max:
        s_max = s

print((s_max + K) / 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 = P[i]
  p = (1+p)/2
  P[i] = p+P[i-1]
ans = 0
for i in range(N-K+1):
  ans = max(ans,P[i+K]-P[i])
print(ans)

Submission status: Accepted

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


def calc(x):
    return (x+1)/2


pe = []
for i in range(N):
    pe.append(calc(p[i]))

cs = [pe[0]] + [0]*(N-1)

for i in range(1, N):
    cs[i] = pe[i] + cs[i-1]

ans = cs[K-1]
for i in range(K, N):
    wa = cs[i] - cs[i-K]
    ans = max(ans, wa)

print(ans)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
import math
from collections import defaultdict,deque
from itertools import permutations
ml=lambda:map(int,input().split())
ll=lambda:list(map(int,input().split()))
ii=lambda:int(input())
ip=lambda:list(input())
ips=lambda:input().split()

"""========main code==============="""

t,k=ml()
n=ll()
ans=0
lol=0
for i in range(t):
    if(i>=k):
        lol+=((n[i]*(n[i]+1))//2)/n[i]
        lol-=((n[i-k]*(n[i-k]+1))//2)/n[i-k]
    else:
        lol+=((n[i]*(n[i]+1))//2)/n[i]
    ans=max(ans,lol)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def Csum(a):
    b,c=[0],0
    for i in range(len(a)):
        c+=a[i]
        b.append(c)
    return b
n,k=map(int,input().split())
p=Csum(list(map(int,input().split())))
ans=0
for i in range(n-k+1):
    ans=max(ans,p[i+k]-p[i])
print((ans+k)/2)

Submission status: Accepted

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

rui=[0]
for i in a:
  rui.append(rui[-1]+i)
hantei=0
for i in range(0,len(rui)-k):
  if hantei<=rui[i+k]-rui[i]:
    hantei=rui[i+k]-rui[i]
    l=i
    r=i+k
ans=0
for i in range(l,r):
  ans+=(a[i]+1)/2
  
print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
li=list(map(int,input().split()))
kai=[0]
for i in range(1,1001):
  kai.append(kai[i-1]+i)
ka=[0]+[kai[i]/i for i in range(1,len(kai))]
lis=[ka[i] for i in li]

ans=sum(lis[:k])
mx=ans
for i in range(len(li)-k):
  ans-=lis[i]
  ans+=lis[i+k]
  mx=max(ans,mx)
print(mx)

Submission status: Accepted

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

import numpy as np

data = np.array(p) + 1

Pcum = np.zeros(N + 1, np.int32)
Pcum[1:] = data.cumsum()

length_K_sums = Pcum[K:] - Pcum[0:-K]

print(np.max(length_K_sums)/2)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
p = list(map(int,input().split()))
math = [0]*N
ans = 0
check = 0
for i,j in enumerate(p):
    math[i] += (j*(j+1)/2)/j
    if(i+1<=K):
        check += math[i]
    else:
        check += math[i]
        check -= math[i-K]
    ans = max(ans,check)
print(ans)