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:
N, K = map(int,input().split())
s = list(map(int,input().split()))
t = [0] * (N - K + 1)
k = 0
for i in range (K):
    k = k + s[i]
t[0] = k
for i in range(N - K):
    t[i + 1] = t[i] + s[i + K] - s[i]
A = max(t)
B = (A + K)/2
print(B)

Submission status: Accepted

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

means = [(1+p)/2. for p in ps]

for i in range(n-k+1):
    if i == 0:
        cur = sum(means[i:i+k])
        out = cur
    else:
        cur = cur - means[i-1] + means[i+k-1]
        out = max(cur, out)

print(out)

Submission status: Accepted

Solution code:
N, K = map(int, input().split());
p = list(map(int, input().split()));
sum = 0;
max_sum = 0;
for i in range(K):
  sum += p[i]

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

print((max_sum+K) / 2)

Submission status: Accepted

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

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

max,tmp = sum(Q[0:K]),sum(Q[0:K])
for i in range(N-K):
    tmp = tmp + Q[K+i] - Q[i]
    if max < tmp:
        max = tmp

print(max)

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
l=ans

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

Submission status: Accepted

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






print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
N,K = map(int,stdin.readline().split())
P = list(map(int,stdin.readline().split()))
B = sum(P[0:K])
A = B
for i in range(N-K):
	B = B - P[i] + P[i+K]
	A = max(A,B)
print((A+K)/2)

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
from operator import itemgetter, mul
from copy import deepcopy
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()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

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

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

accs = [0]*N
accs[0] = acc[0]
for i in range(1, N):
	accs[i] = accs[i - 1] + acc[i]

ma = 0
for i in range(K - 1, N):
	ma2 = 0
	if i == K - 1:
		ma2 = accs[i]
	else:
		ma2 = accs[i] - accs[i - K]
	if ma < ma2:
		ma = ma2

print(ma)

Submission status: Accepted

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

def E(N):
    SUM = N*(N+1)/2
    return SUM / N

def solve(N: int, K: int, p: "List[int]"):
    P = [E(val) for val in p]

    group_sum = sum(P[:K])
    memo = [group_sum]

    for n in range(N-K):
        group_sum = group_sum - P[n] + P[n+K]
        memo.append(group_sum)

    print(max(memo))
    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:
n,k=list(map(int,input().split()))
a=list(map(int,input().split()))
  
ans=0
for i in range(k):
  ans += (a[i]+1)/2
past=ans
for i in range(1,n-k+1):
  tmp = past - (a[i-1]+1)/2 +  (a[i+k-1]+1)/2
  if ans<tmp:
    ans=tmp
  past = tmp
    
print(ans)

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

Submission status: Accepted

Solution code:
def pk(x):
  x=int(x)
  return (x+1)//2 if x%2 else x//2+0.5
n,k = map(int,input().split())
l = list(map(pk,input().split()))
p = m=sum(l[:k])
for i in range(k,n):
  p=p-l[i-k]+l[i]
  m=max(p,m)
print(m)

Submission status: Accepted

Solution code:
#D
N, K = map(int, input().split())
P = list(map(int, input().split()))
ans = sum(P[0:K])
sum_P = ans

for i in range(1, N-K+1):
    sum_P = sum_P - P[i-1] + P[i+K-1]
    ans = max(ans, sum_P)
#     ans = max(ans, K+0.5*(sum_P-K))
    
print(K+0.5*(ans-K))

Submission status: Accepted

Solution code:
def main():
    n, k = map(int, input().split(" "))
    line = [int(s) for s in input().split(" ")]
    max_num = 0
    start = 0
    total = 0
    for i in range(k):
        total += line[i]
        if max_num < line[i]:
            max_num = line[i]
    max_sum = total
    for i in range(k, n):
        total = total + line[i] - line[i - k]
        if max_num < line[i]:
            max_num = line[i]
        if max_sum < total:
            max_sum = total
            start = i - k + 1
    kitai = [0.0 for _ in range(max_num + 1)]
    total = 0
    for i in range(1, max_num + 1):
        total += i
        kitai[i] = total / i
    total = 0
    for i in range(start, start + k):
        total += kitai[line[i]]
    print(total)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
d = defaultdict(int)

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

for i in range(1, 1000+1):
  t = 0
  for s in range(1, i+1):
    t += s * (1 / i)

  d[i] = t

ans = 0
t = 0

for index, i in enumerate(li):
  t += d[i]

  if index > K-1:
    t -= d[li[index-K]]

  if ans < t:
    ans = t

print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
p = list(map(int, input().split()))
ans = 0
dp = [0]*N
dp[0] = sum(p[:K])
for i in range(N-K):
    dp[i+1] = dp[i] - p[i] + p[i+K]
index = dp.index(max(dp))
for i in range(index, index+K):
    ans += 0.5*p[i]*(p[i]+1)/p[i]
print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
p = list(map(int, input().split()))
Expected_val = []
for val in p:
    sum_val = (val * (val + 1)) // 2
    Expected_val.append(sum_val / val)
# print(Expected_val)

left = 0
right = K

ans = sum(Expected_val[left:right])
tmp_ans = ans
# print(ans)
for i in range(N - K):
    tmp_ans = tmp_ans - Expected_val[left + i] + Expected_val[right + i]
    if tmp_ans > ans:
        ans = tmp_ans
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def expectation(p):
    return 0.5 * sum(p) + 0.5 * len(p)


def main():
    n, k = map(int, input().split())
    p = list(map(int, input().split()))
    max_num = sum(p[0:k])
    max_idx = 0
    lst = [max_num]
    for i in range(1, n-k+1):
        num = lst[i-1] + p[i+k-1] - p[i-1]
        lst.append(num)

        if num >= max_num:
            max_num = num
            max_idx = i
    print(expectation(p[max_idx:max_idx+k]))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# coding: utf-8


def solve(*args: str) -> str:
    n, k = map(int, args[0].split())
    P = list(map(int, args[1].split()))

    S = [0]*(n+1)
    for i, p in enumerate(P):
        S[i+1] += S[i] + P[i]

    ret = 0
    for i in range(k, n+1):
        ret = max(ret, (S[i]-S[i-k]+k)/2)

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Submission status: Accepted

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

mydata = []

kazu = list(range(1,1001))
for i in p_L:

    kitai = sum(kazu[0:i])/i
    mydata.append(kitai)

res = [0] * (n+1)

res[0] = mydata[0]
for i in range(len(mydata)-1):
    res[i+1] = res[i] + mydata[i+1]

# print(mydata)
# print(res)
# print("----")
ans = 0
for i in range(n):
    tmp = res[i] - res[i-k]
    ans = max(ans,tmp)
    #print(mydata[i:i+k])
print(ans)

Submission status: Accepted

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

d = []
d.append(sum(p[0:k]))

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

md = d.index(max(d))

print(sum([ (1/2 *( i * (i + 1)))/ i for i in p[md:md + k]]))

Submission status: Accepted

Solution code:
from itertools import accumulate
n,k = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
b = []

num = 0
maxi= 0
l = list(accumulate([0] + a))
for i in range(0,n-k+1):
    if l[i+k] - l[i] > maxi:
        maxi = l[i+k] - l[i]
        num = i  

for i in range(n):
    b.append((1+a[i])/2)
    
ans = sum(b[num:k+num])
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

n,k=mii()
arra=limii()
arr=[]
s=[0]
chk=0
for i in range(n):
    arri=arra[i]
    arr.append((arri*(arri+1)//2)/arri)
    

for i in arr:s.append(s[-1]+i)

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

print(chk)

Submission status: Accepted

Solution code:
S_n = lambda n:n*(n+1)//2

def solve():
  N,K = map(int, input().split())
  P = list(map(int, input().split()))
  Q_idx = 0
  Q = P[:K]
  sum_Q = sum(Q)
  sum_Q_ = sum(Q)
  for i in range(N-K):
    sum_Q_ = sum_Q_ - P[i] + P[K+i]
    if sum_Q < sum_Q_:
      Q_idx = i+1
      sum_Q = sum_Q_

  Q = P[Q_idx:Q_idx+K]
  # print(Q)
  print(sum(S_n(q)/q for q in Q))
  
solve()

Submission status: Accepted

Solution code:
#import numpy as np
import sys
input=sys.stdin.readline

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

#p=np.array(list(map(int,input().split())))
func=lambda x: ((int(x)+1.)/2.)
p=list(map(func,input().split()))

#p=(p+1.)/2.
s=sum(p[0:k])
max_p=s

#for i in range(n-k+1):
for i in range(n-k):
    #s=np.sum(p[i:i+k])
    s=s-p[i]+p[i+k]
    if  max_p < s:
        max_p=s

print(max_p)

Submission status: Accepted

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

kk = sum(p[:K])
res = kk

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

res = res/2 + K/2
print(res)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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

max = 0

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

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


print(ans)

Submission status: Accepted

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

pe_sum = 0.0
pe_sum_max = 0.0

for i in range(K):
    pe_sum += p[i] / 2 + 0.5

pe_sum_max = pe_sum

for i in range(K,N):
    pe_sum += (p[i] / 2 + 0.5) - (p[i-K] / 2 + 0.5)
    pe_sum_max = max(pe_sum,pe_sum_max)

print(pe_sum_max)

Submission status: Accepted

Solution code:
import copy

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

S=[]
for _ in range(N-K+1):
    S.append(0)

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

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

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

print(ans)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
p = list(map(int,input().split()))
def maxexp(p,K):
    s = 0 
    for i in range(0,K):
        s = s + p[i]
        t = s
    for j in range(0,len(p)-K):
        s = s - p[j] + p[j+K]
        t = max(s,t)
    return (t+K)/2
print(maxexp(p,K))

Submission status: Accepted

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

Submission status: Accepted

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

max_x = 0
idx = 0
x = 0

if n == k:
    print((sum(p) + k) / 2)
    exit()

for i in range(n-k):
    x += p[i+k] - p[i]
    if max_x < x:
        max_x = x
        idx = i+1

ans = (sum(p[idx:idx+k]) + k) / 2
print(ans)

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])*(p[i]*(1+p[i])/2))

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

ans=[a]
for i in range(1,n-k+1):
  a=a-e[i-1]+e[i+k-1]
  ans.append(a)

print(max(ans))

Submission status: Accepted

Solution code:
def resolve():
    N, K = map(int, input().split())
    p = list(map(int, input().split()))
    l = [0]*N
    l[0] = p[0]+1
    for i in range(1, N):
        l[i] = l[i-1]+p[i]+1
    ans = l[K-1]
    for i in range(N-K):
        tmp = l[K+i]-l[i]
        if tmp > ans:
            ans = tmp
    print(ans/2)
resolve()

Submission status: Accepted

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

l = list(map(int, input().split()))
dp = [0.5+0.5*i for i in range(max(l)+1)]
dp[0] = 0

# print(dp)
tmp = 0
for i in range(k-1):
    tmp += dp[l[i]]

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

Submission status: Accepted

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

M = [sum(P[:K]) / 2 + K / 2]

for i in range(1, N-K+1):
    M.append(M[i-1] - P[i-1]/2 + P[i-1+K]/2)


print(max(M))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

IN=lambda : map(int, input().split())
mod=1000000007

#+++++

def main():
	n, k = IN()
	pl = list(IN())
	ppl=[(v+1)/2 for v in pl]
	#pa(ppl)
	ss=sum(ppl[:k])
	ret=ss
	#pa((ss,ret))
	for i in range(n-k):
		ss-=ppl[i]
		ss+=ppl[i+k]
		ret=max(ret,ss)
		#pa((ss,ret))
		
	print(ret)
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
import math

debug = False

def log(text):
    if debug:
        print(text)

def parse_input(lines_as_string = None):

    global debug
    lines = []
    if lines_as_string is None:
        debug = False
#        for line in sys.stdin:
#            lines.append(line)
        lines.append(input())
        lines.append(input())
    else:
        debug = True
        lines = [e for e in lines_as_string.split("\n")][1:-1]
    

    (n, k) = [int(e) for e in lines[0].split(' ')]
    p = [int(e) for e in lines[1].split(' ')]

    return (n, k, p)

def solve(n, k, p):

    current = sum([e + 1 for e in p[0:k]]) / 2
    result = current
    for i in range(n):

        if i + k < n: 
            next = current - (p[i] + 1) / 2 + (p[i+k] + 1) / 2
            if next > result:
                result = next
            current = next
        else:
            break


    return result

def main():
    # 出力
    result = solve(*parse_input())
    if isinstance(result, list):
        for r in result:
            print("%s" % r)
    else:
        print("%s" % result)

if __name__ == '__main__':

    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return list(map(int, sys.stdin.readline().split()))
def II(): return int(sys.stdin.readline())
def LS(): return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]

def main():
    n, k = LI()
    ps = LI()
    sum_ = [0]
    for i in range(1, 1000+2):
        sum_.append(sum_[i-1] + i)
    kitai = [ke / (i + 1) for i, ke in enumerate(sum_[1:])]
    kitai2 = [kitai[i-1] for i in ps]
    ans = []
    for i in range(n-k+1):
        if i == 0:
            ans.append(sum(kitai2[0:k]))
        else:
            ans.append(ans[i-1] - kitai2[i-1] + kitai2[i+k-1])
    print(max(ans))




if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

ex_pre = 0
for i in range(k):
    ex_pre += (p[i]+1)/2

ex_max = ex_pre
for i in range(k, n):
    ex = ex_pre + (p[i]+1)/2 - (p[i-k]+1)/2
    ex_max = max(ex, ex_max)
    ex_pre = ex

print(ex_max)

Submission status: Accepted

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

x = sum(p[0:k])
ans_i = 0
ans_max = x
ans = 0

for i in range(1, n-k+1):
    x = x - p[i-1] + p[i+k-1]
    if x > ans_max:
        ans_max = x
        ans_i = i
        
for j in range(ans_i, ans_i+k):
    ans += (p[j]+1)/2
print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
l = list(map(int, input().split()))
at = l[0]
ans = 0
max_i = 0
max_l = sum(l[:k])
hikaku = sum(l[:k])
if k == 1:
    a = max(l)
    print(a * (a + 1) / 2 / a)
else:
    for i in range(1, n - k + 1):
        hikaku = hikaku - at + l[i + k - 1]
        at = l[i]
        if max_l < hikaku:
            max_i = i
            max_l = hikaku
    for i in range(k):
        a = l[max_i + i]
        ans += a * (a + 1) / 2 / a
    print(ans)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
P = list(map(int,input().split()))
ans = 0
n_max = 0
place = 0
n_sum = sum(P[:K])
for i in range(N - K):
	n_sum = n_sum - P[i] + P[i+K]
	if n_max <= n_sum:
		n_max = n_sum
		place = i + 1
for i in range(place,place + K):
	ans += (1 + P[i]) /2 
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

##### 無限 #####
# f_inf = float('inf')

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

def main():
	N,K = inputMap()
	P = inputList()

	kikan1 = 0
	maaxx = 0
	base = 0
	for i in range(N):
		if i == 0:
			tmp = 0
			for j in range(K):
				tmp += P[i+j]
			base = tmp
			continue

		#print(i)
		if i+K > N:
			break
		#print(i)
		tmp = base - P[i-1] + P[i+K-1]
		base = tmp
		if tmp > maaxx:
			maaxx = tmp
			kikan1 = i

	#print(kikan1)
	ans = 0
	for j in range(K):
		#print(P[kikan1+j])
		tmp = P[kikan1+j]
		total = 0
		for jj in range(1,tmp+1):
			total += jj
		ans += total/tmp

	print(ans)

if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
b=[]
max1=0
s=0
c=[]
p=0
if n==k:
    for i in range(n):
        p += (1 / a[i]) * (a[i] * (a[i] + 1) / 2)
else:
    for i in range(n):
        s+=a[i]
        c.append(s)

        if i-k>-1:
            b.append(s-c[i-k])


    t=max(b)
    r=b.index(t)

    for i in range(r+1,r+k+1):
        p+=(1/a[i])*(a[i]*(a[i]+1)/2)
print(p)

Submission status: Accepted

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

k_list = [(i+1)/2 for i in N_list]


memo = sum(k_list[0:K])
accum_list = [memo]

for i in range(N-K):
    memo += k_list[i+K] - k_list[i]
    accum_list.append(memo)

print(max(accum_list))

Submission status: Accepted

Solution code:
def acinput():
    return list(map(int, input().split(" ")))


import numpy as np

N,K=acinput()
p=np.array(acinput())

pp=(p+1)/2

pp=np.insert(pp,0,0)
p_cs=np.cumsum(pp)

res=0

for i in range(K,N+1):
    res=max(res,(p_cs[i]-p_cs[i-K]))
    #tmp = (p[i:(i+K)]+1)/2
    #res = max(res, np.sum(tmp))


print(res)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# vim:fenc=utf-8 ff=unix


def solv(n, k, p):
    total = sum(p[0:k])
    max_total = total
    pl = p[0]
    for i in range(1, n-k+1):
        pr = p[i+k-1]
        total = total - pl + pr
        if total > max_total:
            max_total = total
        pl = p[i]
    return (max_total + k) / 2


if __name__ == "__main__":

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

    ans = solv(n, k, p)

    print(ans)

Submission status: Accepted

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

prev = sum(p[0:k])
sum_max = prev
for i in range(n-k+1):
    if i == 0:
        tmp = prev
    else:
        tmp = prev - p[i-1] + p[i+k-1]

    sum_max = max(sum_max, tmp)
    prev = tmp

print(sum_max)

Submission status: Accepted

Solution code:
import math
N,K=map(int,input().split())
p=list(map(int,input().split()))
bufexp=0
exp=0
buf=0
max=0
for i in range(K):
    buf=buf+p[i]
    bufexp=bufexp+(1+p[i])/2
left=p[0]
#print(bufexp)
#print(bufexp,buf)
for i in range(N-K):
    if buf>max:
        #print(i,bufexp)
        exp=bufexp
        max=buf
    bufexp=bufexp-((1+left)/2)+((1+p[i+K])/2)
    buf=buf-left+p[i+K]
    left=p[i+1]
    #print(i,bufexp,buf)
if buf>max:
    print(bufexp)
else:
    print(exp)

Submission status: Accepted

Solution code:
#!python3.4
# -*- coding: utf-8 -*-
# abc154/abc154_d
import sys

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [i2s() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def main():
    N,K = i2nn()
    q = [(1+int(s))/2 for s in i2s().split()]
    sum_pi = 0
    sum_k = sum(q[0:K])
    sum_k_max = sum_k
    for i in range(K, N):
        sum_k += q[i] - q[i - K]
        if sum_k_max < sum_k:
            sum_k_max = sum_k
    print(sum_k_max)
    return

main()

Submission status: Accepted

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

N, K = list(map(int, input().split()))
p_list = list(map(int, input().split()))
c_list = []

k_list = []
total = 0
for x in range(1001):
    total += x
    if x == 0:
        k_list.append(0)
    else:
        k_list.append(total / x)

max_t = -float("inf")
max_kp = -float("inf")
kp_list = []
t_list = []
for i, p in enumerate(p_list):  # 200000
    kp = k_list[p]
    if i != 0:
        c_list.append(c_list[i - 1] + p)
        kp_list.append(kp_list[i - 1] + kp)
    else:
        c_list.append(p)
        kp_list.append(kp)

    if i >= K - 1:
        if i - K < 0:
            t = c_list[i]
        else:
            t = c_list[i] - c_list[i - K]
        t_list.append(t)

        if t > max_t:
            if i - K < 0:
                max_kp = kp_list[i]
            else:
                max_kp = kp_list[i] - kp_list[i - K]
            max_t = t

ans = max_kp
print(ans)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
li = list(map(int,input().split()))
mux = 0
s = 0

def div(n):
    return (n + 1)/2

for i in range(k):
    s += div(li[i])
mux = s 	

for i in range(k,len(li)):
    s -= div(li[i-k])
    s += div(li[i])
    if s > mux:
        mux = s
print(mux)

Submission status: Accepted

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


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


Rn = list(map(lambda x: f(x)/x, Pn))

Sn = [0] * (N+1)
for i in range(1, N+1):
    Sn[i] = Sn[i-1] + Rn[i-1]

ans = -float("inf")
for i in range(K, N+1):
    # print(i, i-1)
    ans = max(ans, Sn[i] - Sn[i-K])

print(ans)

Submission status: Accepted

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

maxsum = -1
cur = sum(Pe[0:K])
maxsum = cur
for i in range(1, N-K+1):
    cur = cur - Pe[i-1] + Pe[i+K-1]
    if cur > maxsum:
        maxsum = cur

print(maxsum)

Submission status: Accepted

Solution code:

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

ll=[]
for i in range(n):
    ll.append((l[i]+1)/2)

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

print(max(lll))

Submission status: Accepted

Solution code:
N,K=list(map(int,input().split()))
P=list(map(int,input().split()))
ans=[0]
ans[0]=sum(P[0:K])
for i in range(K,len(P)):
  ans.append(ans[-1]-P[i-K]+P[i])
print((max(ans)+K)*0.5)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from itertools import accumulate

R = lambda: map(int, input().split())

n, k = R()
a = [0] + list(accumulate(R()))
print((max(y - x for x, y in zip(a, a[k:])) + k) / 2)

Submission status: Accepted

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

B = [0]*(N-K+1)
B[0] = sum(p[0:K])
for i in range(1, N-K+1):
    B[i] = B[i-1] - p[i-1] + p[i+K-1]
    
max_ind = B.index(max(B))

ep = 0
for i in range(K):
    ep += (p[max_ind+i]*(p[max_ind+i]+1))/(2*p[max_ind+i])

print(ep)

Submission status: Accepted

Solution code:
n, k = map(lambda x: int(x), input().split(" "))
Ps = list(map(lambda x: int(x), input().split(" ")))

result = 0
expected_list = []
temp_result = 0
for i, p in enumerate(Ps):
    temp = (p * (p + 1) / 2 )/ p
    expected_list.append(temp)
    temp_result += temp
    if i+1 >= k:
        result = max(result, temp_result)
        temp_result -= expected_list[i-k+1]

print(result)

Submission status: Accepted

Solution code:
import math
import sys


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

tmp = sum(P[0:K])
max = tmp
# print(tmp,max)
for x in range(K,N):
    tmp = tmp - P[x-K] + P[x]
    if tmp > max:
        max = tmp
    # print(tmp,max)
print((float(max)+K)/float(2))