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:
n,k=map(int,input().split()))
i=list(map(int,input().split()))
l=[0]*(n-k)
for j in range(n-k):
  l[j]=i[j+k]-i[j]
place=0
plus=0
for j in range(n-k):
  plus=plus+l(j)
  if plus>0:
    place=j+1
    plus=0
a=0
for j in range(k):
  a+=(i[j+place]+1)//2
print(a)

Submission status: Runtime Error

Solution code:
import sys
from functools import lru_cache
def input(): return sys.stdin.readline().rstrip()

def calc(n):
    if n == 1:
        return 1
    else:
        return n + calc(n - 1)

def main():
    N, K = map(int, input().split())
    P = tuple(map(int, input().split()))

    l = 0
    sum_v = 0
    max_v = 0
    max_i = 0
    ind = 0
    for i in range(N-K+1):
        while l < K:
            sum_v += P[ind]
            ind += 1
            l += 1
        if sum_v > max_v:
            max_v = sum_v
            max_i = i
        l -= 1
        sum_v -= P[i]
    print(sum([calc(p) / p for p in P[max_i:max_i+K]]))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
P = map(int, input().split())
res = -1
for i in range(N-K+1):
  PP = P[i:K]
  mp = float(sum(PP)) / len(PP)
  if res < mp:
    res = mp

print(res)

Submission status: Runtime Error

Solution code:
N, K = map(int, input.split())
P = map(int, input.split())
res = -1
for i in range(N-K+1):
  PP = P[i:K]
  mp = float(sum(PP)) / len(PP)
  if res < mp:
    res = mp

print(res)

Submission status: Runtime Error

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

Submission status: Runtime Error

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

P2 = [(n*(n+1))/2/n for n in P]

S = sum(P2[:K])
max_s = S
for i in range(1, N-K):
    S -= P2[i-1]
    S += P2[i+K]

    max_s = max(max_s, S)

print(f'{max_s:.9f}')

Submission status: Runtime Error

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

e3=[sum(e[i:i+k]) for i in range(n-2)]

print(max(e3))

Submission status: Runtime Error

Solution code:
n,k=list(map(int,input().split()))
a=list(map(int,input().split()))
cal=lambda x:(1+x)/2
a=list(map(cal,a))
#print(a)
now=sum(a[:k])
#print(now)
d=a[0]
for i in range(1,n-k+1):
    #print(i)
    tmp=now-d+a[i+k-1]
    ans=max(now,tmp)
    d=a[i]
    now=tmp
    #print(now)
    #print()
print(ans)

Submission status: Runtime Error

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

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

print((ans+K)/2)

Submission status: Runtime Error

Solution code:
from statistics import mean
N, K = map(int, input.split())
P = map(int, input.split())
res = -1
for i in range(N-K+1):
  mp = mean(P[i:K])
  if res < mp:
    res = mp

print(res)

Submission status: Runtime Error

Solution code:
def func(l):
    if l == 1:
        return 1
    else:
        return l + func(l-1)

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

print(ans)

Submission status: Runtime Error

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

q = sum(P[:K])
m = q

for k in range(K):
    if k > 0:
        q = q - P[k-1] + P[K-1+k]
    if m < q:
        m = q

print((m+K)/2)

Submission status: Runtime Error

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

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

Submission status: Runtime Error

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

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

p2 = p.copy()
for i,px in enumerate(p):
  p2[i] = (px+1)/2

max_ans = 0
for i in range(0, N-K):
  ans = sum(p2[i:i+K])
  if ans > max_ans:
    max_ans = ans
    
print(ans)

Submission status: Runtime Error

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

Submission status: Runtime Error

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

pk = np.array([])
ansum = np.array([])
for i,name  in enumerate(p):
    pk = np.append(pk, (name+1)/2)
    if i >= 2:
        ansum = np.append(ansum, np.sum(pk[-k:]))

print(np.max(ansum))

Submission status: Runtime Error

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

Submission status: Runtime Error

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+1):
        sum_.append(sum_[i-1] + i)
    kitai = [k / (i + 1) for i, k in enumerate(sum_[1:])]
    kitai2 = [kitai[i-1] for i in ps]
    ans = []
    for i in range(n-k):
        ans.append(sum(kitai2[i:i+k]))
    print(max(ans))



if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

	ans = 0
	for i in range(N):
		if i+K >= N:
			break

		anstmp = 0
		for i in range(K):
			tmp = P[i+K]
			total = 0
			for j in range(1,tmp+1):
				total += j
			anstmp += total/tmp

		if anstmp > ans:
			ans = anstmp

	print(ans)

if __name__ == "__main__":
	main()

Submission status: Runtime Error

Solution code:
import numpy as np
N, K = map(int, input().split())
P = np.array(input().split(), dtype=int)
# 期待値に変換
Q = P/2 + 0.5
# 累積和をとる
S = Q.cumsum()
# K範囲での最大値
T = S[K:] - S[:-K]

print(max(T))

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
l = list(map(int,input().split()))
x = 0
a = 0
for i in range(n-3):
    b = l[i]+l[i+1]+l[i+2]+l[i+3]
    if b > a:
        a = b
        x = i

def kitai(x):
    ans = 0
    for i in range(1,x+1):
        ans += i
    return ans/x
ans = 0
for i in range(x,x+m):
    ans += kitai(l[i])
print(ans)

Submission status: Runtime Error

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

Submission status: Runtime Error

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

N, K = map(int, readline().split())
p = list(map(int, readline().split()))

p = np.array(p)
a = [sum(p[i:i+K] + 1) / 2 for i in range(N - K)]
print(max(a))

Submission status: Runtime Error

Solution code:
from itertools import accumulate

n, k = map(int, input().split())
e = [(int(i) + 1) / 2 for i in input().split()]
a = list(accumulate(e))
s = [a[i + k] - a[i] for i in range(n - k)]
print(max(a[k - 1], *s))

Submission status: Runtime Error

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

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

ruiseki = [0] * (n + 1)
for i in range(n):
    ruiseki[i + 1] = ruiseki[i] + ans[i]
    
res = 0
for i in range(n):
    if k+i > n:
        break
    res = max(res, ruiseki[k + i] - ruiseki[i])
print(res)

Submission status: Runtime Error

Solution code:
5 3
1 2 2 4 5

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define M1 1000000007
#define M2 998244353
#define ll long long
#define pll pair<ll,ll>
#define REP(i,a,b) for(ll i=a;i<b;i++)
#define REPI(i,a,b) for(ll i=b-1;i>=a;i--)
#define F first
#define S second
#define PB push_back
#define DB pop_back
#define MP make_pair
#define MT make_tuple
#define G(a,b) get<a>(b)
#define V(a) vector<a>

template<typename T>
#define o_set(T) tree<T, null_type,less<T>, rb_tree_tag,tree_order_statistics_node_update>
//member functions :
//1. order_of_key(k) : number of elements strictly lesser than k
//2. find_by_order(k) : k-th element in the set

ll modI(ll a,ll m);
ll gcd(ll a,ll b);
ll powM(ll x,ll y,ll m);
template<typename T>
void pairsort(T a[],T b[],ll n);
ll logint(ll x,ll y);
void Miden(ll **p1,ll n);
void Mmult(ll **p1,ll **p2,ll **ans,ll x,ll y,ll z,ll m);
void Mpow(ll **p1,ll **ans,ll n,ll y,ll m);
pll Egcd(ll x,ll y);
ll PrimRoot(ll n,ll x);
void fft(ll a[],ll n,bool invert,ll m,ll x);
V(ll) PolyMult(V(ll) &a,V(ll) &b,ll m,ll x);

ll gcd(ll x,ll y)
{
    if(x==0) return y;
    return gcd(y%x,x);
}

pll Egcd(ll x,ll y)
{
    if(x==0) return MP(0,1);
    pll t=Egcd(y%x,x);
    return MP(t.S-t.F*(y/x),t.F);
}

ll powM(ll x,ll y,ll m)
{
    ll ans=1,r=1;
    x%=m;
    while(r>0&&r<=y)
    {
        if(r&y)
        {
            ans*=x;
            ans%=m;
        }
        r<<=1;
        x*=x;
        x%=m;
    }
    return ans;
}

ll modI(ll a, ll m)
{
    ll m0=m,y=0,x=1;
    if(m==1) return 0;
    while(a>1)
    {
        ll q=a/m;
        ll t=m;
        m=a%m;
        a=t;
        t=y;
        y=x-q*y;
        x=t;
    }
    if(x<0) x+=m0;
    return x;
}

template<typename T>
void pairsort(T a[],T b[],ll n)
{
    pair<T,T> v[n];
    REP(i,0,n)
    {
        v[i].F=a[i];
        v[i].S=b[i];
    }
    sort(v,v+n);
    REP(i,0,n)
    {
        a[i]=v[i].F;
        b[i]=v[i].S;
    }
}

ll logint(ll x,ll y)
{
    ll ans=0;
    ll a=1;
    for(ll i=0;i<=x;i++)
    {
        if(x<a)
        {
            return ans;
        }
        ans++;
        a*=y;
    }
    return -1;
}

void Miden(ll **p1,ll n)
{
    ll (*x)[n]=(ll(*)[n]) p1;
    REP(i,0,n)
    {
        REP(j,0,n)
        {
            x[i][j]=0;
        }
        x[i][i]=1;
    }
    return;
}

void Mmult(ll **p1,ll **p2,ll **ans,ll x,ll y,ll z,ll m)
{
    ll (*a)[y]=(ll (*)[y])p1;
    ll (*b)[z]=(ll (*)[z])p2;
    ll (*c)[z]=(ll (*)[z])ans;
    REP(i,0,x)
    {
        REP(j,0,z)
        {
            c[i][j]=0;
            REP(k,0,y)
            {
                c[i][j]+=a[i][k]*b[k][j];
                c[i][j]%=m;
            }
        }
    }
    return;
}

void Mpow(ll **p1,ll **ans,ll n,ll y,ll m)
{
    if(y==0)
    {
        Miden(ans,n);
        return;
    }
    ll t[n][n];
    Mpow(p1,(ll **)t,n,y/2,m);
    ll z[n][n];
    Mmult((ll **)t,(ll **)t,(ll **)z,n,n,n,m);
    if(y%2)
    {
        Mmult((ll **)z,p1,ans,n,n,n,m);
    }
    else
    {
        Miden((ll **)t,n);
        Mmult((ll **)z,(ll **)t,ans,n,n,n,m);
    }
    return;
}

ll PrimRoot(ll p,ll x)
{
    //finds primitive root of prime p greater than x(If it doesnt exist, returns 0)
    V(ll) v;
    ll t=p-1;
    REP(i,2,t+1)
    {
        if(i*i>t) break;
        if(t%i==0)
        {
            v.PB((p-1)/i);
            while(t%i==0)
            {
                t/=i;
            }
        }
    }
    if(t>1) v.PB((p-1)/t);
    REP(i,x+1,p)
    {
        ll flag=0;
        REP(j,0,v.size())
        {
            if(powM(i,v[j],p)==1)
            {
                flag=1;
                break;
            }
        }
        if(flag==0)
        {
            return i;
        }
    }

    return 0;
}

void fft(ll a[],ll n,bool invert,ll m,ll x)
{
    if(n==1) return;
    ll d[2][n>>1];
    REP(i,0,n/2)
    {
        d[0][i]=a[i<<1];
        d[1][i]=a[(i<<1)+1];
    }
    fft(d[0],n>>1,invert,m,(x*x)%m);
    fft(d[1],n>>1,invert,m,(x*x)%m);
    ll r=1;
    if(invert) x=modI(x,m);
    REP(i,0,n>>1)
    {
        a[i]=(d[0][i]+(r*d[1][i])%m)%m;
        if(a[i]<0) a[i]+=m;
        a[i+(n>>1)]=(d[0][i]-(r*d[1][i])%m)%m;
        if(a[i+(n>>1)]<0) a[i+(n>>1)]+=m;
        r*=x;
        r%=m;
    }
    if(invert)
    {
        ll inv2=modI(2,m);
        REP(i,0,n)
        {
            a[i]=(a[i]*inv2)%m;
        }
    }
    return;
}

V(ll) PolyMult(V(ll) &a,V(ll) &b,ll m,ll x)
{
    ll n=1;
    while(n<a.size()+b.size())
    { 
        n<<=1;
    }
    ll fa[n]={};
    ll fb[n]={};
    ll f[n]={};
    REP(i,0,a.size())
    {
        fa[i]=a[i];
    }
    REP(i,0,b.size())
    {
        fb[i]=b[i];
    }
    ll y=powM(x,(m-1)/n,m);
    fft(fa,n,false,m,y);
    fft(fb,n,false,m,y);
    REP(i,0,n)
    {
        f[i]=(fa[i]*fb[i])%m;
    }
    fft(f,n,true,m,y);
    V(ll) v(n);
    REP(i,0,n)
    {
        v[i]=f[i];
    }
    return v;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    /*
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    */

    ll ntc=1;
    //cin>>ntc;
    REP(tc,1,ntc+1)
    {
        //cout<<"Case #"<<tc<<": ";

        ll n,k;
        cin>>n>>k;
        ll a[n];
        REP(i,0,n)
        {
            ll t;
            cin>>t;
            a[i]=t;
        }
        sort(a,a+n);
        double ans=0;
        REP(i,n-k,n)
        {
            ans+=(a[i]+1)/2.0;
        }
        cout<<ans;

        cout<<'\n';
    }

    return 0;
}

Submission status: Runtime Error

Solution code:
import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

N , K = list(map(int, sys.stdin.buffer.readline().split()))
P = list(map(int, sys.stdin.buffer.readline().split()))

P = np.array(P, dtype=float)
E = (P + 1) / 2
cs = E.cumsum()


ans = (cs[K:] - cs[:-K]).max()
ans = max(ans, cs[K - 1])
print(ans)

Submission status: Runtime Error

Solution code:
n=int(input())
A=[int(i) for i in input().split()]
if len(set(A))==n:
    print("YES")
else:
    print("NO")