http://algospot.com/judge/problem/read/FESTIVAL

gistfile1.py

# Brute-force
def solve(costs, mindays):
    mincost = None
    availdays = len(costs)
    for days in xrange(mindays, availdays + 1):
        for start in xrange(availdays - days + 1):
            # costs = 0, 1, 2, 3 (availdays=4), days = 2
            # => (0, 1), (1, 2), (2, 3)
            # last start = 2 = availdays-days = 4 - 2
            cost = sum(costs[start:start+days]) / float(days)
            if mincost is None or mincost > cost:
                mincost = cost
    return mincost

# Memoized
def solve(costs, mindays):
    availdays = len(costs)

    # invariant: memo[start] == sum(costs[start:start+days])
    memo = []

    days = mindays
    for start in xrange(availdays - days + 1):
        cost = sum(costs[start:start+days])
        memo.append(cost)
    mincost = min(memo) / float(mindays)
    
    for days in xrange(mindays + 1, availdays + 1):
        #print days-1, [x/float(days-1) for x in memo]
        #memo.pop()
        for start in xrange(availdays - days + 1):
            # costs = 0, 1, 2, 3 (availdays=4), days = 2
            # => (0, 1), (1, 2), (2, 3)
            # last start = 2 = availdays-days = 4 - 2
            memo[start] += costs[start + days - 1]
            cost = memo[start] / float(days)
            if mincost > cost:
                mincost = cost
    return mincost

C = input()
for i in xrange(C):
    N, L = map(int, raw_input().split())
    costs = map(int, raw_input().split())
    print '%.10f' % solve(costs, L)