1. Очередь на двух стеках

Очередь с поддержкой минимума построена на двух стеках с поддержкой минимума.

# очередь, которая умеет возвращать минимум всех элементов в ней
class MinQueue:
    def __init__(self):
        self._s1 = []     # первый стек хранит только значения без минимумов
        self._s1_min = [] # текущий минимум всего первого стека
        self._s2 = []     # второй стек хранит только минимумы без значений

    # константа
    def len(self):
        return len(self._s1) + len(self._s2)

    # константа
    def min(self, default=None):
        # минимум по обоим стекам
        return min(self._s1_min + self._s2[-1:], default=default)

    # константа
    def push(self, v):
        self._s1.append(v)                       # добавить в первый стек
        self._s1_min = [min([v] + self._s1_min)] # обновить минимум первого стека

    # амортизированная константа
    def pop(self):
        if not self._s2: # если второй стек пуст
            while self._s1: # пока первый стек не пуст
                # положить во второй стек новый минимум
                self._s2.append(min([self._s1.pop()] + self._s2[-1:]))
            self._s1_min = [] # стереть минимум первого стека
        self._s2.pop()


# последовательное чтение целых чисел из входного потока
def ints():
    while True:
        yield from map(int, input().split())


def main():
    it = ints()

    n = next(it) # число клеток в полоске
    k = next(it) # максимальная длина прыжка

    # содержит минимальные суммы для последовательных клеток
    q = MinQueue()
    for _ in range(n):
        v = q.min(default=0) + next(it) # сердце алгоритма
        if q.len() >= k:
            q.pop()
        q.push(v)

    print(v) # печать последнего элемента очереди


main()

2. Упорядоченная по возрастанию очередь

Идея заимствована из ответа MBo. Обычный deque, но новые элементы удаляют из конца очереди элементы больше либо равные им. Понятно, что эти большие элементы повлиять на минимум в будущем не смогут. Такая очередь упорядочена по возрастанию в каждый момент времени.

import collections


# очередь, которая умеет возвращать минимум всех элементов в ней
class MinQueue:
    def __init__(self):
        self._i = 0 # индекс хвоста очереди
        self._q = collections.deque() # (индекс, значение), значения возрастают

    # константа
    def len(self):
        return self._i - self._q[0][0] if self._q else 0

    # константа
    def min(self, default=None):
        return self._q[0][1] if self._q else default

    # амортизированная константа
    def push(self, v):
        while self._q and self._q[-1][1] >= v:
            self._q.pop()
        self._q.append((self._i, v))
        self._i += 1

    # константа
    def pop(self):
        self._q.popleft()

Сравнение

Обе очереди обеспечивают линейную сложность решения задачи. У какой лучше константа?

В таблице через дробь записаны времена для "двух стеков" и "упорядоченной очереди". Упорядоченная очередь мало замечает изменение k – на случайных данных эта очередь короткая. "Два стека" всегда хуже. Иногда в два раза, иногда больше.

Восстановление маршрута

Если к элементам очереди добавить маршрут (список индексов), его можно будет восстановить:

def main():
    it = ints()

    n = next(it) # число клеток в полоске
    k = next(it) # максимальная длина прыжка

    # содержит пары (минимальная сумма, маршрут) для последовательных клеток
    q = MinQueue()
    for i in range(n):
        v, r = q.min(default=(0, None))
        if q.len() >= k:
            q.pop()
        v += next(it) # сердце алгоритма
        r = i, r
        q.push((v, r))

    print(v, r) # печать последнего элемента очереди