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 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 = sum(p[0:k])
be = maxValue
memo = p[0:k]
ans = 0
for i in range(1,n-k+1):
	be+=-p[i-1]+p[i+k-1]
	if maxValue<be:
		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: Accepted

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

Submission status: Accepted

Solution code:
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

n,k = nm()
p = nl()

def exp(num):
  ret = (1+num)/2
  return ret

mx=0

pp = list(map(exp,p))
pd = [0]*(n+1)



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




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

print(mx)

Submission status: Accepted

Solution code:

n,k = list(map(int,input().split()))
a = list(map(int,input().split()))
r = [0 for _ in range(n+1)]
ans = 0
for i in range(1,n+1):
    x = a[i-1]
    r[i] = r[i-1] + (x*(x+1))/2/x #期待値
    if i+1 >=k:
        ans = max(ans,r[i]-r[i-k])
print(ans)

Submission status: Accepted

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

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

cnt=max(cnt,d)

print((cnt+k)/2)

Submission status: Accepted

Solution code:
from itertools import accumulate
N, K = map(int, input().split())
P = list(map(int, input().split()))
acc = [0] + list(accumulate(P))
print((max(b - a for a, b in zip(acc, acc[K:])) + K) / 2)

Submission status: Accepted

Solution code:
# ABC154 D Dice in Line

import itertools

n, k = map(int, input().split())
p_list = [int(x) for x in input().split()]
e_list = [None]*n

for i in range(n):
    e_list[i] = (1 + p_list[i])/2

cumsum = list(itertools.accumulate(e_list))
ans = cumsum[k-1]

for i in range(k,n):
    _ = cumsum[i] - cumsum[i-k]
    if ans < _:
        ans = _

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

maxp = sum(p[0:k])
s = maxp
save = 0
pre = p[0]
for i in range(k,n):
    s = s - p[i-k] + p[i]
    if(maxp < s):
        maxp = s
        save = i-k+1

score = 0
for i in range(save,save+k):
    score += (1+p[i])/2 
print(score)

Submission status: Accepted

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

if n == k:
    ans.append(sume[-1])
else:
    for i in range(n-k):
        ans.append(sume[i+k]-sume[i])

print("%.12f"%max(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()))
    answer = sum(p[0:K])
    r = answer
    for i in range(N-K):
        answer = answer - p[i] + p[i+K]
        r = max(r, answer)
    print((r+K)/2)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools


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

    P = [(1 + p) / 2 for p in P]
    accumulate_P = [0] + list(itertools.accumulate(P))

    ans = 0
    for ii in range(N - K + 1):
        range_sum_P = accumulate_P[ii + K] - accumulate_P[ii]
        ans = max(ans, range_sum_P)

    print(ans)

resolve()

Submission status: Accepted

Solution code:
import sys
n, k = map(int, input().split())
p = [int(i) for i in input().split()]
total = [0] * n
total[0] = sum(range(1, p[0] + 1)) / p[0]
max_value = 0
if k == 1:
    print(sum(range(1, max(p) + 1)) / max(p))
    sys.exit()
elif k == n:
    print(sum([sum(range(1, i + 1)) / i for i in p]))
    sys.exit()
for i in range(1, n):
    total[i] = total[i - 1] + sum(range(1, p[i] + 1)) / p[i]
    
    if i == k - 1:
        max_value = total[i]
    elif i >= k:
        max_value = max(max_value, total[i] - total[i - k])
print(max_value)

Submission status: Accepted

Solution code:
import sys
import math
from collections import deque
from collections import defaultdict

def main():
    n, k = list(map(int,sys.stdin.readline().split()))
    p = list(map(int,sys.stdin.readline().split()))
    sum_l = [0] * (n - k + 1)
    for i in range(k):
        sum_l[0] += p[i]
    for i in range(1,n - k + 1):
        sum_l[i] = sum_l[i - 1] - p[i - 1] + p[i + k - 1]
    #print(sum_l)
    max_idx = sum_l.index(max(sum_l))
    #print(max_idx)
    ans = 0
    for i in range(max_idx, max_idx + k):
        ans += ((p[i] * (p[i] + 1)) / 2) / p[i]
    print("{:.12f}".format(ans))
    return 0
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
p = list(map(int,input().split()))
def ex_even(a):
    return (a+1)/2
def ex_odd(b):
    return b//2 + 1
s = sum(p[0:k])
s_max = sum(p[0:k])
for i in range(n-k):
    s = s-p[i] + p[i+k]
    s_max = max(s_max,s)
if s_max % 2 == 0:
    print(ex_even(s_max) + 0.5*(k-1))
else:
    print(ex_odd(s_max) + 0.5*(k-1))

Submission status: Accepted

Solution code:
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


n, k = inpl()
p = inpl()
p = [(i + 1) / 2.0 for i in p]

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

Submission status: Accepted

Solution code:
#n dices from left to right

import collections
def ev(pi):
	return sum([1.0/pi * p for p in range(1, pi+1)])

n,k = map(int, raw_input().split(' '))
elems = map(int, raw_input().split(' '))
q = collections.deque([])
s = 0
r = -float('inf')
for pi in elems:
	v = ev(pi)
	q.append(v)
	s += v
	if len(q) == k+1:
		s -= q.popleft()
	if len(q) == k:
		r = max(r, s )

print r

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
from collections import deque

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

q=deque(p[0:k])
tmp=sum(q)
res=tmp
for i in range(k,n):
	q.append(p[i])
	tmp+=(p[i]-q.popleft())
	res=max(res,tmp)
	
print((float(res)+k)/2)

Submission status: Accepted

Solution code:
n,k= list(map(int, input().split()))
j = list(map(int, input().split()))
s=0
sumlist=[0]*(n+1)
anslist=[0]*(n-k+1)
for i in range(n):
    s+=j[i]
    sumlist[i+1]=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: Accepted

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

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

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

ans = 0

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

# print(a)
print(ans)

Submission status: Accepted

Solution code:
import itertools
N, K = [int(hoge) for hoge in input().split()]
P = [int(hoge) for hoge in input().split()]
PP = [0] + list(itertools.accumulate(P))
print((max([PP[X]-PP[X-K] for X in range(K,N+1)])+K)/2)

Submission status: Accepted

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

Submission status: Accepted

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

n,k = map(int,input().split())
p_list = list(map(hoge,input().split()))
p_set = [0,p_list[0]]
t = 0
for i in range(1,n):
  p_set.append(p_set[i]+p_list[i])
for j in range(k,n+1):
  t = max(t,p_set[j]-p_set[j-k])
print(t)

Submission status: Accepted

Solution code:

def E(x):
  y = int(x)
  return (y + 1) / 2

N, K = map(int, input().split())
p = list(map(E, input().split()))
ps = [0, p[0]]
ans = 0

for i in range(1, len(p)):
  ps.append(ps[i] + p[i])

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

print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate
n,k = map(int,input().split())
l = list(map(int,input().split()))
l = list((i+1)/2 for i in l)
rui = list(accumulate([0]+l))
#print(l)
#print(rui)
ma = 0
for i in range(n-k+1):
  a = rui[i+k]-rui[i]
  ma = max(ma,a)
print(ma)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
p = list(map(int, input().split()))
e = [(n+1)/2 for n in p]
now = sum(e[0:K])
ans = now
if N == 1:
  print(e[0])
  exit()

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

Submission status: Accepted

Solution code:
# ABC154D

def f(n, k, p):
    p = [(i+1)/2 for i in p]
    sums = sum(p[:k])
    mx = sums
    for i in range(k, n):
        sums = sums - p[i - k] + p[i]
        # print(f"sums = {sums}")
        if sums > mx:
            mx = sums
    print(mx)

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

Submission status: Accepted

Solution code:
from sys import stdin


N,K=map(int, stdin.readline().rstrip().split())

P = [int(x) for x in stdin.readline().rstrip().split()]
psum = 0.0
for i in range(K):
    psum += P[i]

ans = psum

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

print((ans+K)/2)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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, 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: Accepted

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

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

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

Submission status: Accepted

Solution code:
N,M=list(map(int,input().split()))
l_n=list(map(int,input().split()))
k=[]
j=0
for i in range(1,1001):
   j+=i
   k.append(j/i)
l_n=[k[l_n[i]-1] for i in range(N)]
ans=sum(l_n[0:M])
sum_n=ans
for i in range(N-M):
   sum_n+=l_n[i+M]
   sum_n-=l_n[i]
   ans=max(ans,sum_n)
print(ans)

Submission status: Accepted

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

expected_list = [(x+1)/2 for x in p_list]

partsum = sum(expected_list[0:k])
maximum = partsum
for i in range(1, n-(k-1)):
    partsum = partsum + expected_list[i+k-1] - expected_list[i-1]
    maximum = max(maximum, partsum)
print(maximum)

Submission status: Accepted

Solution code:
import math
n, k = map(int, input().split())
P = list(map(int, input().split()))
 
maxsum = 0
maxindex = 0
p_sum = 0
for i in range(k):
    p_sum += P[i]
maxsum = p_sum
maxindex = 0
for i in range(1, n - k + 1):
    p_sum = p_sum - P[i - 1] + P[i + k - 1]
    if p_sum > maxsum:
        maxsum = p_sum
        maxindex = i
result = 0
for i in range(maxindex, maxindex + k):
    result += (1 + P[i]) * P[i] / 2 / P[i]
print(result)

Submission status: Accepted

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

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

maxe = 0
idx = 0
for i in range(n-k+1):
    if cumsum[i+k] - cumsum[i] > maxe:
        maxe = cumsum[i+k] - cumsum[i]
        idx = i

def ex(n):
    return 0.5 * n + 0.5

res = 0
for i in range(k):
    res += ex(p[i+idx])

print(res)

Submission status: Accepted

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

#p_iの期待値は(1+p_i)/2で求められる
ans=0
sum_expected=[0]*(n-k+1)
for i in range(n-k+1):
    if i==0:
        sum_expected[0]=sum(p_input[:k])
    else:
        sum_expected[i]=sum_expected[i-1]-p_input[i-1]+p_input[i+k-1]

print(max(sum_expected))

Submission status: Accepted

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

a = i = j = count = ans = 0

new_p = [0] * n

for i in range(n):
    new_p[i] = float((p[i]+1)/2)

i = j = 0
total = 0
for i in range(k):
    total += new_p[i]
ans = total
for i in range(k,n):
    total = total + new_p[i] - new_p[i-k]
    ans = max(ans,total)

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

Submission status: Accepted

Solution code:
from __future__ import print_function

import sys
sys.setrecursionlimit(500000)

import re
import array
import copy
import functools
import operator

import math
import string
import fractions
from fractions import Fraction

import collections
import itertools
import bisect

import random
import time

import heapq
from heapq import heappush
from heapq import heappop
from heapq import heappushpop
from heapq import heapify
from heapq import heapreplace
from queue import PriorityQueue as pq
from queue import Queue

from itertools import accumulate

from collections import deque
from collections import Counter

from operator import mul
from functools import reduce

input = sys.stdin.readline


def eprint(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)
    return

# from fractions import gcd
# from math import gcd

# def lcm(n, m):
#     return int(n * m / gcd(n, m))


# def coprimize(p, q):
#     common = gcd(p, q)
#     return (p // common, q // common)


# def find_gcd(list_l):
#     x = reduce(gcd, list_l)
#     return x


def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom


def main():
    n,k = map(int,input().strip().split())      # 1 <= k <= n <= 2*10^5
    p = list(map(lambda n: Fraction( int(n)+1,2 ), input().strip().split())) # p[i] <= 10^3

    xsum=sum(p[0:k]) # 0 <= i < k
    ans=xsum
    for i in range(k,n):    # k <= i < n
        xsum = xsum + p[i] - p[i-k]
        ans = max(ans,xsum)
    print(float(ans))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
p=list(map(int,input().split()))
r=[0]
for i in range(n):
    r.append(r[i]+p[i])
p=0
for i in range(k,n+1):
    p=max(p,r[i]-r[i-k])
print('{:.10f}'.format((p+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
kset = 0
for j in range(k):
    kset += p[j]
max = -10000
if n != k:
    for l in range(n-k):
        if kset >= max:
            max = kset
        kset = kset - p[l] + p[l+k]
else:
    max = kset
    
if kset >= max:
    max = kset
print(max)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n, k = (int(x) for x in raw_input().split())
l = [int(x) for x in raw_input().split()]
pref = [0]
for i in xrange(n):
    pref.append(pref[-1] + (1 + l[i]) / 2.)
i = k
ret = 0
while i < len(pref):
    ret = max(ret, pref[i] - pref[i-k])
    i += 1
print ret

Submission status: Accepted

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

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

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

S.insert(0,0)

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

print(b)

Submission status: Accepted

Solution code:
def cumsum(a):
    s = [0]
    for i in range(len(a)):
        s.append(s[i]+a[i])
    return s

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

Submission status: Accepted

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

Submission status: Accepted

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

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

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

print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate
from collections import deque
N,K=list(map(int,input().split()))
p=list(map(int,input().split()))
p2=list(accumulate(p))
p2=deque(p2)
p2.appendleft(0)
p3=[]
ans=0
counter=0
ans2=0
for i in range(N-K+1):
    if counter<p2[i+K]-p2[i]:
        counter=p2[i+K]-p2[i]
        ans=i
for i in range(K):
    ans2+=sum(list(range(1,p[ans+i]+1)))/p[ans+i]
    
print(ans2)

Submission status: Accepted

Solution code:
import sys
import os

def file_input():
    f = open('ABC154/input.txt', 'r')
    sys.stdin = f

def main():
    #file_input()
    # int(input())
    N,K=map(int, input().split())
    p=list(map(int, input().split()))

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

    # print(maxi)
    out=0
    for i in range(maxi,maxi+K):
        out+=((1+p[i])*p[i]/2)/p[i]
        # print(out)

    print(out)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

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

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# D - Dice in Line

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

Q = [0] * (N + 1)
for i in range(N):
    q = ((1 + P[i]) * P[i] / 2) / P[i]
    Q[i + 1] = Q[i] + q

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

print(mx)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import combinations
#import bisect# lower_bound etc
#import numpy as np
def run():
    N,K = map(int, sysread().split())
    P = list(map(int, sysread().split()))
    P = [(1+p)/2 for p in P]
    val = sum(P[:K])
    ret = val
    for i in range(1, N-K+1):
        val -= P[i-1]
        val += P[i+K-1]

        ret = max(ret, val)
    print(ret)



if __name__ == "__main__":
    run()

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy, copy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, K = MAP()
p = LIST()

ans = 0

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

l = 0
r = K-1
ans = 0

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

anss = copy(ans)

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

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from itertools import accumulate
N,K = list(map(int,input().split()))
P = list(map(int,input().split()))
for i in range(N):
    P[i] = 1+(P[i]-1)/2
ruiseki = list(accumulate([0]+P))
ans = 0
for i in range(N-K+1):
    ans = max(ans,ruiseki[i+K]-ruiseki[i])
print(ans)

Submission status: Accepted

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: (x + 1) / 2
p = [E(p_) for p_ in p]
q = [0] + list(np.cumsum(p))
sum_ = [q[i+k] - q[i] for i in range(n-k+1)]

print(max(sum_))

Submission status: Accepted

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

s = sum(e_list[:k])
ans = s
for i, e in enumerate(e_list[k:]):
    s = s - e_list[i] + e
    ans = max(ans, s)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import collections
import itertools as it
import math
#import numpy as np
 
#  = input()
#  = int(input())
n, k  = map(int, input().split())
p  = list(map(int, input().split()))
#  = [int(input()) for i in range(N)]
#
# c = collections.Counter()

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

ans = 0
for p_ in p[max_[1]:max_[2]]:
    ans += 1 + (p_ - 1) * 0.5

#print(max_)
print(ans)

Submission status: Accepted

Solution code:
#C++のコードを移植
def Expected_value(n):
    return n + 1

n,k = map(int, input().split())
a = input().split()
sm = 0
mx = 0
for i in range(n):
    if i <= k-1:
        sm += Expected_value(int(a[i]))
        mx = sm
    else:
        sm = sm + Expected_value(int(a[i])) - Expected_value(int(a[i-k]))
        mx = max(mx,sm)

print(mx/2)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Fri May  8 14:30:55 2020

@author: shinba
"""
import copy

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

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

q = []

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

ans = copy.copy(a)
for i in q:
    a += i
    ans = max(ans,a)

print((ans+k)/2)

Submission status: Accepted

Solution code:
N,K = map(int,input().split(" "))
p_list = list(map(int,input().split(" ")))
expect_val = []
for i in p_list:
    expect_val.append((i+1)/2)
max_val = 0
val = 0
for i in range(K):
    max_val += expect_val[i]
val = max_val
for i in range(N-K):
    val = val - expect_val[i] + expect_val[i+K]
    max_val = max(max_val,val)
print(max_val)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
cnt = [int(x) * 0.5 + 0.5 for x in input().split()]

add = [0]
for i in cnt:
    add.append(add[-1]+i)

ans = [add[i+K]-add[i] for i in range(N-K+1)]

print(max(ans))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import numpy as np

N, K = map(int, input().split())
p = np.array(list(map(int, input().split())))
p = (p+1) / 2

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

Submission status: Accepted

Solution code:
def ii():return int(input())
def iim():return map(int,input().split())
def iil():return list(map(int,input().split()))
def ism():return map(str,input().split())
def isl():return list(map(str,input().split()))

n,k = iim()
P = iil()
Psum = []
tmp = 0
for i in P:
    tmp += i
    Psum.append(tmp)

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

print((ans+k)/2)

Submission status: Accepted

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

maxsum = 0
maxindex = 0
p_sum = 0
for i in range(k):
    p_sum += P[i]
maxsum = p_sum
maxindex = 0
for i in range(1, n - k + 1):
    p_sum = p_sum - P[i - 1] + P[i + k - 1]
    if p_sum > maxsum:
        maxsum = p_sum
        maxindex = i
result = 0
for i in range(maxindex, maxindex + k):
    result += (1 + P[i]) * P[i] / 2 / P[i]
print(result)

Submission status: Accepted

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

e = []

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

tmp = sum(e[:k])
maxV = tmp

for i in range(n-k):
    tmp += e[i+k] - e[i]
    maxV = max(maxV, tmp)

print(maxV)

Submission status: Accepted

Solution code:
N, K = [int(_) for _ in input().split()]
P = [int(_) for _ in input().split()]
E = [(p + 1)/2 for p in P]
sumE = sum(E[0:K])
ans = sumE
for i in range(1, N-K+1):
    sumE = sumE - E[i-1] + E[i+K-1]
    ans = max(ans, sumE)
print(ans)

Submission status: Accepted

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

res = sum(p_[:k])
cnt = sum(p_[:k])
for i in range(1,n-k+1):
    cnt = cnt - p_[i-1] + p_[i+k-1]
    res = max(res,cnt)
print(res)

Submission status: Accepted

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