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:
def resolve():
    N, K = map(int, input().split())
    p = list(map(int, input().split()))
    exp_table = [0] * 200002
    curr_sum = 0
    for i in range(1, 200002):
        curr_sum += i
        exp_table[i] = curr_sum / float(i)
    curr_sum = 0
    max_v = float('-inf')
    for i in range(len(p)):
        if i+1 < K:
            curr_sum += exp_table[p[i]]
        elif i+1 == K:
            curr_sum += exp_table[p[i]]
            max_v = max(max_v, curr_sum)
        else:
            curr_sum = curr_sum - exp_table[p[i-K]] + exp_table[p[i]]
            max_v = max(max_v, curr_sum)
        # print(curr_sum, max_v, p[i], exp_table[p[i]])
    print(max_v)
resolve()

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
num_list = list(map(int , input().split()))
candidate = 0
for i in range(n-k+1):
    if i == 0:
        for j in range(k):
            candidate += (num_list[j]+1)/2
        tmp = candidate
    else:
        tmp += -(num_list[i-1]+1)/2 + (num_list[i+k-1]+1)/2
        if tmp > candidate:
            candidate = tmp
        
print(candidate)

Submission status: Accepted

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


def solve(N: int, K: int, p: "List[int]"):
    expectation = [1]*1000
    for i in range(1, len(expectation)):
        expectation[i] = expectation[i-1]+i+1
    for i in range(len(expectation)):
        expectation[i] /= (i+1)
    costs = [0]*(N-K+1)
    for i in range(K):
        costs[0] += expectation[p[i]-1]
    for i in range(1, len(costs)):
        costs[i] = costs[i-1] - expectation[p[i-1]-1]+expectation[p[i+K-1]-1]
    print(max(costs))
    return


# 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:
from collections import deque
n, k = map(int, input().split())
p = list(map(int, input().split()))
p = [(1/num)*(num)*(num+1)/2 for num in p]
d = deque(p[:k])
result = temp = sum(d)
popleft = d.popleft
dappend = d.append
for el in p[k:]:
    temp -= popleft()
    dappend(el)
    temp += el
    if result < temp:
        result = temp
print(result)

Submission status: Accepted

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

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

Submission status: Accepted

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

S = [0]
E = []

for i in range(0, N):
    S.append(S[i]+p[i])

for i in range(0, N-K+1):
    E.append(S[i+K]-S[i])


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

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

for i in range(N-K):
    tmp += -p[i] + p[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()))
ansmax = 0
ans = 0
for j in range(K):
  ans += (p[j]+1)/2
if(ansmax < ans):
  ansmax = ans
for i in range(N-K):
  ans =  ans - (p[i]+1)/2 + (p[i+K]+1)/2
  if(ansmax < ans):
    ansmax = ans
print(ansmax)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=[int(j) for j in input().split()]
ma=0.0
for i in range(0,k):
    temp=(1+a[i])
    temp=temp*a[i]
    temp=temp//2
    ma+=(temp/a[i])

sum=ma
#print(sum)

for i in range(k,n):
    temp=(1+a[i])
    temp=temp*a[i]
    temp=temp//2
    temp=temp/a[i]

    temp1=(1+a[i-k])
    temp1=temp1*a[i-k]
    temp1=temp1//2
    temp1=temp1/a[i-k]

    sum=(sum+temp)-temp1
    if(sum>ma):
        ma=sum

print(ma)

Submission status: Accepted

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

Submission status: Accepted

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

sum = 0
e = [0] * 1001
for i in range(1, 1000 + 1):
    sum += i
    e[i] = sum / i
    # print(i, e[i])


maxV = 0
maxI = 0
for i in range(0, K):
    maxV += p[i]

tmp = maxV
# [1 ..  2]
for i in range(1, N-K+1):
    tmp -= p[i-1]
    tmp += p[i+K-1] 
    if tmp > maxV:
        maxV = tmp
        maxI = i
    
    
    
    
    

ans = 0
for i in range(maxI, maxI + K):
    ans += e[p[i]]

print(ans)

Submission status: Accepted

Solution code:
x,y = map(int,input().split())
li = list(map(int,input().split()))
from collections import deque
l = []
for i in range(len(li)):
    l.append((1+ li[i])/2)
from itertools import accumulate
a = list(accumulate(l))
M = a[y-1]
for i in range(len(a)-y):
    m = a[i+y] - a[i]
    if m > M:
        M = m
print(M)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

import numpy as np
exps = np.array(p) / 2 + 0.5

# s = exps[:k].sum()
# m = s
# for i in range(1, n - k + 1):
#     s = s - exps[i-1] + exps[i+k-1]
#     if s > m:
#         m = s
# print(m)

cum = exps.cumsum()
diff = cum[k-1:n] - np.r_[0, cum[:n-k]]
print(diff.max())

Submission status: Accepted

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

import numpy as np
exps = np.array(p) / 2 + 0.5

s = exps[:k].sum()
m = s
for i in range(1, n - k + 1):
    s = s - exps[i-1] + exps[i+k-1]
    if s > m:
        m = s
print(m)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

data = np.fromstring(read(), np.int64, sep =' ')

N, K = data[:2]
P = np.hstack([[0], data[2:] + 1])

Pcum = P.cumsum()
x = Pcum[K:] - Pcum[0:-K]
print(x.max()/2)

Submission status: Accepted

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

import numpy as np

data = np.fromstring(read(), np.int64, sep=' ')

N, K  = data[:2]
P = np.hstack([[0], data[2:] + 1])

Pcum = P.cumsum()
x = Pcum[K:] - Pcum[0:-K]
print(x.max() / 2)

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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


def kitaichi(x):
    return (k+x)/2

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

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
b=[0]*n
for i in range(n):
    if a[i]%2==1:
        b[i]=(a[i]+1)//2
    else:
        b[i]=(a[i]+1)/2
from itertools import accumulate
ac=list(accumulate(b))
ans=0
for i in range(n-k+1):
    if i==0:
        tmp=ac[k-1]
    else:
        tmp=ac[i+k-1]-ac[i-1]
    ans=max(tmp,ans)
print(ans)

Submission status: Accepted

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

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]

answer = temporary = sum(E[:k])
for i in range(n - k):
    temporary += E[i + k] - E[i]
    answer = max(answer, temporary)

print(answer)

Submission status: Accepted

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

j = 0
for i in range(k):
    j += p[i]
ma = j

for i in range(k, n):
    j = j - p[i - k] + p[i]
    ma = max(ma, j)
print((ma+k)/2)

Submission status: Accepted

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

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

from itertools import accumulate
Q = [0]+P
Q = list(accumulate(Q))

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

Submission status: Accepted

Solution code:
from itertools import accumulate
n,k = map(int, input().split())
p = list(map(int,input().split()))
b = []
for i in p:
    b.append((i+1)/2)
c = list(accumulate([0] + b))
ans = []
for j in range(len(b)-(k - 1)):
    ans.append (c[j + k] - c[j])
print(max(ans))

Submission status: Accepted

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

me = [0]
for i in range(n):
    p = (P[i] * (P[i] + 1) / 2) / P[i]
    me.append(me[(i+1)-1]+p)

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

Submission status: Accepted

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

ans = 0
tmp = 0
for i in range(k):
    tmp2 = (p[i] * (1 + p[i])) // 2
    #print(tmp2)
    ans += tmp2 / p[i]
    tmp = ans
#print(ans)
for i in range(n - k):
    tmp3 = (p[i] * (1 + p[i])) // 2
    tmp4 = (p[i + k] * (1 + p[i + k])) // 2
    tmp = tmp + (tmp4 / p[i + k]) - (tmp3 / p[i])
    #print(p[i], p[i + k], tmp)
    #print(p[i], sum([i for i in range(1, p[i] + 1)]) / p[i])
    #print(p[i + k], sum([i for i in range(1, p[i + k] + 1)]) / p[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()))

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

Submission status: Accepted

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

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

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

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
ans = 0.0
tmp = 0.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 sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 0, 1, -1, 1, -1, -1, 1]
dy = [1, -1, 0, 0, 1, -1, 1, -1]

n, k = MAP()
p = LIST()
psum = [0 for _ in range(n - k + 1)]
for i in range(k):
    psum[0] += (p[i] + 1) / 2
for i in range(1, n - k + 1):
    psum[i] = psum[i - 1] + (p[i + k - 1] + 1) / 2 - (p[i - 1] + 1) / 2
print(max(psum))

Submission status: Accepted

Solution code:
def main():
    N, K = (int(i) for i in input().split())
    P = [int(i) for i in input().split()]
    B = [(p+1)/2 for p in P]
    from itertools import accumulate
    S = list(accumulate([0] + B))
    # print(B, S)
    ans = 0
    for i in range(N-K+1):
        cur = S[i+K] - S[i]
        ans = max(ans, cur)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

sum_ = sum(p[0:k])
max_ = sum(p[0:k])
for i in range(k, n):
    sum_ += p[i] - p[i - k]
    max_ = max(sum_, max_)

print((max_ + k) / 2)

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
s=sum(p[:k])
m=s
for i in range(k,n):
  s+=p[i]-p[i-k]
  m=max(m,s)
print(m)

Submission status: Accepted

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

N, K = map(int, input().split())
p = list(map(int, input().split()))
s = sum(p[:K])
m = s
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()))

cums = [0]
for p in P:
    cums.append(cums[-1] + (p+1)/2)
ans = 0
for i in range(N-K+1):
    ans = max(ans, cums[i+K] - cums[i])
print(ans)

Submission status: Accepted

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

S = []

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

B = []
for i in range(N-K+1):
  if i == 0:
    B.append(S[K-1])
  else:
    B.append(S[(K-1)+i]-S[-1+i])

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

Submission status: Accepted

Solution code:
import numpy as np
N, K = list(map(int, input().split()))
p = list(map(int, input().split()))
p_sum=[0]
for i in p:p_sum.append(p_sum[-1]+i)
max_sum_val = 0
for j in range(len(p_sum) - K):
    max_sum_val = max(p_sum[K+j]-p_sum[j], max_sum_val)
print((max_sum_val + K)/2)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
p =[int(s) for s in input().split()]
s = 0
key = 0
pred = 0
acc = {}
for h in range(n):
    if h == 0:
        acc[0] = p[0]
    else:
        acc[h] = acc[h-1]+p[h]
for r in range(n-k+1):
    if r == 0:
        s2 = acc[k-1]
    else:
        s2 = acc[k+r-1]-acc[r-1]
    if s2>s:
        s = s2
        key = r
print(0.5*(s+k))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from itertools import accumulate

n, k = map(int, input().split())
p = list(map(int, input().split()))
cs = [0] + list(accumulate(p))
pvt = 0
for i in range(n - k + 1):
    m = cs[pvt + k] - cs[pvt]
    s = cs[i + k] - cs[i]
    if s > m:
        pvt = i
print((cs[pvt + k] - cs[pvt] + k) / 2)

Submission status: Accepted

Solution code:
import numpy as np
N, K = map(int, input().split())
A = list(map(int, input().split()))
 
r=sum(A[0:K])
re=r
for i in range(N-K):
    r=r+A[K+i]-A[i]
    if r > re:
        re=r
        
print((re+K)/2)

Submission status: Accepted

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

hoge=0
for i in range(K):
    hoge += A[i]

re=hoge
for i in range(N-K):
    hoge=hoge+A[K+i]-A[i]
    if hoge >= re:
        re=hoge
        
print((re+K)/2)

Submission status: Accepted

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

res = []

res.append((sum(range(1,p[0]+1)))/p[0])

for i in range(1,N):
  #res.append(res[i-1] + p[i]*(p[i]+1)/(2*p[i]))
  res.append(res[i-1] + 0.5*(p[i]+1))
  #res.append(res[i-1] + 1 + 0.5*(p[i]-1))

ans=res[K-1]

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

Submission status: Accepted

Solution code:
import numpy as np
N,K = (int(x) for x in input().split())
p1 = np.array(list(map(int, input().split())))
s1 = p1.cumsum()
s2 = np.append(0, s1)
p2 = np.array([(s2[i+K] - s2[i]) for i in range(N-K+1)])
max = np.amax(p2)
print((max+K) / 2)

Submission status: Accepted

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

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

plus_p=[expect[K-1]]
for i in range(1, N-K+1):
    plus_p.append(expect[i+K-1]-expect[i-1])
print(max(plus_p))

Submission status: Accepted

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

expect=[(dice+1)/2 for dice in p]
#print(expect)
#plus_p=[sum(expect[i:i+K]) for i in range(N-K+1)]

first=sum(expect[0:K])
plus_p=[first]
for i in range(1, N-K+1):
	plus_p.append(plus_p[i-1]-expect[i-1]+expect[i-1+K])
#print(plus_p)
print(max(plus_p))

Submission status: Accepted

Solution code:
import queue

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

A_expect=[a+1 for a in A]
q = queue.Queue()
S=0
ans=0
for a_e in A_expect:
    S+=a_e
    q.put(a_e)
    if q.qsize()>K:
        S-=q.get()
    if q.qsize()==K:
       ans=max(ans,S)
ans/=2
print(ans)

Submission status: Accepted

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

wa_temp = sum(P[0:K])
max_wa = wa_temp

for i in range(N-K):
    wa_temp = wa_temp - P[i] + P[i+K]
    if wa_temp > max_wa:
        max_wa = wa_temp
print(max_wa)

Submission status: Accepted

Solution code:
# 初期入力
N,K = (int(x) for x in input().split(" "))
A = list(map(int, input().split()))

# １からnまでの和 S_n = n*(n+1)/2　さいころの期待値は　S_n /n
kitaiti = [ (i+1)/2 for i in A ]

#　N個のサイコロの期待値の累積和 S
S = [0] * (N +1)
#S[0] = kitaiti[0]
#S =[0]
# S[0] = 0
for i in range(1,N +1):
    S[i] = S[i-1] + kitaiti[i-1]

# 隣接するK個の期待値の和 S_K
S_K = []
for i,v in enumerate(S[:(-1)*K ]):
    S_K.append( S[i + K ] - S[i] )
"""
print(kitaiti)
print(S)
print(S_K)
"""
print(max(S_K))

Submission status: Accepted

Solution code:
class BIT:
    def __init__(self, n):
        self.node = [ 0 for _ in range(n+1) ]

    def add(self, idx, w):
        i = idx
        while i < len(self.node) - 1:
            self.node[i] += w
            i |= (i + 1)

    def sum_(self, idx):
        ret, i = 0, idx-1
        while i >= 0:
            ret += self.node[i]
            i = (i & (i + 1)) - 1
        return ret

    def sum(self, l, r):
        return self.sum_(r) - self.sum_(l)


n, k = map(int, input().split())
tree = BIT(n)
p = [ int(x) for x in input().split() ]

for i in range(n):
    tree.add(i, (1+p[i])/2)

ans = 0
for i in range(n-k+1):
    ans = max(ans, tree.sum(i, i+k))

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
N, K = map(int, input().split())
a = np.array(list(map(int, input().split())))
a = (a + 1) / 2
total = 0
maxi = 0
for i in range(0, N):
    total += a[i]
    if i >= K - 1:
        maxi = max(maxi, total)
        total -= a[i-(K-1)]
print('{:.12f}'.format(maxi))

Submission status: Accepted

Solution code:
from itertools import accumulate

def main():
    N, K = map(int, input().split())
    P = list(map(int, input().split()))
    ans = 0
    E = [0] * N
    for i in range(N):
        E[i] = ((P[i] * (P[i] + 1)) // 2) / P[i]

    F = [0] + list(accumulate(E))
    ans = 0
    for i in range(N-K+1):
        tmp = F[i+K] - F[i]
        ans = max(ans, tmp)

    print(ans)






if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque
n, k = map(int, input().split())
p = list(map(int, input().split()))
p_acc = deque([])
for i, x in enumerate(p):
    if i == 0:
        p_acc.append((x + 1) / 2)
    else:
        p_acc.append((x + 1) / 2 + p_acc[i - 1])
ans = 0
for i in range(n - k + 1):
    equity = p_acc[k - 1 + i] - p_acc[i - 1] if i != 0 else p_acc[k - 1]
    if equity > ans:
        ans = equity
print(ans)

Submission status: Accepted

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

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

e = sum(E[:K])
ans = e
for i in range(1, N-K+1):
  e = e - E[i-1] + E[i+K-1]
  if ans < e:
    ans = e
    
print(ans)

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]
#print(E)

# 累積和
cusum = [0]
for e in E:
    cusum.append(cusum[-1] + e)
#print(cusum)

# 隣接K個の和
ans = 0
for i in range(K, N+1):
    tmp_e = cusum[i] - cusum[i-K]
    #print(i, tmp_e)
    ans = max(ans, tmp_e)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
class SegmentTree:
    seg_len = 1
    node = []
    def __init__(self, n):
        while self.seg_len < n:
            self.seg_len <<= 1
        self.node = [ 0 for _ in range(self.seg_len*2) ]

    def add(self, idx, v):
        idx += self.seg_len
        self.node[idx] += v
        while True:
            idx >>= 1
            if idx == 0:
                break
            self.node[idx] = self.node[idx*2] + self.node[idx*2+1]

    def sum(self, l, r):
        l += self.seg_len
        r += self.seg_len
        ret = 0
        while l < r:
            if l & 1 == 1:
                ret += self.node[l]
                l += 1
            if r & 1 == 1:
                ret += self.node[r-1]
                r -= 1
            l >>= 1; r >>= 1;
        return ret


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

seg_tree = SegmentTree(n)
for i in range(n):
    seg_tree.add(i, (1+p[i])/2)

ans = 0
for i in range(n-k+1):
    ans = max(ans, seg_tree.sum(i, i+k))

print(ans)

Submission status: Accepted

Solution code:
class SegmentTree:
    seg_len = 1
    node = []
    def __init__(self, n):
        while self.seg_len < n:
            self.seg_len <<= 1
        self.node = [ 0 for _ in range(self.seg_len*2) ]

    def add(self, idx, v):
        idx += self.seg_len
        self.node[idx] += v
        while True:
            idx //= 2
            if idx == 0:
                break
            self.node[idx] = self.node[idx*2] + self.node[idx*2+1]

    def sum(self, l, r):
        l += self.seg_len
        r += self.seg_len
        ret = 0
        while l < r:
            if l & 1 == 1:
                ret += self.node[l]
                l += 1
            if r & 1 == 1:
                ret += self.node[r-1]
                r -= 1
            l //= 2; r //= 2;
        return ret


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

seg_tree = SegmentTree(n)
for i in range(n):
    seg_tree.add(i, (1+p[i])/2)

ans = 0
for i in range(n-k+1):
    ans = max(ans, seg_tree.sum(i, i+k))

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
x,y=list(map(int, input().split()))
z=list(map(int, input().split()))
ans=0
chk=0
for i in range(y):
	ans=ans+z[i]
	chk=ans
for i in range(x-y):
	chk=chk-z[i]+z[i+y]
	if chk>ans:
		ans=chk
print((ans+y)/2)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
class BIT:
    def __init__(self, n):
        self.bit = [ 0 for _ in range(n+1) ]

    def add(self, x, w):
        i = x
        while i < len(self.bit)-1:
            self.bit[i] += w
            i |= (i+1)

    def sum_(self, x):
        ret, i = 0, x-1
        while i >= 0:
            ret += self.bit[i]
            i = (i & (i+1)) - 1

        return ret

    def sum(self, l, r):
        return self.sum_(r) - self.sum_(l)


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

tree = BIT(n)
for i in range(n):
    tree.add(i, (p[i] + 1) / 2)

ans = 0
for i in range(n-k+1):
    ans = max(ans, tree.sum(i, i+k))

print(ans)

Submission status: Accepted

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

e = []
max_ = 0
sum_ = 0
f = []
e = [(1+p[i])/2  for i in range(n)]
for i in range(n):
    if i < k:
        sum_ += e[i]
        max_ = sum_
    else:
        sum_ = sum_ + e[i] - e[i - k]
        max_ = max(max_, sum_)

print(max_)

Submission status: Accepted

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

ans = 0
expect = 0
for i in range(N-K+1):
    if i == 0:
        expect = sum([(p[i]+1)/2 for i in range(K)])
        ans = expect
    else:
        expect = expect - ((p[i-1] + 1) / 2) + ((p[i+K-1] + 1) / 2)
        ans = max(ans, expect)
print(ans)

Submission status: Accepted

Solution code:
n,k = map(int,input().split(" "))
c = list(map(int,input().split(" ")))
ans = 0
kar = 0
for i in range(n):
    c[i] = (c[i]+1)/2

for i in range(n):
    if i + 1 <= k:
        ans += c[i]
        kar += c[i]
    else:
        kar += c[i] - c[i-k]
        if ans <= kar:
            ans = kar
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import copy
import math
import string

N,K = map(int,input().split())
p = list(map(int,input().split()))
k = [0]*N
s = [0]*(N+1)
for i in range(N):
    k[i] = (1+p[i])/2
    s[i+1] = s[i]+k[i]

ans = 0
for i in range(N+1):
    if i - K < 0:
        continue
    ans = max(ans,s[i]-s[i-K])
print(ans)

Submission status: Accepted

Solution code:
N,K = (int(x) for x in input().split())
max_e = 0.0
e = 0.0
cnt = 0
p = list(map(float,input().split()))
for i in range(N):
  n = p[i]
  p[i] = n*(n+1)/(2.0*n)
  
for i in range(N):
  cnt += 1
  e += p[i]
  if cnt == K:
    n = p[i-K+1]
    if max_e < e:
      max_e = e
    cnt = K-1
    e -= n

print(max_e)

Submission status: Accepted

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

p=list(map(int,input().split()))
l=[0]*k
ans=0
for i in range(k):
    aa=1+0.5*(p[i]-1)
    ans+=aa
th=ans
for j in range(k,n):
    a=1+0.5*(p[j-k]-1)
    b=1+0.5*(p[j]-1)

    if ans-a+b>th:
        th=ans-a+b
    ans=ans-a+b

print(th)
"""
1=>1
2=>1.5
3=>2
4=>2.5
5=>3
6=>3.5
7=>4
8=>4.5
9=>5
10=>5.5
11=>6

1+0.5*(n-1)

1+0.5*10"""

Submission status: Accepted

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

ret = 0
for i in range(N - K + 1):
    ret = max(ret, lst[i + K] - lst[i])
print(ret)

Submission status: Accepted

Solution code:
# from math import factorial,sqrt
# from itertools import permutations as permus
# from fractions import gcd
# from collections import deque,Counter
# from decimal import Decimal, getcontext
# # getcontext().prec = 1000
# # eps = Decimal(10) ** (-100)

# import numpy as np
# import scipy as scp

# 入力の受け取り
n,k = map(int,input().split())
# 配列入力の受け取り
arrP = list(map(int,input().split()))

sumlist = [0]
meansum = 0
for num in arrP:
    heikin = (1 + num)/2
    meansum += heikin
    sumlist.append(meansum)

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

print(ans)
# print("{:.10f}".format(ans))
# print(*ans)   # unpackして出力。間にスペースが入る
# for row in board:
#     print(*row,sep="")    #unpackして間にスペース入れずに出力する

Submission status: Accepted

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

Submission status: Accepted

Solution code:

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

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
P = [int(i) for i in input().split()]
ex_list = []
ex = 0
sum = 0
for j in range(K):
  sum += P[j]
ex_list.append((sum + K) / 2)
for i in range(N - K):
  sum = sum - P[i] + P[i + K]
  ex_list.append((sum + K) / 2)
print(max(ex_list))

Submission status: Accepted

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

Submission status: Accepted

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

S = numpy.cumsum(P)

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

Submission status: Accepted

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

for i in range(1, n-k+1):
    cur -= (a[i-1]+1)/2
    cur += (a[i+k-1]+1)/2
    maximum = max(maximum, cur)

print(maximum)