Untitled

 avatar
unknown
plain_text
6 months ago
644 B
3
Indexable
n, d = map(int, input().split())
a = list(map(int, input().split()))

l, r = -1, 1e9
res = ()

def good(mid):
    pref_sum = [0]
    for x in range(n):
        pref_sum.append(pref_sum[-1] + (a[x] - mid))
    
    m = pref_sum[0]
    index1 = 0

    for o in range(d, n + 1):
        if pref_sum[o] - m >= 0:
            return True, (index1+1, o)

        if pref_sum[o - d + 1] < m:
            m = pref_sum[o - d + 1]
            index1 = o - d + 1

    return False, []

while r - l > 1e-10:
    mid = (l + r) / 2
    found, segment = good(mid)
    if found:
        res = segment
        l = mid  
    else:
        r = mid  

print(*res)
Editor is loading...
Leave a Comment