Как решить задачу на питоне без превышения времени. Как это сделать?

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

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

если игрок в предыдущий день не посещал игру, то за сегодняшнее посещение он получит награду уровня 1;

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

если игрок в предыдущий день зашёл в игру и получил награду уровня n
, то за сегодняшнее посещение он получит награду уровня 1.

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

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

Первая строка входных данных содержит натуральные числа n
и m (1 ≤n,m≤ 1000) — количества уровней наград и дней до турнира.

Вторая строка входных данных содержит n
целых чисел a1,a2, ...,an (1 ≤ai≤ 1000), где ai — величина награды i−го уровня в золотых монетах.

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

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

Примечание

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

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

3 3                                                8
4 2 1


Вот мои наработки, но не получается. выводит неверный ответ:
n, m = map(int, input().split())
a = list(map(int, input().split()))
res = 0
i = 0
b = 1
while i < m:
    if b == n + 1:
        b = 0
        res += a[0]
    else:
        if i <= m - 3:
            if a[0] * 2 > a[b - 1] + a[b] + a[b + 1]:
                res += a[0] * 2
                b = 0
                i += 2
            else:
                res += a[b - 1]
        else:
            res += a[b - 1]
    b += 1
    i += 1
print(res)
  • Вопрос задан
  • 140 просмотров
Пригласить эксперта
Ответы на вопрос 1
@MrRobott
На работки не твои, а другого человека.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы