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: Runtime Error

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

(n, k), s = map(int, input().split()), list(map(lambda x: (int(x) + 1) / 2, input().split()))
print(f'{max([sum(s[i:i+k]) for i in range(n - k)]):.10f}')

Submission status: Runtime Error

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


#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

#import numpy as np

def main():
	n,k=MI()
	p=LI()

	for i in range(N -K +1):
  	ans2 = sum(p[i:i+K])
  	if ans2 > ans1:
    	ans1 = ans2
    	ans_list = p[i:i+K]
    ans = sum(map(lambda i:i/2+0.5,ans_list))
	print(ans)


if __name__ == "__main__":
	main()

Submission status: Runtime Error

Solution code:
def f(H):
    if H == 1:
        return 1
    return 2 * f(H//2) + 1


def solve():
    H = int(input())
    print(f(H))


if __name__ == "__main__":
    solve()

Submission status: Runtime Error

Solution code:
n, k= map(int,input().split())
ps = list(map(int, input().split()))
    
s = [0]*(n+1)
 
for i in range(n):
    s[i+1] = s[i] + (ps[i] + 1)/2
 
    
tmp=0
for i in range(len(res)-k):
    tmp=max(tmp, s[i+k] - s[i])

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

Submission status: Runtime Error

Solution code:
import numpy
n, k= map(int,input().split())
ps = list(map(int, input().split()))
    
 
s = [0]*(n+1)
 
for i in range(n):
    s[i+1] = s[i] + (ps[i] + 1)/2
 
    
#res = numpy.cumsum(data2)
tmp=0
for i in range(len(res)-k):
    tmp=max(tmp, s[i+k] - s[i])

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

Submission status: Runtime Error

Solution code:
import numpy
n, k= map(int,input().split())
ps = list(map(int, input().split()))
if k==1:
    ans=(1+pon[pon.index(max(pon))])/2
    print(ans)
    sys.exit()
    
# 数値を倍にする関数
def calc_double(n):
    return (n +1)/2
 
data2 = list(map(calc_double, ps))
res = numpy.cumsum(data2)
tmp=0
for i in range(len(res)-k):
    if res[i+k]-res[i] >=tmp:
        tmp=res[i+k]-res[i]

print(tmp)

Submission status: Runtime Error

Solution code:
import numpy
n, k= map(int,input().split())
ps = list(map(int, input().split()))
pon=ps
i=1
for a in range(k-1):
    ps1 = numpy.roll(pon, -i)  # = np.ndarray([ x[1], x[2], ..., x[n-1], x[0] ])
    ps = ps + ps1
    i+=1

    
if not k==1:num=ps.tolist().index(ps[:-(k-1)].max())
ans=0
for a in range(k):
    ans+=sum(range(1,pon[num+a]+1))/pon[num+a]
    
print(ans)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
from itertools import accumulate
from decimal import Decimal
n,k=map(int,input().split())
p=list(map(int,input().split()))
l=[]
tmp=0
for i in range(n):
    p[i]=Decimal((p[i]+1)/2)
    tmp+=p[i]
    l.append(tmp)
ans=l[k]
for i in range(k,n):
    tmp=l[i]-l[i-k]
    if tmp>ans:
        ans=tmp
print(Decimal(ans))

Submission status: Runtime Error

Solution code:
import numpy as np
import copy
n,k=map(int,input().split())
p=list(map(int,input().split()))
p = np.array(p)
s = copy.deepcopy(p)
P = np.empty((k-1, n))
for i in range(k-1):
    P[i] = np.roll(p,(-i-1))
    s = s+P[i]
    s[-i-1] = 0
s.sort()
ans = (s[-1]/2)+0.5*k
print(ans)

Submission status: Runtime Error

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

Submission status: Runtime Error

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()))

d=[]

c=[(i+1)/2 for i in c]
n=cumsum(c)
m=[]
for i in range(a-b):
    m.append(n[i+b]-n[i])


print(max(m))

Submission status: Runtime Error

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

d=[]
for i in range(a-b):
    d.append(sum(c[i:i+b]))

n=max(d)
print((n+b)/2)

Submission status: Runtime Error

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
A= list(accumulate(A))
#print(A)
B=[]
for i in range(K,N):
    B.append((A[i]-A[i-K])/2)
print(max(B))

Submission status: Runtime Error

Solution code:
import copy
n, k = input().split()
m = list(map(int, input().split()))
ans = 0
kazu =[]
kai = []
kitai2 = 0
for x in range(int(n)):
    kazu = []
    for l in range(int(k) - (int(k)-1)):
        if x+l < len(m):
           kazu.append(m[x+l])
    if ans < sum(kazu):
        ans = sum(kazu)
        kai = copy.deepcopy(kazu)

for j in range(int(k)):
    kitai = 0
    for g in range(kai[j]):
        kitai += g+1
    kitai2 += kitai / kai[j]
print(kitai2)

Submission status: Runtime Error

Solution code:
import numpy as np
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)

q = deque()
ans = 0
for p in P:
  q.append(dice[p])
  
  if len(q) < K:
    continue
  else:
    ans = max(ans, sum(q))
    q.popleft()

print(ans)

Submission status: Runtime Error

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]

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: Runtime Error

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[2]

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: Runtime Error

Solution code:
import numpy as np
import numpy

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

S = numpy.cumsum(P)
P.append(0)

for i in range(1,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: Runtime Error

Solution code:
N,K=map(int,input().split())
_=input().split()
S=[]
for s in _:
    S.append((int(_)+1)/2)

maxsum=0

for i in range(len(S)):
    tempsum=sum(S[i:i+K])
    if maxsum<tempsum:
        maxsum=tempsum
    else:
        pass
      
print(maxsum)

Submission status: Runtime Error

Solution code:
import sys
n = int(input())
ls = list(map(int,input().split()))
for i in range(len(ls)):
    if ls.count(ls[i]) > 1:
        print("NO")
        sys.exit()
    else:
        continue
print("YES")

Submission status: Runtime Error

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

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

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
Dices = list(map(int, input().split()))
Que = []
Eyes = {}
for i in range(K):
    Que.append(Dices[i])
Eyes[K]=sum(Que)
for i in range(K+1, N):
    Que.pop(0)
    Que.append(Dices[i])
    Eyes[i] = Eyes[i-1]-Que[0]+Que[-1]
a = 0
b = 0
for k, v in Eyes.items():
    if v > a:
        a = v
        b = k
ans = 0
for i in range(k-K+1, k+1):
    ans += (Dices[i]+1)/2
print(ans)

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
Dices = list(map(int, input().split()))
Que = []
Eyes = {}
for i in range(K):
    Que.append(Dices[i])
for i in range(K, N):
    Eyes[i] = sum(Que)
    Que.pop(0)
    Que.append(Dices[i])
a = 0
b = 0
for k, v in Eyes.items():
    if v > a:
        a = v
        b = k
ans = 0
for i in range(k-K+1, k+1):
    ans += (Dices[i]+1)/2
print(ans)

Submission status: Runtime Error

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

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

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

Submission status: Runtime Error

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]
for i in range(N-K):
  c=a+ls_p[i+K]-ls_p[i]
  b=max([a,c])
  a=c
print(b)

Submission status: Runtime Error

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 -= s[j]
    s += s[j+k]
    if s > ans :
        ans = s
print(ans)

Submission status: Runtime Error

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

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

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

print(ans)

Submission status: Runtime Error

Solution code:
from itertools import accumlate


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

    expected_accum = list(accumlate((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: Runtime Error

Solution code:
import numpy as np
n, k = map(int, input().split())
P = list(map(int, input().split()))
for i in range(len(P)):
	P[i] = (P[i] + 1) * 0.5
maxv = 0
for i in range(n):
	maxv = max(maxv, sum(P[i:i+k]))
print(maxv)

Submission status: Runtime Error

Solution code:
import numpy as np
n, k = map(int, input().split())
P = np.array(list(map(int, input().split())))
# P = list(map(int, input().split()))
P = (P + 1) * 0.5
maxv = 0
for i in range(n):
	maxv = max(maxv, sum(P[i:i+k]))
print(maxv)

Submission status: Runtime Error

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

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

import numpy as np
cums=np.cumsum([0] + [exp(i) for i in p])

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

print(ans)

Submission status: Runtime Error

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

    print(ps)
    cumulative_sums = [sum(ps[:i+1]) for i in range(n)]
    ans = max([cumulative_sums[i+k] - cumulative_sums[i] for i in range(n-k)])
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import math
import itertools

n = int(input())
k = int(input())

if (n < 99 and k == 3) or (n < 9 and k == 2):
    print(0) 

else:
    f = len(str(n))

    #f-1桁以内に収まる数

    en = 1
    for i in range(k):
        en *= f-1-i

    de = math.factorial(k)


    s = en // de * pow(9, k)

    #print(s)
    #f桁目によって絞る

    kami = int(str(n)[0])

    en_2 = 1
    for i in range(k-1):
        en_2 *= f-1-i

    de_2 = math.factorial(k-1)


    s += (en_2 // de_2 * pow(9, k-1)) * (kami-1)


    #以下上1桁は同じ数字

    keta = list(range(f-1))
    num = list(range(1,10))

    b =  kami * pow(10, f-1)
    m = 0

    if k == 1:
        s += 1
    elif k == 2:
        s += 9*(f-2) + int(str(n)[1])
    else:
        kami2 = int(str(n)[1])

        en_3 = (f-2)*(f-3)

        de_3 = 2


        s += (en_3 // de_3 * pow(9, k-1))  + kami2 * 9 * (f-2)

    print(s)

Submission status: Runtime Error

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

    cumulative_sums = [sum(ps[:i]) for i in range(n)]
    ans = max([cumulative_sums[i+k] - cumulative_sums[i] for i in range(n-k)])
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import numpy as np


def main():
    n, k = map(int, input().split())
    ps = (np.array(list(map(int, input().split()))) + 1) / 2

    if k == 1:
        ans = ps[0]
    else:
        cumulative_sum = [0] * n
        for i in range(n):
            if i == 0:
                cumulative_sum[i] = ps[0]
            else:
                cumulative_sum[i] = ps[i] + cumulative_sum[i-1]

        ans = max([cumulative_sum[i+k] - cumulative_sum[i] for i in range(n-k)])
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import numpy as np


def main():
    n, k = map(int, input().split())
    ps = (np.array(list(map(int, input().split()))) + 1) / 2

    if k == 1:
        ans = max(ps)
    else:
        cumulative_sum = [0] * n
        for i in range(n):
            if i == 0:
                cumulative_sum[i] = ps[0]
            else:
                cumulative_sum[i] = ps[i] + cumulative_sum[i-1]
    
        ans = max([cumulative_sum[i+k] - cumulative_sum[i] for i in range(n-k)])
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import numpy as np


def main():
    n, k = map(int, input().split())
    ps = (np.array(list(map(int, input().split()))) + 1) / 2

    cumulative_sum = [0] * n
    for i in range(n):
        if i == 0:
            cumulative_sum[i] = ps[0]
        else:
            cumulative_sum[i] = ps[i] + cumulative_sum[i-1]

    ans = max([cumulative_sum[i+k] - cumulative_sum[i] for i in range(n-k)])
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

l = list(map(int, input().split()))
l = [(i+1)/2 for i in l]

ls = [l[0]]
for i in range(1, n):
    ls.append(ls[-1]+l[i])

if n == 1:
    print((l[0]+1)/2)
else:
    lans = [ls[i+k]-ls[i] for i in range(len(ls)-k)]
    print(max(lans))

Submission status: Runtime Error

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

l = list(map(int, input().split()))
l = [(i+1)/2 for i in l]

ls = [l[0]]
for i in range(1, n):
    ls.append(ls[-1]+l[i])

lans = [ls[i+k]-ls[i] for i in range(len(ls)-k)]
print(max(lans))

Submission status: Runtime Error

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

for i in range(0, n + k - 1):
    if (i + k - 1 > n - 1):
        break
    cnt = i
    s = 0
    while i + k != cnt:
        s += p[cnt]
        cnt += 1
    d.append(s)
# print(d)
idx = d.index(max(d))
ans = 0
for i in range(idx, idx + k):
    s = 0
    for j in range(1, p[i] + 1):
        s += j
    ans += s * (1 / p[i])

print('{:.10f}'.format(ans))

Submission status: Runtime Error

Solution code:
def main():
    n, k = list(map(int, input().split()))
    p = list(map(int, input().split()))
    
    s = []
    for i in range(len(p)-k):
        s.append((sum(p[i:i+k])+k)/2)    
    print(max(s))
    
if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

Submission status: Runtime Error

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

awk = 0
aix = k
for i in range(k):
  awk += a[i]
  #print(a[i])
#print('--')
a_max = awk

for i in range(k,n):
  #print(a[i],i-k)
  awk = awk + a[i] - a[i-k]
  if a_max < awk:
    a_max =  awk
    aix   = i

#print('===')
ans = 0.0
for i in range(aix-k+1,aix+1 ):
  #print(a[i],( 1 + a[i] )  / 2.0)
  ans += ( 1 + a[i] )  / 2.0

print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
from decimal import Decimal

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

if N==1:
    print((p.max() + 1) / Decimal(2))
else:
    p = np.cumsum(p)

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

    ans = (max(ans) + K) / Decimal(2)

    print(ans)

Submission status: Runtime Error

Solution code:
import math
import queue
from collections import defaultdict

def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()
def factorization(n):
	res = []
	if n%2==0:
		res.append(2)
	for i in range(3,math.floor(n//2)+1,2):
		if n%i==0:
			c = 0
			for j in res:
				if i%j==0:
					c=1
			if c==0:
				res.append(i)
	return res
def fact2(n):
	p = factorization(n)
	res = []
	for i in p:
		c=0
		z=n
		while 1:
			if z%i==0:
				c+=1
				z/=i
			else:
				break
		res.append([i,c])
	return res
def fact(n):#階乗
	ans = 1
	m=n
	for _i in range(n-1):
		ans*=m
		m-=1
	return ans
def comb(n,r):#コンビネーション
	if n<r:
		return 0
	l = min(r,n-r)
	m=n
	u=1
	for _i in range(l):
		u*=m
		m-=1
	return u//fact(l)
def combmod(n,r,mod):
	return (fact(n)/fact(n-r)*pow(fact(r),mod-2,mod))%mod
def printQueue(q):
	r=qb
	ans=[0]*r.qsize()
	for i in range(r.qsize()-1,-1,-1):
		ans[i] = r.get()
	print(ans)
def dq():
	return queue.deque()
class UnionFind():
	def __init__(self, n):
		self.n = n
		self.parents = [-1]*n

	def find(self, x): # root
		if self.parents[x]<0:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def union(self,x,y):
		x = self.find(x)
		y = self.find(y)

		if x==y:
			return

		if self.parents[x]>self.parents[y]:
			x,y = y,x

		self.parents[x]+=self.parents[y]
		self.parents[y]=x

	def size(self,x):
		return -1*self.parents[self.find(x)]

	def same(self,x,y):
		return self.find(x)==self.find(y)

	def members(self,x): # much time
		root = self.find(x)
		return [i for i in range(self.n) if self.find(i)==root]

	def roots(self):
		return [i for i,x in enumerate(self.parents) if x<0]

	def group_count(self):
		return len(self.roots())

	def all_group_members(self):
		return {r: self.members(r) for r in self.roots()} # 1~n
def bitArr(n):#ビット全探索
	x = 1
	zero = "0"*n
	ans = []
	ans.append([0]*n)
	for i in range(2**n-1):
		ans.append(list(map(lambda x:int(x),list((zero+bin(x)[2:])[-1*n:]))))
		x+=1
	return ans;
def arrsSum(a1,a2):
	for i in range(len(a1)):
		a1[i]+=a2[i]
	return a1
def maxValue(a,b,v):
	v2 = v
	for i in range(v2,-1,-1):
		for j in range(v2//a+1): #j:aの個数
			k = i-a*j
			if k%b==0:
				return i
	return -1

n,k = readInts()
p = readInts()
#print(p)
maxValue = 0
ans = 0
for i in range(n-k):
	if maxValue<sum(p[i:i+k]):
		maxValue = sum(p[i:i+k])
		memo = p[i:i+k]

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

print(ans)

Submission status: Runtime Error

Solution code:
import math
import queue
from collections import defaultdict

def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()
def factorization(n):
	res = []
	if n%2==0:
		res.append(2)
	for i in range(3,math.floor(n//2)+1,2):
		if n%i==0:
			c = 0
			for j in res:
				if i%j==0:
					c=1
			if c==0:
				res.append(i)
	return res
def fact2(n):
	p = factorization(n)
	res = []
	for i in p:
		c=0
		z=n
		while 1:
			if z%i==0:
				c+=1
				z/=i
			else:
				break
		res.append([i,c])
	return res
def fact(n):#階乗
	ans = 1
	m=n
	for _i in range(n-1):
		ans*=m
		m-=1
	return ans
def comb(n,r):#コンビネーション
	if n<r:
		return 0
	l = min(r,n-r)
	m=n
	u=1
	for _i in range(l):
		u*=m
		m-=1
	return u//fact(l)
def combmod(n,r,mod):
	return (fact(n)/fact(n-r)*pow(fact(r),mod-2,mod))%mod
def printQueue(q):
	r=qb
	ans=[0]*r.qsize()
	for i in range(r.qsize()-1,-1,-1):
		ans[i] = r.get()
	print(ans)
def dq():
	return queue.deque()
class UnionFind():
	def __init__(self, n):
		self.n = n
		self.parents = [-1]*n

	def find(self, x): # root
		if self.parents[x]<0:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def union(self,x,y):
		x = self.find(x)
		y = self.find(y)

		if x==y:
			return

		if self.parents[x]>self.parents[y]:
			x,y = y,x

		self.parents[x]+=self.parents[y]
		self.parents[y]=x

	def size(self,x):
		return -1*self.parents[self.find(x)]

	def same(self,x,y):
		return self.find(x)==self.find(y)

	def members(self,x): # much time
		root = self.find(x)
		return [i for i in range(self.n) if self.find(i)==root]

	def roots(self):
		return [i for i,x in enumerate(self.parents) if x<0]

	def group_count(self):
		return len(self.roots())

	def all_group_members(self):
		return {r: self.members(r) for r in self.roots()} # 1~n
def bitArr(n):#ビット全探索
	x = 1
	zero = "0"*n
	ans = []
	ans.append([0]*n)
	for i in range(2**n-1):
		ans.append(list(map(lambda x:int(x),list((zero+bin(x)[2:])[-1*n:]))))
		x+=1
	return ans;
def arrsSum(a1,a2):
	for i in range(len(a1)):
		a1[i]+=a2[i]
	return a1
def maxValue(a,b,v):
	v2 = v
	for i in range(v2,-1,-1):
		for j in range(v2//a+1): #j:aの個数
			k = i-a*j
			if k%b==0:
				return i
	return -1

n,k = readInts()
p = readInts()
#print(p)
maxValue = 0
ans = 0
for i in range(n-k):
	if maxValue<sum(p[i:i+k]):
		maxValue = sum(p[i:i+k])
		memo = p[i:i+k]
print(memo)
for i in range(k):
	ans+=(memo[i]+1)/2

print(ans)

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
p=list(map(int,input().split()))
f=lambda x:0.5*(x+1)
pp=list(map(f,p))
t=[0]*(n+1)
for i in range(n):
    t[i+1]=t[i]+pp[i]

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

Submission status: Runtime Error

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

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

sume = [0 for _ in range(n)]
for i in range(n):
    if i == 0:
        sume[i] = e[i]
    else:
        sume[i] = sume[i-1]+e[i]

ans = []
for i in range(n-k):
    ans.append(sume[i+k]-sume[i])    
    
print(max(ans))

Submission status: Runtime Error

Solution code:
n,k= list(map(int, input().split()))
j = list(map(int, input().split()))
s=0
sumlist=[0]*n
anslist=[0]*(n-k+1)
for i in range(n):
    s+=j[i]
    sumlist[i]=s
for i in range(len(anslist)):
    if i==0:
        z=sumlist[k-1]
        anslist[i]=z
    else:
        z=sumlist[i+k]-sumlist[i]
        anslist[i]=z
ans=max(anslist)
ans+=k
ans=ans/2
print(ans)

Submission status: Runtime Error

Solution code:
n,k= list(map(int, input().split()))
j = list(map(int, input().split()))
s=0
sumlist=[0]*n
anslist=[0]*(n-k+1)
for i in range(n):
    s+=j[i]
    sumlist[i]=s
for i in range(len(anslist)):
    z=sumlist[i+k]-sumlist[i]
    anslist[i]=z
ans=max(anslist)
ans+=k
ans=ans/2
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
n, k = map(int, input().split())
def f(x):
    return sum(range(1, x + 1)) / x
p = [f(int(i)) for i in input().split()]
s = np.cumsum(p)
print(max(s[k-1], max(s[k:] - s[:n - k])))

Submission status: Runtime Error

Solution code:
def main():
    input = stdin.buffer.readline
    n, k = map(int, input().split())
    p = list(map(int, input().split()))

    e = [i * (i + 1) / (2 * i) for i in range(1, 1001)]

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

    max = sum[k - 1]
    for i in range(k, n):
        if max < sum[i] - sum[i - k]:
            max = sum[i] - sum[i - k]

    print(max)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Runtime Error

Solution code:
from sys import stdin, setrecursionlimit


def main():
    input = stdin.buffer.readline
    n, k = map(int, input().split())
    p = list(map(int, input().split()))

    e = [i * (i + 1) / (2 * i) for i in range(1, 1000)]

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

    max = sum[k - 1]
    for i in range(k, n):
        if max < sum[i] - sum[i - k]:
            max = sum[i] - sum[i - k]

    print(max)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Runtime Error

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

for p in range(N-K+1):
  for q in range(K):
    S = S + L[K]
    L.append(S)
    
print(max(L))

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import numpy as np
 
n, k = map(int, input().split())
p = list(map(int, input().split()))

E = lambda x: 1 + (x - 1) * 0.5
p = [E(p_) for p_ in p]
q = np.cumsum(p)
sum_ = [q[i+k] - q[i] for i in range(n-k)]
print(max(sum_))

Submission status: Runtime Error

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

def calc_ex(x):
    return  x/2 + 0.5
p_ = list(map(calc_ex,p_))

cnt,res =0,[]
for i in range(2,n):
    cnt = sum(p_[i-k+1:i+1])
    res.append(cnt)

print(max(res))

Submission status: Runtime Error

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

def max_expected(L, K):
  length = len(L)
  if (length < K):
    return -1
  mid = length // 2
  s_left = max_expected(L[0:mid], K)
  #print("left array:{}, max: {}".format(L[0:mid], s_left))
  s_right = max_expected(L[mid:], K)
  #print("right array:{}, max: {}".format(L[mid:], s_right))
  offset = 0

  if (mid - K + 1 < 0):
    offset = - (mid - K + 1)
  end_offset = 0
  if (mid + K - 1 >= length):
    end_offset = mid + K - 1 - length
  max_p = sum(L[mid - K + 1 + offset:mid + 1 + offset])
  for i in range(mid - K + 1 + offset, mid - end_offset):
    j = sum(L[i:(i + K)])
    #print("{}[{}]..{}[{}]: {}".format(L[i], i, L[i + K - 1], i + K - 1, j))
    if max_p < j:
      max_p = j
  #print("mid: {}".format((max_p + K) / 2));
  
  return max((max_p + K) / 2, s_left, s_right)
print("{}".format(max_expected(P, K)))

Submission status: Runtime Error

Solution code:
from sys import stdin, setrecursionlimit


def main():
    n, k = map(int, stdin.readline().split())
    p = list(map(int, stdin.readline().split()))

    sp = [0] * 1001

    for i in range(1, 1001):
        sp[i] = sum(range(i + 1)) / i

    max = 0
    max_index = 0

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

    ans = 0
    for i in range(max_index, max_index + k):
        ans += sp[p[i]]

    print(ans)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Runtime Error

Solution code:
import numpy as np

n, k = map(int, input().split())
p = np.array(list(map(int, input().split())), dtype="i8")
p = np.cumsum((1 + p) / 2)
print((p[k:] - p[:n - k]).max())

Submission status: Runtime Error

Solution code:
from itertools import accumulate
import numpy as np

n, k = map(int, input().split())
p = np.array(list(map(int, input().split())), dtype=np.int64)

p = (1 + p) / 2
p = [0] + list(accumulate(p))
ans = 0
for i in range(k):
    ans = max(ans, p[i + k] - p[i])
print(ans)

Submission status: Runtime Error

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

N = NK[0]
K = NK[1]
tmp = sum(Ps[0:K])

for i in range(N-K+1):
    if (tmp < sum(Ps[i:i+K])):
        tmp = Ps[i:i+K]
        

print((tmp/2.0) + K/2.0)

Submission status: Runtime Error

Solution code:
for i in plist:
    sm = 0
    j = 0
    while j <= int(i):
        sm += j
        j += 1
    # print(sm)
    exp = sm / int(i)
    exlist.append(exp)
# print(exlist)

EMax = 0
for l in range(N - K + 1):
    t = 0
    testlist = []
    for t in range(K):
        if exlist[t + l] > EMax:
            EMax = exlist[t + l]

print(EMax)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
p = list(map(int, input().split()))
max = 0
list = [0] * k
if n % 2 == 0:
    roop = int(n / 2)
else:
    roop = int(n / 2) + 1
for i in range(roop):
    wk = 0
    for j in range(i, i + k):
        wk += p[j]
    if max < wk:
        max = wk
        for j in range(i, i + k):
            list[j - i] = p[j]
ans = 0
for i in range(k):
    wk = 0
    for j in range(list[i]):
        wk += j + 1
    ans += float(wk / list[i])
print(ans)

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
a = list(map(int, input().split()))
s = sum(a[:K])
ans = s
for i in range(N-K):
    s = s - s[i] + s[i+K]
    ans = max(s, ans)
print(ans)

Submission status: Runtime Error

Solution code:
import itertools　#pythonで累積和を使うときはitertoolsというライブラリのaccumulateを使う
n, k = map(int, input().split())
p = list(map(int, input().split()))
acc = list(itertools.accumulate([x for x in p])) #累積和の計算


#pの中から隣り合う（ｋ個）の和が最大のときの値は？（今回は２＋４＋５＝１１）　ｋ個離れたaccの差が最大なところ
ans=max(acc[i]-acc[i-k] for i in range(k-1,n))
answer=ans/2+k/2

Submission status: Runtime Error

Solution code:
N,K = map(int, input().split())
p = list(map(int, input().split()))
sump0=0
for i in range(N-2):
	sump=p[i]+p[i+1]+p[i+2]
	if sump>sump0:
	sump0=sump
    
print(sump0/2+K/2)

Submission status: Runtime Error

Solution code:
N,K = map(int, input().split())
p = list(map(int, input().split()))
sump0=0
for i in range(N-2):
	sump=p[i]+p[i+1]+p[i+2]
	if sump>sump0:
	sum0=sump
    
print(sum0/2+K/2)

Submission status: Runtime Error

Solution code:
N,K = map(int, input().split())
p = list(map(int, input().split()))
sump0=0
for i in range(N-2):
 
  sump=p[i]+p[i+1]+p[i+2]
  if sump>sump0:
		sum0=sump
    
print(sum0/2+K/2)

Submission status: Runtime Error

Solution code:
N,K = map(int, input().split())
p = list(map(int, input().split()))
sump0=0
for i in range(N-2):
 
  sump=p[i]+p[i+1]+p[i+2]
  if sump>sump0:
    sum0=sump
    
print(sum0/2+K/2)

Submission status: Runtime Error

Solution code:
N,K = map(int, input().split())
p = list(map(int, input().split()))
 
for i in range(N-2):
  sump0=0
  sump=p[i]+p[i+1]+p[i+2]
  if sump>smp0:
    sum0=sump
    
print(sum0/2+K/2)

Submission status: Runtime Error

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

for i in range(n-2):
  sump0=0
  sump=p[i]+p[i+1]+p[i+2]
  if sump>smp0:
    sum0=sump
    
print(sum0/2+k/2)