Решить задачу на Python?

Question

[maksim-mshp]

Ежедневные награды

Миша установил на свой телефон новую игру «Мемтест 2к17». В ней предусмотрены ежедневные награды за посещение. Награды бывают n уровней.
Тип награды зависит от награды за предыдущий день, а именно:

• если игрок в предыдущий день не посещал игру, то за сегодняшнее посещение он получит награду уровня 1
  
• если игрок в предыдущий день зашёл в игру и получил награду уровня k (k≠n), то за сегодняшнее посещение он получит награду уровня k + 1
  
• если игрок в предыдущий день зашёл в игру и получил награду уровня n, то за сегодняшнее посещение он получит награду уровня 1
  

На Форуме для Крутых Программистов Миша выяснил, что награды каждого из уровней составляют соответственно a₁,a₂, ...,a_n золотых монет. Через m дней состоится турнир по «Мемтест 2к17», к которому Миша хочет собрать как можно больше золотых монет. Помогите ему спланировать посещения игры на протяжении m дней, оставшихся до турнира. Найдите наибольшее количество золотых монет, которое он сможет получить за счёт ежедневных наград в этот период. Можно считать, что игра установлена в первый из этих m дней, то есть до этого Миша в неё ни разу не заходил.

Входные данные

Первая строка входных данных содержит натуральные числа n и m (1 ≤n,m≤ 1000) — количества уровней наград и дней до турнира.
Вторая строка входных данных содержит n целых чисел a₁,a₂, ...,a_n (1 ≤ aⁱ ≤ 1000), где aⁱ — величина награды i−го уровня в золотых монетах.

Выходные данные

Выведите одно натуральное число — наибольшее количество золотых монет, которое Миша сможет получить до турнира.

Примечание

В первом тесте из примера Мише выгодно заходить в игру каждый день. Тогда он получит 1 + 2 + 4 = 7 золотых монет.
Во втором тесте из примера Мише выгодно заходить в игру в первый и третий день, получив в каждый из них по 4 монеты, тогда в сумме он получит 8 монет.

Примеры

Ввод
3 3
4 2 1
Вывод
8

Ввод
3 3
1 2 4
Вывод
7

Вот мои наработки, но не работает

n, m = map(int, input().split())
a = list(map(int, input().split()))
summa = 0 # a[0]
i = 0
for j in range(m - 1):
    if a[i + 1] >= a[i]:
        if i == 0:
            summa = a[0]
        summa += a[i + 1]
        i += 1
    else:
        if a[i + 1] >= a[0]:
            if i == 0:
                summa = a[0]
            summa += a[i + 1]
            i += 1
        else:
            # Эта часть кода наверно неправильная
            if a[0] * 2 >= a[i] + a[i + 1] + a[i + 2]:
                summa += a[0]
                i = 0
            else:
                if i == 0:
                    summa = a[0]
                summa += a[i + 1]
                i += 1
print(summa)

Comments

[Антон Федорян]

почему бы не указать ссылку на ресурс где можно потестировать решение?

Answer 1

[Антон Федорян]

n, m = 3, 3
bounty = [4, 2, 1]

coins = 0

# Игра установлена
queue = [(0, 0, 0)]
while queue:
    score, k, day = queue.pop(0)
    # Дни перед турниром
    day += 1
    if day > m:
        # Наступил день турнира
        coins = max(coins, score)
    else:
        # Еще есть время собирать монеты
        # Пропустим этот день
        queue.append((score, 0, day))
        k += 1
        # А лучше соберем награду
        score += bounty[(k - 1) % n]
        queue.append((score, k, day))

print(coins)  # 8

Comments

[maksim-mshp]

Пишет что программа слишком долго выполняется. Можно ли как-то ускорить?

[longclaps]

queue.pop(0)
queue.popleft()

[Аморти Константин]

Нет такого атрибута popleft() у списков. НЕ РАБОТАЕТ!!! Помогите, время не проходит!