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:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    #N = int(input())
    N, K = map(int, input().split())
    A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    k=K
    p=[(a+1)*0.5 for a in A]
    cur=sum(p[:k])
    ans=cur
    for i in range(1,N-K+1):
        cur=cur-p[i-1]+p[i+k-1]
        ans=max(cur,ans)
    print(ans)




if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def cumsum(xs):
    result = [xs[0]]
    for x in xs[1:]:
        result.append(result[-1] + x)
    return result

a,b=map(int,input().split())
c=list(map(int,input().split()))

if a==b:
    print((sum(c)+a)/2)
    exit()

d=[]

c=[(i+1)/2 for i in c]
n=cumsum(c)

m=[]
for i in range(0,a-b):
    m.append(n[i+b]-n[i])


print(max(m))

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
p = list(map(int, input().split()))
s = [0] * N

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

answer = sum(s[:K])
current = answer
for i in range(1, N - K + 1):
    current = current - s[i - 1] + s[i + K - 1]
    answer = max(answer, current)

print(answer)

Submission status: Accepted

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

E_P=[(1+p)/2 for p in P] 

E_P_sum=[0]
E_P_sum_=0
for n in range(N):
    E_P_sum_=E_P_sum_+E_P[n]
    E_P_sum.append(E_P_sum_)

max_ = 0
for k_ in range(len(P)-K+1):
    sum_=E_P_sum[k_+K]-E_P_sum[k_]
#     print(E_P_sum[k_+K],E_P_sum[k_],sum_)
    if max_ < sum_:
        max_=sum_
        
print(max_)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
p=list(map(int,input().split()))
num=[sum(p[0:k])]
def ap(num1):
    num.append(num1)
for i in range(n-k):
    ap(num[i]-p[i]+p[k+i])
print((max(num)+k)/2)

Submission status: Accepted

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

ans = 0
kitai = []
for i in range(n):
    kitai.append((1+p[i])/2)
wa = []
a = 0
for i in range(n):
    a += kitai[i]
    wa.append(a)
if n == k:
    print(wa[n-1])
    exit()
ans = 0
for i in range(n-k):
    ans = max(ans, wa[i+k] - wa[i])

print(ans)

Submission status: Accepted

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


mx = 0
for i in range(1,n-k+1):
    delta = psum[i+k-1] - psum[i-1]
    if mx < delta:
        mx = delta
print(mx/2)

Submission status: Accepted

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

A =[]
for i in range(N):
    A.append(P[i]+1)

from itertools import accumulate
B = list(accumulate(A))
#print(A)

ans = 0
if len(A) == K:
    ans = sum(A)/2
else:
    for i in range(K,N):
        ans=max(ans,(B[i]-B[i-K])/2)
print(ans)

Submission status: Accepted

Solution code:
n, kosuu = map(int, input().split(" "))
a=list(map(int, input().split(" ")))
first = sum(a[:kosuu])
temp = []
temp.append(first)
for i in range(n - kosuu):
  first = first + a[i + kosuu] - a[i]
  temp.append(first)
print((max(temp) + kosuu) / 2)

Submission status: Accepted

Solution code:
# import sys
# sys.setrecursionlimit(10 ** 6)
# from decorator import stop_watch
#
#
# @stop_watch
def solve(N, K, ps):
    ev = [0] *  (N + 1)       # Expected value
    cs = [0] * (N + 1)        # Cumulative sum
    for i, p in enumerate(ps, 1):
        ev[i] = (p + 1) / 2
        cs[i] = cs[i - 1] + ev[i]

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

    print(ans)


if __name__ == '__main__':
    N, K = map(int, input().split())
    ps = [int(i) for i in input().split()]

    # N, K = 200000, 2
    # ps = [i for i in range(1, 200000 + 1)]

    solve(N, K, ps)

Submission status: Accepted

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

ex = [0]*N

for i,p in enumerate(P):
    ex[i] = (p+1)*(1/2)

ex = [0] + ex
cumsum = np.cumsum(ex)

B = cumsum[K:] - cumsum[:-K]

print(np.max(B))

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
p = list(map(int,input().split()))
b = [(1 + p[i])/2 for i in range(n)]
 
ttl = sum(b[:k])
res = ttl
for i, v in enumerate(b[k:]):
    ttl += v - b[i]
    res = max(res, ttl)
 
print("{:.10f}".format(res))

Submission status: Accepted

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

ttl = sum(b[:k])
res = ttl
for i, v in enumerate(b[k:]):
    ttl += v - b[i]
    res = max(res, ttl)

print("{:.10f}".format(res))

Submission status: Accepted

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

kazu =[]
kai = []
kazu = [(a+1) /2 for a in m]
kitai = sum(kazu[0:int(k)])
ans = kitai


for x in range(int(n) - int(k)):
    kitai -= kazu[x]
    kitai += kazu[x + int(k)]
    if ans < kitai:
        ans = kitai

print(ans)

Submission status: Accepted

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

m = [(e + 1) / 2 for e in p]

t = sum(m[0:K])
result = t
for i in range(N - K):
    t -= m[i]
    t += m[i + K]
    if t > result:
        result = t
print(result)

Submission status: Accepted

Solution code:
def solve():
  N, K = map(int, input().split())
  A = list(map(int, input().split()))
  B = [1 + (A[i] - 1) * 0.5 for i in range(N)]
  total = sum(B[0:K])
  answer = total
  for i in range(N - K):
    total += B[i + K] - B[i]
    answer = max(answer, total)
  print(answer)
solve()

Submission status: Accepted

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

ans = 0
for i in range(0,K):
    ans += ex[p[i]-1]

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

Submission status: Accepted

Solution code:
from collections import deque, defaultdict

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

dice = [0]
for i in range(1000):
  dice.append(1 + 0.5 * i)
  
lis = [0]
sum = 0
for p in P:
  sum += dice[p]
  lis.append(sum)
  
ans = 0
for i in range(N - K + 1):
  ans = max(ans, lis[K+i] - lis[i])
print(ans)

Submission status: Accepted

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

p_t = [0]
for i in range(n):
    p_t.append(p_t[i] + p[i])

max_value = 0
max_index = 0
for i in range(n - k + 1):
    if max_value < p_t[i + k] - p_t[i]:
        max_value = p_t[i + k] - p_t[i]
        max_index = i

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

print(ans)

Submission status: Accepted

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

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

total = sum(p[:k])
ans = total
for i in range(n-k):
    total -= p[i]
    total += p[i+k]
    ans = max(total,ans)

print((ans+k)/2)

Submission status: Accepted

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

ps = list(map(lambda x: int(x) + 1, input().split()))



from collections import deque

q = deque()

tmp = sum(ps[:k])

q.append(tmp)



ps

for i in range(n-k):
    tmp = tmp - ps[i] + ps[k+i]
    q.append(tmp)



q

print(max(q)/2)

Submission status: Accepted

Solution code:
s = input().split()
n, k = int(s[0]), int(s[1])
l = input().split()
l = [int(i) for i in l]
#l = [17,13,13,12,15,20,10,13,17,11]
x = [(i+1)/2 for i in l]
#print(sum(p[-4:]))
#print(x)
#print(len(x))
p = []
p.append(x[0])
prev=0
for i in x[1:]:
    curr = p[prev]+i
    p.append(curr)
    prev += 1
#print(p)
#print(len(p))
#k=4
maxi = p[k-1]
for i in range(k,len(p)):
    maxi = max(maxi, p[i]-p[i-k])
print('%.9f'%maxi)

Submission status: Accepted

Solution code:
import numpy as np
import numpy

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

S = numpy.cumsum(P)
P.append(0)
M = S[K-1]

for i in range(0,N):
    if P[i+K] == 0:
        break
    A = S[i+K] - S[i]
    M = max(M, A)

ans = 0.5 * (M + K)

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from itertools import accumulate


n, k = map(int, input().split())
p = list(map(int, input().split()))
max_sum_k = 0
cum_sum = [0] + list(accumulate(p))
for i in range(k-1, n + 1):
    sum_p = cum_sum[i] - cum_sum[i-k]
    if sum_p > max_sum_k:
        max_sum_k = sum_p

max_ex = (k + max_sum_k) / 2
print(max_ex)

Submission status: Accepted

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

for i in range(k, n + 1):
    sum_p = cum_sum[i] - cum_sum[i-k]
    if sum_p > max_sum_k:
        max_sum_k = sum_p

max_ex = (k + max_sum_k) / 2
print(max_ex)

Submission status: Accepted

Solution code:
import collections

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

ans = 0
tmp = 0
q = collections.deque()
for i in range(n):
    e = (1+a[i])/2
    q.append(e)
    tmp += e
    if len(q) > k:
        tmp -= q.popleft()
    ans = max(ans,tmp)
print(ans)

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

def f(n):
    return (n * (n + 1) // 2) / n

acc = [0 for _ in range(N + 1)]

for i in range(N):
    acc[i + 1] = acc[i] + f(P[i])

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

Submission status: Accepted

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

Submission status: Accepted

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

total = 0
ans = 0
for i,a in enumerate(P):
    total += (a+1)/2
    if i >= k:
        total -= (P[i-k]+1)/2
    if i >= k-1:
        ans = max(total,ans)
    
print(ans)

Submission status: Accepted

Solution code:
import sys
n,k=map(int,input().split())
pp = list(map(int,input().split()))
s=[0]*n
for i,p in enumerate(pp):
  if i==0:
    s[0] = (1+p)/2
  else:
    s[i] = s[i-1]+(1+p)/2
res =0
if n==k:
  print(s[n-1])
  sys.exit()
for i in range(n-k):
  if res < s[i+k] - s[i]:
    res = s[i+k]-s[i]
print(res)

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()))
    ref = sum(p[:k])
    ans = ref

    for i in range(1, n - k + 1):
        ref = ref - p[i - 1] + p[i + k - 1]
        if ref > ans:
            ans = ref

    print(ans/2 + k*0.5)

main()

Submission status: Accepted

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

for num in P:
    S.append((num + 1) / 2)

ans = sum(S[0:K])
max_ans = ans

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

print(max_ans)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
_=input().split()
S=[]
for s in _:
    S.append((int(s)+1)/2) #初めから期待値で配列作成

ans=sum(S[0:K])
temp=ans

for i in range(N-K):
    temp=temp-S[i]+S[i+K]
    if ans<temp:
        ans=temp
    else:
        pass
    
print(ans)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
_=input().split()
S=[]
for s in _:
    S.append((int(s)+1)/2) #初めから期待値で配列作成

maxsum=sum(S[0:K])
tempsum=maxsum

for i in range(N-K):
    tempsum=tempsum-S[i]+S[i+K]
    if maxsum<tempsum:
        maxsum=tempsum
    else:
        pass

print(maxsum)

Submission status: Accepted

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

tmp = sum(Ps[:K])
ms = tmp

for i in range(K,N):
  tmp = tmp + Ps[i] - Ps[i-K]
  if ms < tmp:
    ms = tmp
    
print(ms)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
#from collections import deque

#期待値はΣ(from 1 to pi)/len(pi)
P = list(map(int,input().split()))
cumsum = [0]*(N+1)
counter = []
for k in range(N):
    cumsum[k+1]=cumsum[k]+P[k]

for i in range(N-K+1):
    counter.append(cumsum[i+K]-cumsum[i])

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

Submission status: Accepted

Solution code:
from collections import deque

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

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

max_sum = 0
for i in range(N-K+1):
    s = sum_list[i+K] - sum_list[i]
    if max_sum < s:
        max_sum = s

ans = (max_sum + K) / 2

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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

res = 0
for i in range(K,N+1):
  res = max(res, exp[i]-exp[i-K])

print(res)

Submission status: Accepted

Solution code:
import sys

def II(): return int(input())
def MI(): return map(int,input().split())
def LI(): return list(map(int,input().split()))
def TI(): return tuple(map(int,input().split()))
def RN(N): return [input().strip() for i in range(N)]


def main():
    N, K = MI()
    p = LI()

    sum_i = sum(p[0:K])
    max_ans = sum_i
    max_i = 0
    ans = 0
    for i in range(1, N-K+1):
        sum_i = sum_i - p[i-1] + p[K+i-1]
        #print(i,p[i-1],p[K+i-1])
        #print(sum_i)
        #for j in range(i+1,i+K):
        #    sum_i += p[j]
        #print("sum",sum_i)
        if max_ans <= sum_i:
            max_ans = sum_i
            max_i = i
    #print("max",max_i) 
    for j in range(max_i,max_i+K):
        #print("max_i",j)  
        ans += sum(range(1, p[j] + 1))/p[j]
    
    print(ans)




if __name__ == "__main__":
	main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
P=list(map(int,input().split()))
total=sum(P[:K])
maximum=sum(P[:K])
num=0
for i in range(N-K):
    m=total-P[i]+P[i+K]
    if m>=maximum:
        num=i+1
        maximum=m
    total=m
print(sum([1+(p-1)*0.5 for p in P[num:num+K]]))

Submission status: Accepted

Solution code:
# 難易度 484
# 800~
# 解法805,pi~pjの合計が最大となる区間を求める
# Kの区間が固定されているので0~K-1 -> N-K~N-1を足していイケば良い
# 2~10^5こしかNがないので，せいぜいO(N)で終わるので十分
# 期待値の計算をいちいちしていたら，計算量がもタンクなるかも？最初から計算しておくか
# なぜTLEが起こるのかがよくわからない

N, K = map(int,input().split())
P = list(map(int,input().split()))
P_MAX = 10**3
E = [0]*(P_MAX+1)
for i in range(1,P_MAX+1):
    E[i] = sum([1/i * j for j in range(1,i+1)])

ans = 0
for i in range(0,N-K+1):
    if i == 0:
        old = sum([E[l] for l in P[0:0+K]])
        ans = old
        continue
    new = old - E[P[i-1]] + E[P[i+K-1]]
    ans = max(ans,new)
    old = new
print(ans)

Submission status: Accepted

Solution code:
def main():
    N,K = map(int, input().split())
    P = list(map(int, input().split()))
    S = [0]*(N)

    for i in range(N):
        P[i] = P[i]+1

    S[0]=P[0]
    for i in range(1,N):
        S[i] = S[i-1] + P[i]

    m = S[K-1]

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

    print(m/2)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, K = map(int,input().split())
p = list(map(int,input().split()))
sumnation = sum(p[:K])
ans = sumnation
for i in range(N-K):
    sumnation -= p[i]
    sumnation += p[i+K]
    ans = sumnation if sumnation > ans else ans
ans = 0.5*K + 0.5*(ans)
print(ans)

Submission status: Accepted

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

L=[0]*(N-K+1)

target=0


for i in range(N-K+1):
    if i==0:
        for j in range(K):
            target+=S[j]
        L[0]=target
    else:    
        target+=S[K+i-1]-S[i-1]
        L[i]=target
best=max(L)    
print((best+K)/2)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from itertools import accumulate

n,k = map(int, input().split())
a = list(map(int, input().split()))
e_a = [(i+1)/2 for i in a] #それぞれの期待値
s_a = list(accumulate(e_a)) #期待値の累積和

res = 0
exp = 0
for i in range(k-1, n):
    if i == k-1:
        exp = s_a[i]
    else:
        exp = s_a[i] - s_a[i-k]
        
    res = max(res, exp) #最大期待値を更新

print(res)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
p=list(map(int,input().split()))
p=[(1+i)/2 for i in p]
ans=sum(p[0:K])
A=[ans]

for i in range(N-K):
  ans-=p[i]
  ans+=p[K+i]
  A.append(ans)
print(max(A))

Submission status: Accepted

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

M=[sum(p[:K])]
for i in range(1,N-K+1):
  tmp=M[-1]-p[i-1]+p[i+K-1]
  M.append(tmp)

ans=max(M)/2+K/2
print(ans)

Submission status: Accepted

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

exv = [(e+1)/2 for e in dices]
temp = sum(exv[0:K])
result = temp
for i in range(N-K):
    temp -= exv[i]
    temp += exv[i+K]
    if temp > result:
        result = temp
print(result)

Submission status: Accepted

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

Submission status: Accepted

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

lst=[0]
sum=0
for i in range(n):
    sum+=p[i]
    lst.append(sum)
    
ans=[]
for i in range(n-k+1):
    ans.append(lst[i+k]-lst[i])

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
ls=list(map(int,input().split()))
ls_p=[(ls[i]+1)/2 for i in range(N)]
a=0
for i in range(K):
  a+=ls_p[i]
b=a  
for i in range(N-K):
  c=a+ls_p[i+K]-ls_p[i]
  b=max([b,c])
  a=c
print(b)

Submission status: Accepted

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

E = [(1+p)/2 for p in P]
S = [0]
for i in range(len(E)):
    S.append(S[i] + E[i])

for j in range(K, len(S)):
    ans = max(ans, S[j]-S[j-K])
print(ans)

Submission status: Accepted

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

for i in p:
    temp = (1+i)/2
    e.append(temp)
    if len(ruiseki) == 0:
        ruiseki.append(temp)
    else:
        ruiseki.append(ruiseki[len(ruiseki)-1] + temp)

e_sum = []

for i in range(n-k+1):
    if i == 0:
        e_sum.append(ruiseki[i+k-1])
    else:
        e_sum.append(ruiseki[i+k-1] - ruiseki[i-1])

print(max(e_sum))

Submission status: Accepted

Solution code:
N, K = map(int,input().split())
P = list(map(int,input().split()))
prob = [0 for _ in range(N)]
for i in range(N):
    prob[i] = (P[i]+1)/2
m = sum(prob[:K])
a = sum(prob[:K])
for j in range(1,N-K+1):
    a = a - prob[j-1] + prob[j+K-1]
    if a > m:
        m = a
print(m)

Submission status: Accepted

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

st = 0
max_p = sum(p[0:k])
sum_p = max_p
for i in range(0,n-k):
    sum_p -= p[i]
    sum_p += p[i+k]
    if max_p < sum_p:
        st = i+1
        max_p = sum_p

ex = 0
for j in range(st,st+k):
    ex += (p[j]+1)/2

print(ex)

Submission status: Accepted

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

p2 = [((e+1)*e / 2) / e for e in p]
res = sum(p2[:K])
ans = res
for i in range(K, N):
    res -= p2[i-K]
    res += p2[i]
    ans = max(ans, res)

print(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()))
P = list(map(lambda x: (x + 1) / 2, P))

s = sum(P[:K])
ans = [s]
for prev_a, next_a in zip(P, P[K:]):
    s -= prev_a
    s += next_a
    ans.append(s)
print(max(ans))

Submission status: Accepted

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

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()))
    ans = 0
    com = [0] * (N+1)
    for i in range(N):
        com[i+1] = (1+p[i]) / 2 + com[i]
    for i in range(K, N+1):
        ans = max(ans, com[i]-com[i-K])
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
p=list(map(int,input().split()))
P=([(1+i)/2 for i in p])
count=0
S=[0]
for i in range(N):
  S.append(S[i]+P[i])

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

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
p=[int(i) for i in input().split()]
a=[]
ans=0
for i in p:
    ans+=(i+1)/2
    a.append(ans)
k=0
for t in range(0,N-K):
    tt=a[t+K]-a[t]
    k=max(k,tt)
print(k if k!=0 else a[-1])

Submission status: Accepted

Solution code:
from itertools import accumulate


def expectation(n):
    n = int(n)
    return n * (n + 1) // 2 / n


N, K = map(int, input().split())
acc_E = [0.0] + list(accumulate(map(expectation, input().split())))
print(max(acc_E[i + K] - acc_E[i] for i in range(N - K + 1)))

Submission status: Accepted

Solution code:
#累積和　都度sum（O(n)）を取っていると，O(n^2)になってしまう
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+k]-acc[i] for i in range(n-k+1)) 
print(ans)

Submission status: Accepted

Solution code:
#for内でその都度sumをとるのはまずいらしい
n,k = map(int,input().split())
p = list(map(int,input().split()))
ave = []
ans = 0
tmp = 0

for i in range(n):
  ave.append((p[i]+1)/2)

for j in range(n):
  tmp += ave[j]
  if j >= k:
    tmp -= ave[j-k]
    
  ans = max(ans,tmp)


print(ans)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
p = list(map(int,input().split()))
ave = []
ans = 0
tmp = 0

for i in range(n):
  ave.append((p[i]+1)/2)

for j in range(n):
  tmp += ave[j]
  if j >= k:
    tmp -= ave[j-k]
    
  ans = max(ans,tmp)


print(ans)

Submission status: Accepted

Solution code:
# 和の期待値は期待値の和
# それぞれ期待値を出したあとは大きさKの区間和の最大値
# n(n+1)/2
n, k = map(int, input().split())
p = []
for x in list(map(int, input().split())):
    p.append((x * (x + 1) // 2) / x)

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

print(ans)

Submission status: Accepted

Solution code:
import numpy as np

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

expects = np.array([(p + 1) / 2 for p in ps])
partial_sum = np.sum(expects[:k])
mx = partial_sum

for i in range(1, n - k + 1):
    partial_sum = partial_sum - expects[i - 1] + expects[i + k - 1]
    mx = max(partial_sum, mx)

print(mx)

Submission status: Accepted

Solution code:
from itertools import accumulate


def main():
    n, k = [int(x) for x in input().split()]
    dice = [int(x) for x in input().split()]

    expected_accum = list(accumulate((1 + p) / 2 for p in dice))

    def gen():
        for start in range(n - k + 1):
            if start == 0:
                yield expected_accum[k - 1]
            else:
                yield expected_accum[start + k - 1] - expected_accum[start - 1]

    print(max(gen()))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    n, k = [int(x) for x in input().split()]
    dice = [int(x) for x in input().split()]

    expected_accum = []
    for i, p in enumerate(dice):
        ex = (1 + p) / 2
        if i == 0:
            expected_accum.append(ex)
        else:
            expected_accum.append(expected_accum[-1] + ex)

    def gen():
        for start in range(n - k + 1):
            if start == 0:
                yield expected_accum[k - 1]
            else:
                yield expected_accum[start + k - 1] - expected_accum[start - 1]

    print(max(gen()))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

a= sum(p[0:k])
ans = a

for i in range(n-k):
    a -= p[i]
    a += p[i+k]
    ans = max(ans,a)

print((ans+k)/2)

Submission status: Accepted

Solution code:
n,k=list(map(int,input().split()))
p=list(map(int,input().split()))
s=sum(p[0:k])
ans=(k+s)/2

for l in range(n-k):
  s-=p[l]
  s+=p[l+k]
  ans=max(ans,(k+s)/2)
print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
P = list(map(int, input().split()))
maxv = tempsum = sum(P[:k])
for i in range(1, n-k+1):
	tempsum = tempsum - P[i-1] + P[i+k-1]
	maxv = max(maxv, tempsum)
print((maxv + k) * 0.5)

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]+1)/2

ans = [0]*(n)
tem = 0
for i in range(n):
    tem = tem
    if i < k:
        tem = tem + p[i]
    else:
        tem = tem + p[i] - p[i-k]
    ans[i] = tem

print(max(ans))

Submission status: Accepted

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

q = [0]
for v in p:
    q.append(q[-1] + v)

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

print(res)